在未知转移的对抗性低秩MDP中，首次实现带bandit反馈的高效学习。
Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
- 提出新算法，在未知转移下用全信息反馈将遗憾率降至T^{2/3}。
- 在带bandit反馈时，基于线性损失结构实现T^{2/3}遗憾率。
- 揭示线性结构必要性：无结构时遗憾必随状态数多项式增长。
我们研究具有固定转移和对抗性损失的低秩MDP中的遗憾最小化问题。先前工作仅在两种情形下分析：一是未知转移但全信息反馈（Zhao et al., 2024），二是已知转移但带bandit反馈（Foster et al., 2022）。本文首先将未知转移下的全信息反馈遗憾界从poly(d, A, H)T^{5/6}改进为poly(d, A, H)T^{2/3}，其中d为转移矩阵秩，A为动作数，H为决策步长，T为总轮次。其次，首次研究带bandit反馈且未知转移的设定。假设损失具线性结构，我们设计了基于模型与免模型的算法，均达到poly(d, A, H)T^{2/3}遗憾；此外还提出计算高效的免模型算法，遗憾为poly(d, A, H)T^{4/5}。我们证明：若无线性结构，带bandit反馈时遗憾必须随状态数多项式增长，这与全信息情形（可独立于状态数）形成对比。
原文摘要 · Abstract (English)
We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedback with unknown transitions (Zhao et al., 2024), or bandit loss feedback with known transition (Foster et al., 2022). First, we improve the $poly(d, A, H)T^{5/6}$ regret bound of Zhao et al. (2024) to $poly(d, A, H)T^{2/3}$ for the full-information unknown transition setting, where d is the rank of the transitions, A is the number of actions, H is the horizon length, and T is the number of episodes. Next, we initiate the study on the setting with bandit loss feedback and unknown transitions. Assuming that the loss has a linear structure, we propose both model based and model free algorithms achieving $poly(d, A, H)T^{2/3}$ regret, though they are computationally inefficient. We also propose oracle-efficient model-free algorithms with $poly(d, A, H)T^{4/5}$ regret. We show that the linear structure is necessary for the bandit case without structure on the reward function, the regret has to scale polynomially with the number of states. This is contrary to the full-information case (Zhao et al., 2024), where the regret can be independent of the number of states even for unstructured reward function.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。