Lune

NeurIPS2024Top-tier venue

Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation

Wooseong Cho, Taehyun Hwang, Joongkyu Lee, Min-hwan Oh

Abstract

We study reinforcement learning with multinomial logistic (MNL) function approximation where the underlying transition probability kernel of the Markov decision processes (MDPs) is parametrized by an unknown transition core with features of state and action. For the finite horizon episodic setting with inhomogeneous state transitions, we propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. For our first algorithm, RRL-MNL\texttt{RRL-MNL}, we adapt optimistic sampling to ensure the optimism of the estimated value function with sufficient frequency. We establish that RRL-MNL\texttt{RRL-MNL} achieves a O~(κ−1d32H32T)\tilde{O}(\kappa^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T}) frequentist regret bound with constant-time computational cost per episode. Here, dd is the dimension of the transition core, HH is the horizon length, TT is the total number of steps, and κ\kappa is a problem-dependent constant. Despite the simplicity and practicality of RRL-MNL\texttt{RRL-MNL}, its regret bound scales with κ−1\kappa^{-1}, which is potentially large in the worst case. To improve the dependence on κ−1\kappa^{-1}, we propose ORRL-MNL\texttt{ORRL-MNL}, which estimates the value function using the local gradient information of the MNL transition model. We show that its frequentist regret bound is O~(d32H32T+κ−1d2H2)\tilde{O}(d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T} + \kappa^{-1} d^2 H^2). To the best of our knowledge, these are the first randomized RL algorithms for the MNL transition model that achieve statistical guarantees with constant-time computational cost per episode. Numerical experiments demonstrate the superior performance of the proposed algorithms.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

4 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Tractable Multinomial Logit Contextual Bandits with Non-Linear Utilities cites Improved Online Confidence Bounds for Multinomial Logistic Bandits
  • Provably Efficient Exploration in Policy Optimization cites Model-Based Reinforcement Learning with Value-Targeted Regression
  • Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options cites Improved Online Confidence Bounds for Multinomial Logistic Bandits
  • Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms cites Provably Efficient Exploration in Policy Optimization
  • Diversified Multinomial Logit Contextual Bandits cites Improved Online Confidence Bounds for Multinomial Logistic Bandits
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers4

  1. Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple OptionsJoongkyu Lee, Seouh-won Yi, Min-hwan OhNeurIPS 2025 · 3 citations
  2. Tractable Multinomial Logit Contextual Bandits with Non-Linear UtilitiesTaehyun Hwang, Dahngoon Kim, Min-hwan OhNeurIPS 2025
  3. Improved Online Confidence Bounds for Multinomial Logistic BanditsJoongkyu Lee, Min-hwan OhICML 2025
  4. Diversified Multinomial Logit Contextual BanditsHeesang Ann, Taehyun Hwang, Min-hwan OhICLR 2026

Builds on30

  1. Model-Based Reinforcement Learning with Value-Targeted RegressionAlex Ayoub, Zeyu Jia, Csaba Szepesvári, Mengdi Wang et al.ICML 2020 · 324 citations
  2. Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret BoundLin Yang, Mengdi WangICML 2020 · 308 citations
  3. Provably Efficient Exploration in Policy OptimizationQi Cai, Zhuoran Yang, Chi Jin, Zhaoran WangICML 2020 · 304 citations
  4. Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient AlgorithmsChi Jin, Qinghua Liu, Sobhan MiryoosefiNeurIPS 2021 · 264 citations
  5. Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?Simon S. Du, Sham M. Kakade, Ruosong Wang, Lin F. YangICLR 2020 · 213 citations

Related papers

  1. Model-Based Reinforcement Learning with Multinomial Logistic Function ApproximationTaehyun Hwang, Min-hwan OhAAAI 2023 · 13 citations
  2. Provably Efficient Reinforcement Learning with Multinomial Logit Function ApproximationLong-Fei Li, Yu-Jie Zhang, Peng Zhao, Zhi-Hua ZhouNeurIPS 2024 · 11 citations
  3. Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision ProcessesJiafan He, Heyang Zhao, Dongruo Zhou, Quanquan GuICML 2023 · 68 citations
  4. Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration & PlanningReda Ouhamma, Debabrota Basu, Odalric MaillardAAAI 2023 · 14 citations
  5. Near-Optimal Randomized Exploration for Tabular Markov Decision ProcessesZhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel et al.NeurIPS 2022 · 17 citations
Dusk over the sea between two cliffs drawn in fine vertical lines