mlsanityData to 7 Oct 2026

Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation

arXiv 2212.13540 ↗First posted 27 Dec 2022stat.ML cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

We study model-based reinforcement learning (RL) for episodic Markov decision processes (MDP) whose transition probability is parametrized by an unknown transition core with features of state and action. Despite much recent progress in analyzing algorithms in the linear MDP setting, the understanding of more general transition models is very restrictive. In this paper, we establish a provably efficient RL algorithm for the MDP whose state transition is given by a multinomial logistic model. To balance the exploration-exploitation trade-off, we propose an upper confidence bound-based algorithm. We show that our proposed algorithm achieves tildeO(d √H3 T) regret bound where d is the dimension of the transition core, H is the horizon, and T is the total number of steps. To the best of our knowledge, this is the first model-based RL algorithm with multinomial logistic function approximation with provable guarantees. We also comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms the existing methods, hence achieving both provable efficiency and practical superior performance.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 34 of its 58 references that are in the map. First posted on arXiv 27 Dec 2022.

Builds on

34 of 58 references.

References · 34

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  7. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  12. 2017Deep Exploration via Randomized Value Functionscited by 155
22 more
  1. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  2. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  3. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  4. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  5. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  6. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  7. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  8. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  9. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  10. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  11. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  12. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  13. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  14. 2017Scalable Generalized Linear Bandits: Online Computation and Hashingcited by 63
  15. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  16. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  17. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
  18. 2019Perturbed-History Exploration in Stochastic Linear Banditscited by 28
  19. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  20. 2020Algorithms for Non-Stationary Generalized Linear Banditscited by 23
  21. 2021Multinomial Logit Contextual Bandits: Provable Optimality and Practicalitycited by 21
  22. 2021Dynamic pricing and assortment under a contextual MNL demandcited by 20

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 3; 2025: 4; 2026: 3.

13 papers.

Sort:

By area:

  1. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  2. 2023Model-based Offline Reinforcement Learning with Count-based Conservatismcited by 16
  3. 2025Improved Online Confidence Bounds for Multinomial Logistic Banditscited by 14
  4. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  5. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  6. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4
  7. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  8. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  9. 2025Episodic Contextual Bandits with Knapsacks under Conversion Modelscited by 1
  10. 2023Revisiting Weighted Strategy for Non-stationary Parametric Banditscited by 0
  11. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
  12. 2026Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilitiescited by 0
1 more
  1. 2026Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPscited by 0