mlsanityData to 14 Oct 2026

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

arXiv 2605.19768 ↗First posted 19 May 2026cs.AI cs.LG math.STcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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 smashtildeO(dH2√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 ≤ 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 smashtildeO(dH2barσT√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 smashOmega(dH2barσT√T) lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 17 of its 28 references that are in the map. First posted on arXiv 19 May 2026.

Builds on

17 of 28 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation19 Jun
  2. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation27 May

Other references · 15

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  3. 2016Deep Reinforcement Learning for Dialogue Generationcited by 288
  4. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  5. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  6. 2014A Second-order Bound with Excess Lossescited by 95
  7. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  8. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 57
  9. 2022Jointly Efficient and Optimal Algorithms for Logistic Banditscited by 41
  10. 2017Generalized Self-Concordant Functions: A Recipe for Newton-Type Methodscited by 33
  11. 2021Dynamic pricing and assortment under a contextual MNL demandcited by 20
  12. 2025Improved Online Confidence Bounds for Multinomial Logistic Banditscited by 15
3 more
  1. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  2. 2021UCB-based Algorithms for Multinomial Logistic Regression Banditscited by 12
  3. 2025Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithmcited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  3. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
  4. 2024Information-Theoretic Minimax Regret Bounds for Reinforcement Learning based on Duality
  5. 2024Horizon-Free Regret for Linear Markov Decision Processes
  6. 2025Combinatorial Reinforcement Learning with Preference Feedback
  7. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
  8. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs