精选理由
这篇论文首次给出了MNL混合MDPs的极小化最优遗憾界，对研究强化学习理论或设计高效算法的研究者来说，是理解问题复杂度的重要参考。
该论文研究了基于多项逻辑（MNL）模型的马尔可夫决策过程（MDPs）的强化学习问题。现有算法对MNL混合MDPs的遗憾界为Õ(dH²√T)，其中d是特征维度，H是回合长度，T是回合数。作者引入了一个问题依赖常数σ̄_T（≤1/2），衡量最优下游值函数沿学习轨迹的归一化平均方差，并提出了一个遗憾界为Õ(dH²σ̄_T√T)的算法。该算法在最坏情况下恢复现有界，在结构化MDPs（如KL约束鲁棒MDPs）中可将H依赖因子降低H倍。此外，论文证明了匹配的下界Ω(dH²σ̄_T√T)，首次完全刻画了MNL混合MDPs的遗憾复杂度（达到对数因子内的极小化最优）。
AI 翻译 · 中文
该论文研究了基于多项逻辑（MNL）模型的马尔可夫决策过程（MDPs）的强化学习问题。现有算法对MNL混合MDPs的遗憾界为Õ(dH²√T)，其中d是特征维度，H是回合长度，T是回合数。作者引入了一个问题依赖常数σ̄_T（≤1/2），衡量最优下游值函数沿学习轨迹的归一化平均方差，并提出了一个遗憾界为Õ(dH²σ̄_T√T)的算法。该算法在最坏情况下恢复现有界，在结构化MDPs（如KL约束鲁棒MDPs）中可将H依赖因子降低H倍。此外，论文证明了匹配的下界Ω(dH²σ̄_T√T)，首次完全刻画了MNL混合MDPs的遗憾复杂度（达到对数因子内的极小化最优）。
We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of $\smash{\tild…