新算法让强化学习在未知环境模型下仍能自适应地降低决策误差。
Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
- 基于乐观正则化策略追踪设计新型Q值估计器。
- 实现一阶、二阶及路径长度的自适应误差界，含过渡依赖复杂度项。
- 适合关注在线学习与鲁棒性优化的研究者或工程师。
我们研究了在未知转移核的在线周期性表格马尔可夫决策过程中的策略优化问题，目标是同时获得最佳双世界保证和数据依赖的后悔界限。近期工作（Dann et al., 2023；Li et al., 2026）表明，策略优化可在已知转移的情况下自适应于对抗性和随机损失，实现一阶、二阶及路径长度边界，但在转移未知时是否仍能达成此类数据依赖性保证仍悬而未决。本文通过提出一种基于乐观跟随正则领导者的新算法，解决了该问题。核心在于设计了一种新的乐观Q函数估计器，并引入依赖数据的转移奖励以控制估计偏差，其依据为损失预测误差。分析进一步揭示了一个不可避免的依赖转移的复杂度项，反映了估计转移核的固有成本。由此，我们在未知转移条件下首次实现了包含转移依赖复杂度项的一阶、二阶及路径长度边界，同时在随机情形下达到间隙依赖的polylog(T)后悔界。
原文摘要 · Abstract (English)
We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic $Q$-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent $\mathrm{polylog}(T)$ regret in the stochastic regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。