这篇论文首次给出了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的遗憾复杂度（达到对数因子内的极小化最优）。
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic 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{\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.