提出更优的强化学习算法，能自适应复杂度降低误差。
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
- 基于最优价值函数方差设计新算法，动态调整学习效率。
- 理论证明在结构化问题上可将时间步依赖降低至1/H。
- 首次完整刻画该类模型的最坏情况误差边界，适合理论研究者。
研究基于多项式逻辑（MNL）模型建模转移概率的周期性马尔可夫决策过程（MDP）的强化学习问题。现有针对MNL混合MDP的算法达到$ ilde{O}(dH^2 oot{T}{})$的后悔界，其中$d$为特征维度，$H$为每回合长度，$T$为总回合数。受逻辑老虎机文献启发，本文引入一个依赖问题的常数$arσ_T \ \leq 1/2$，用于衡量最优下游价值函数在学习者轨迹上的归一化平均方差。我们提出一种新算法，实现$ ilde{O}(dH^2arσ_T oot{T}{})$的后悔界，在最坏情况下退化为已有结果，但在结构化问题中显著改进。例如，在KL约束鲁棒MDP中，$arσ_T = O(H^{-1})$，使横纵依赖降低$H$倍。进一步建立了匹配的$ ilde{Ω}(dH^2arσ_T oot{T}{})$下界，证明了其最小最大最优性（对数因子内），首次完整刻画了此类模型的后悔复杂度。
原文摘要 · Abstract (English)
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{\tilde{O}(dH^2\sqrt{T})}$ (Li et al., 2024), where $d$ is the feature dimension, $H$ the episode length, and $T$ the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant $\barσ\_T \leq 1/2$, measuring the normalised average variance of the optimal downstream value function along the learner's trajectory. We propose an algorithm achieving a regret of $\smash{\tilde{O}(dH^2\barσ\_T\sqrt{T})}$, which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs, $\barσ\_T = O(H^{-1})$, reducing the horizon dependence by a factor $H$. We further establish a matching $\smash{Ω(dH^2\barσ\_T\sqrt{T})}$ lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。