后验采样在随机最短路里补上最优阶:OPSRL-SSP 去掉 PSRL-SSP 多出的因子
核心概要
随机最短路(SSP,即带唯一吸收目标、以最小化期望累计代价为目标的强化学习框架)的在线学习此前已有后验采样方法 PSRL-SSP,但其遗憾界比极小极大下界多出一个因子。OPSRL-SSP 通过给状态空间加一个赋乐观边界值的伪状态、按对数时间表抽取后验候选、并对 Dirichlet 伪计数做自适应膨胀,使每个状态-动作对在每个回合起点都以高概率存在乐观转移候选。由此得到以 为主项的高概率遗憾界,主项与极小极大下界一致,并借助代价扰动把分析推广到零代价 SSP。
深度剖析
随机最短路问题现在有了一个后验采样算法,其遗憾界的主项与极小极大下界同阶,即 ,其中 是最优策略期望代价的上界,、 为状态数与动作数, 为回合数。 此前后验采样路线上的 PSRL-SSP 虽在实验中表现良好,其遗憾界相对极小极大下界仍多出一个因子,这正是 Jafarnia-Jahromi 等人提出的开放问题。 该界以至少 的概率成立,且低阶状态复杂度项与 EB-SSP、SVI-SSP 等基于乐观面对不确定性(OFU)的算法所达到的水平一致。
乐观性不是靠显式置信集或探索奖励注入,而是靠后验采样本身的结构改造。 有限时域情节式 MDP 上的乐观后验采样依赖已知时域,而 SSP 的回合长度随机且可能无界,静态采样表不再适用。 算法按回合运行,用计数加倍与回合数增加两个停止条件切分回合,并在增广状态空间上求解平稳贝尔曼不动点。
伪状态给每个采样模型一个通往虚拟边界的正概率,使增广空间上的乐观贝尔曼算子成为严格压缩,从而把单步乐观提升为全局任意时刻乐观。 代价最小化方向需要与奖励最大化不同的乐观先验构造,伪状态把低成本乐观转写成辅助函数的尾事件。 在固定 RandomMDP 与 GridWorld 实例上,OPSRL-SSP 与 ULCVI、SVI-SSP、EB-SSP、PSRL-SSP 表现相当,并优于 LCB-ADVANTAGE-SSP 与 -贪心 Q-learning。
启示与展望
结论针对表格型随机最短路:状态与动作有限、代价函数已知、转移核未知,且需要已知最优策略期望代价的上界 ;实验覆盖固定 RandomMDP、GridWorld 两个实例,以及 20 个独立生成的 RandomMDP 实例,每个实例 20 次 rollout。
算法目前要求知道 ,去掉这一要求被列为后续方向;理论上规定的对数采样数与动态伪计数偏保守,实际实现改用固定小超参数,消融显示增加后验样本数反而略微抬高累计遗憾,乐观先验强度则呈 U 形权衡。
