Research map / Bandits and online learning / RL theory and MDPs
Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UCRL-MNL-LL and UCRL-MNL-OL for inhomogeneous MNL mixture MDPs, removing the kappa^{-1} dependence from the dominant regret term and achieving constant per-episode storage/time via online mirror descent, plus a logistic-bandit-based lower bound.
Problem
Reinforcement learning with multinomial logit (MNL) transition function approximation in inhomogeneous episodic MDPs, where prior regret bounds scale polynomially with the number of reachable states via kappa^{-1} and computation grows with episode count.
Approach
Replace the Hoeffding-style kappa-scaled confidence set with a kappa-independent Bernstein-type confidence set built from the MLE gradient/Hessian (self-concordant-like log loss), and make the algorithm constant-cost via online mirror descent with look-ahead Hessians and a closed-form second-order Taylor bonus.
Key results
- UCRL-MNL-LL achieves regret Õ(dH^2√K + κ^{-1}d^2H^2), removing κ^{-1} from the dominant term versus Õ(κ^{-1}dH^2√K) of prior work.
- UCRL-MNL-OL matches the same regret with O(1) storage and time per episode.
- A lower bound Ω(dH√(Kκ*)) for infinite-action MNL mixture MDPs via reduction to logistic bandits.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the UCRL-MNL-LL algorithm instead of the prior method | MNL mixture MDPs · MNL mixture MDPs | regret upper bound: $\Ot(\kappa^{-1} d H^2 \sqrt{K})$ -> $\Ot(d H^2 \sqrt{K} + \kappa^{-1} d^2 H^2 )$ | Helped |
| Use UCRL-MNL-OL with online mirror descent and a closed-form bonus instead of historical-data MLE and non-convex optimization | UCRL-MNL-LL · MNL mixture MDPs | storage per episode: $\O(k)$ -> $\O(1)$ | Helped |
| Use UCRL-MNL-OL with online mirror descent and a closed-form bonus instead of historical-data MLE and non-convex optimization | UCRL-MNL-LL · MNL mixture MDPs | time per episode: $\O(k)$ -> $\O(1)$ | Helped |
| Use UCRL-MNL-OL rather than UCRL-MNL-LL | MNL mixture MDPs · MNL mixture MDPs | regret upper bound: $\Ot(d H^2 \sqrt{K} + \kappa^{-1} d^2 H^2 )$ -> $\Ot(d H^2 \sqrt{K} + \kappa^{-1} d^2 H^2 )$ | No clear effect |
| Use a Bernstein-type confidence set rather than the prior confidence set | UCRL-MNL-LL · MNL mixture MDPs | confidence-set radius: $\kappa^{-1}$ -> at least a factor of $\kappa^{-1/2}$ smaller | Helped |
Surprising findings
- The prior work's self-normalized concentration overlooks that noise sums to zero within each stage, violating the standard zero-mean sub-Gaussian condition.
Limitations
- Gap remains between the upper bound and the lower bound; the H dependence is loose by about H^{1/2} relative to a later lower bound.
- The lower bound for the finite action setting is not established by this paper's reduction.
- Lower-order term still scales with κ^{-1}.
Experimental setup
Metrics: regret
Baselines: Hwang and Oh 2023 MNL mixture MDP algorithm
Builds on: MNL mixture MDP (Hwang and Oh 2023) linear mixture MDPs logistic bandits online mirror descent
Closest papers by meaning
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.91)
- Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation (AAAI 2023 · similarity 0.90)
- Provably Efficient Reinforcement Learning with Kernel and Neural Function Approximations (NeurIPS 2020 · similarity 0.90)
- Logarithmic Regret for Reinforcement Learning with Linear Function Approximation (ICML 2021 · similarity 0.89)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.89)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.