后验采样在随机最短路里补上最优阶:OPSRL-SSP 去掉 PSRL-SSP 多出的因子
随机最短路(SSP,即带唯一吸收目标、以最小化期望累计代价为目标的强化学习框架)的在线学习此前已有后验采样方法 PSRL-SSP,但其遗憾界比极小极大下界多出一个因子。OPSRL-SSP 通过给状态空间加一个赋乐观边界值的伪状态、按对数时间表抽取后验候选、并对 Dirichlet 伪计数做自适应膨胀,使每个状态-动作对在每个回合起点都以高概率存在乐观转移候选。由此得到以 为主项的高概率遗憾界,主项与极小极大下界一致,并借助代价扰动把分析推广到零代价 SSP。