# Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation

arXiv: https://arxiv.org/abs/2212.13540 · HTML: https://mlsanity.com/paper/2212.13540/

## Key facts

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

## Builds on (most cited first, 30 of 34)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions](https://mlsanity.com/paper/2010.01374/) (2020)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)

## Built on by (most cited first, 13 of 13)

- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Model-based Offline Reinforcement Learning with Count-based Conservatism](https://mlsanity.com/paper/2307.11352/) (2023)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation](https://mlsanity.com/paper/2405.17061/) (2024)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs](https://mlsanity.com/paper/2601.01069/) (2026)
- [Demystifying Linear MDPs and Novel Dynamics Aggregation Framework](https://mlsanity.com/paper/2410.24089/) (2024)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options](https://mlsanity.com/paper/2510.18713/) (2025)
- [Episodic Contextual Bandits with Knapsacks under Conversion Models](https://mlsanity.com/paper/2507.06859/) (2025)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits](https://mlsanity.com/paper/2303.02691/) (2023)
- [Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2411.10906/) (2024)
- [Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities](https://mlsanity.com/paper/2601.06913/) (2026)
- [Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs](https://mlsanity.com/paper/2605.19768/) (2026)

## 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.