Research map / Bandits and online learning / RL theory and MDPs
Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General 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 LOOP, an optimistic lazy-update algorithm with a new complexity measure AGEC for sample-efficient average-reward MDPs under general function approximation, achieving O~(poly(d, sp(V*)) sqrt(T beta)) regret.
Problem
Sample-efficient online exploration in infinite-horizon average-reward MDPs with general function approximation, where prior work covers only tabular or specific linear/model-based classes.
Approach
A new complexity measure AGEC (average-reward generalized eluder coefficient) extending GEC with a transferability constraint, and the LOOP algorithm combining optimistic planning over a discrepancy-based confidence set with lazy (low-switching) policy updates triggered by cumulative squared discrepancy, usable in both model-based and value-based forms.
Key results
- LOOP achieves regret O~(poly(d, sp(V*)) sqrt(T beta)), i.e., O~(sqrt(T)) rate, matching special-case results up to factors.
- AGEC is shown to subsume tabular, linear, linear mixture, eluder-dimension, and newly identified kernel and ABE-dimension AMDP classes.
- The lazy update scheme yields O(log T) policy switches (switching cost O(kappa_G log T)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive lazy policy updates instead of splitting learning into fixed-length epochs | LOOP for AMDPs with general function approximation · AMDPs | regret: \tilde{\mathcal{O}}(T^{3/4}) to \tilde{\mathcal{O}}(\sqrt{T}) | Helped |
Limitations
- The optimistic planning step is a constrained optimization that lacks a computationally efficient solution.
- Requires known span sp(V*) and realizability/completeness assumptions.
- Regret bounds are not claimed to be optimal; sharper bounds left open.
Experimental setup
Metrics: regret
Baselines: Sim-to-Real UCRL2-VTR FOPO UCRL2 Politex AAPI
Builds on: generalized eluder coefficient eluder condition fitted Q-iteration Sim-to-Real UCRL2-VTR
Closest papers by meaning
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.91)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.90)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.89)
- A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs (ICML 2025 · similarity 0.88)
- Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization (AAAI 2024 · similarity 0.88)
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 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.