# Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 20 of its 91 references that are in the map.
- First posted on arXiv 19 Feb 2025.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 20 of 20)

- [Generative Adversarial Imitation from Observation](https://mlsanity.com/paper/1807.06158/) (2018)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Recent Advances in Imitation Learning from Observation](https://mlsanity.com/paper/1905.13566/) (2019)
- [Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning](https://mlsanity.com/paper/2407.15007/) (2024)
- [Learning Linear-Quadratic Regulators Efficiently with only √T Regret](https://mlsanity.com/paper/1902.06223/) (2019)
- [Online Apprenticeship Learning](https://mlsanity.com/paper/2102.06924/) (2021)
- [When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning](https://mlsanity.com/paper/2302.07457/) (2023)
- [Regret Bounds for Discounted MDPs](https://mlsanity.com/paper/2002.05138/) (2020)
- [Refined Regret for Adversarial MDPs with Linear Function Approximation](https://mlsanity.com/paper/2301.12942/) (2023)
- [Provably Efficient Adversarial Imitation Learning with Unknown Transitions](https://mlsanity.com/paper/2306.06563/) (2023)
- [Diffusing States and Matching Scores: A New Framework for Imitation Learning](https://mlsanity.com/paper/2410.13855/) (2024)
- [Rate-Optimal Policy Optimization for Linear Markov Decision Processes](https://mlsanity.com/paper/2308.14642/) (2023)
- [Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysis](https://mlsanity.com/paper/2208.01899/) (2022)
- [Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback](https://mlsanity.com/paper/2310.11550/) (2023)
- [Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees](https://mlsanity.com/paper/2210.01282/) (2022)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation](https://mlsanity.com/paper/2404.12648/) (2024)
- [How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach](https://mlsanity.com/paper/2406.03812/) (2024)
- [Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics](https://mlsanity.com/paper/2406.11810/) (2024)
- [Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions](https://mlsanity.com/paper/2406.11640/) (2024)

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

- [Outcome-based Exploration for LLM Reasoning](https://mlsanity.com/paper/2509.06941/) (2025)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPs](https://mlsanity.com/paper/2505.19946/) (2025)
- [Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning](https://mlsanity.com/paper/2505.17610/) (2025)
- [Offline and Online KL-Regularized RLHF under Differential Privacy](https://mlsanity.com/paper/2510.13512/) (2025)
- [Eluder dimension: localise it!](https://mlsanity.com/paper/2601.09825/) (2026)
- [Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning](https://mlsanity.com/paper/2510.09487/) (2025)
- [Multi-agent imitation learning with function approximation: Linear Markov games and beyond](https://mlsanity.com/paper/2602.22810/) (2026)
- [Value Mirror Descent for Reinforcement Learning](https://mlsanity.com/paper/2604.06039/) (2026)
- [Fast Rates for Inverse Reinforcement Learning](https://mlsanity.com/paper/2605.14599/) (2026)
- [Provably avoiding over-optimization in Direct Preference Optimization without knowing the data distribution](https://mlsanity.com/paper/2602.06239/) (2026)
- [Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation](https://mlsanity.com/paper/2605.12000/) (2026)

## Abstract (arXiv)

We study the problem of reinforcement learning in infinite-horizon discounted linear Markov decision processes (MDPs), and propose the first computationally efficient algorithm achieving rate-optimal regret guarantees in this setting. Our main idea is to combine two classic techniques for optimistic exploration: additive exploration bonuses applied to the reward function, and artificial transitions made to an absorbing state with maximal return. We show that, combined with a regularized approximate dynamic-programming scheme, the resulting algorithm achieves a regret of order tildeO (√d3 (1 - γ)- 7 / 2 T), where T is the total number of sample transitions, γ ∈ (0,1) is the discount factor, and d is the feature dimensionality. The results continue to hold against adversarial reward sequences, enabling application of our method to the problem of imitation learning in linear MDPs, where we achieve state-of-the-art results.