Research map / Bandits and online learning / RL theory and MDPs
Randomized Exploration for Reinforcement Learning with Multinomial Logistic 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 RRL-MNL and ORRL-MNL, randomized (optimistic-sampling Thompson-style) RL algorithms for MNL transition models with constant per-episode computation, achieving regret bounds that improve on prior MNL-MDP UCB results and reduce the dependence on the problem constant kappa in the second variant.
Problem
Regret minimization in episodic RL where transitions follow a multinomial logistic (MNL) model with an unknown transition core, requiring randomized exploration with frequentist guarantees and efficient computation.
Approach
Randomized exploration for MNL-MDPs via Gaussian perturbation of the value function with optimistic sampling (max over M samples of the dominant feature) to guarantee optimism with sufficient probability, combined with online Newton/mirror-descent parameter estimation that avoids storing past data; the second variant uses local gradient (centralized feature) Gram matrices to reduce kappa dependenc
Key results
- RRL-MNL achieves tilde-O(kappa^-1 d^{3/2} H^{3/2} sqrt(T)) regret with O(1) computation per episode, the first frequentist regret bound for randomized model-based RL with a non-linear transition model without assuming stochastic optimism.
- ORRL-MNL improves the regret to tilde-O(d^{3/2} H^{3/2} sqrt(T) + kappa^-1 d^2 H^2), removing kappa^-1 from the leading term.
- On a RiverSwim variant (|S|=4,8), the proposed algorithms outperform UCRL-MNL in episodic return and are reported at least 50 times faster in running time over 1,000 episodes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ORRL-MNL instead of RRL-MNL | MNL-MDP reinforcement learning · MNL-MDP | dependence of cumulative regret upper bound on κ: \tilde{\Ocal}(\kappa^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T}) -> \BigOTilde \left( d^{\frac{3}{2}} H^{\frac{3}{2}} | Helped |
| use the proposed algorithms instead of UCRL-MNL | MNL-MDP reinforcement learning · RiverSwim, |S|=4 and |S|=8 | episodic return | Helped |
| use ORRL-MNL or AlgUCB instead of the other evaluated algorithms | MNL-MDP reinforcement learning · RiverSwim | episodes to reach optimal value | Helped |
| use the proposed algorithms instead of UCRL-MNL | MNL-MDP reinforcement learning · RiverSwim runtime, first 1,000 episodes | runtime: at least 50 times faster | Helped |
Limitations
- Regret of RRL-MNL scales with the problem-dependent constant kappa^-1, which can be exponentially large in the worst case.
- Experiments are limited to a RiverSwim variant with small state spaces.
Experimental setup
Benchmarks: RiverSwim (variant)
Metrics: episodic return running time cumulative regret
Baselines: UCRL-MNL
Builds on: UCRL-MNL LSVI-PHE optimistic sampling MNL bandits with online parameter updates
Closest papers by meaning
- Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation (AAAI 2023 · similarity 0.93)
- Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation (NeurIPS 2024 · similarity 0.91)
- Near-Optimal Randomized Exploration for Tabular Markov Decision Processes (NeurIPS 2022 · similarity 0.91)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.90)
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.89)
- Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
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.