提出首个在线MDP带聚合反馈的最优策略优化算法
Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
- 设计新型策略优化方法，仅凭全程总损失反馈学习
- 已知动态下达到最优$ ilde Θ(H^2\ \sqrt{SAK})$后悔界
- 未知动态时性能提升超$H^2S^5A^2$倍，适合强化学习研究者
我们研究具有对抗性损失变化和聚合反馈（即全赌徒反馈）的在线有限时域马尔可夫决策过程。在此反馈设置下，智能体仅能观测整个轨迹的总损失，而非各中间步骤的个体损失。本文首次提出适用于该场景的策略优化算法。在已知动态情况下，实现了首个最优后悔界$ ilde Θ(H^2\sqrt{SAK})$，其中$K$为回合数，$H$为每回合时长，$S$为状态数，$A$为动作数。在未知动态情况下，建立了$ ilde O(H^3 S \sqrt{AK})$的后悔界，相比现有最佳结果提升$H^2 S^5 A^2$倍。
原文摘要 · Abstract (English)
We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory. We introduce the first Policy Optimization algorithms for this setting. In the known-dynamics case, we achieve the first \textit{optimal} regret bound of $\tilde Θ(H^2\sqrt{SAK})$, where $K$ is the number of episodes, $H$ is the episode horizon, $S$ is the number of states, and $A$ is the number of actions. In the unknown dynamics case we establish regret bound of $\tilde O(H^3 S \sqrt{AK})$, significantly improving the best known result by a factor of $H^2 S^5 A^2$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。