Research map / Bandits and online learning / RL theory and MDPs
Minimax Optimal Reinforcement Learning with Quasi-Optimism
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 EQO, a tabular episodic RL algorithm whose bonus is c/N(s,a) (no empirical variance), using a "quasi-optimism" analysis to obtain minimax-optimal regret under a weaker bounded-value assumption.
Problem
Minimax-optimal tabular RL algorithms rely on empirical-variance bonuses, making them complex and often practically slower than suboptimal methods like UCRL2; the paper asks whether provable optimality and practical performance can coexist.
Approach
Replace variance-based bonuses with a simple c/N(s,a) bonus and show that estimated values need not be fully optimistic but only "quasi-optimistic" (underestimating by a bounded amount), using Freedman-type concentration to decouple variance and visit counts; regret bound holds under only bounded optimal values rather than bounded returns or rewards.
Key results
- Regret bound of H√(SAK) plus HS²A non-leading term with sharper logarithmic factors than prior minimax-optimal bounds, under only bounded optimal values (0 ≤ V* ≤ H).
- Mistake-style PAC and best-policy identification bound of Õ(H²SA log(1/δ)/ε²) for ε < H/S.
- On RiverSwim (S=30, 40), EQO reportedly outperforms UCRL2, UCBVI-BF, EULER, ORLC, and MVP in regret and execution time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a c / N(s, a) exploration bonus instead of empirical-variance-based bonuses | EQO on RiverSwim · RiverSwim, S = 30 and S = 40 | cumulative regret | Helped |
| Use EQO instead of the compared algorithms | Tabular RL algorithms on RiverSwim · RiverSwim | execution time | Helped |
Surprising findings
- The c/N bonus guarantees only quasi-optimism, not full optimism, yet still yields minimax-optimal regret.
Limitations
- Analysis is for tabular, time-homogeneous MDPs only.
- Empirical evaluation limited to the RiverSwim environment.
Experimental setup
Datasets: RiverSwim MDP
Benchmarks: RiverSwim
Metrics: cumulative regret execution time
Baselines: UCRL2 UCBVI-BF EULER ORLC MVP
Builds on: UCBVI-BF UCBVI Freedman's inequality
Closest papers by meaning
- Bayesian Optimistic Optimization: Optimistic Exploration for Model-based Reinforcement Learning (NeurIPS 2022 · similarity 0.91)
- Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.90)
- NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.89)
- Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning (ICLR 2024 · similarity 0.89)
- Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL (NeurIPS 2025 · similarity 0.89)
- Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF (ICLR 2025 · 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.