Research map / Bandits and online learning / RL theory and MDPs
A General Framework for Sequential Decision-Making under Adaptivity Constraints
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 the Eluder-Condition (EC) class as a general function-approximation framework and gives low-switching-cost (O(dH log K)) and batch-learning algorithms for RL with rare policy switches and batch constraints.
Problem
Sequential decision-making under adaptivity constraints (rare policy switches and batch learning) with general function approximation, where prior work covered only tabular, linear, or low-eluder settings.
Approach
Define an l2-type Eluder-Condition class with a stronger eluder property (sum of squared in-sample errors bounded by O(d beta log k)) and a decomposable loss; use a lazy policy-switching rule that updates the optimistic confidence set only when in-sample discrepancy of the current hypothesis exceeds a threshold, and a uniform-grid batch schedule with a good/bad batch analysis.
Key results
- Lazy switching reduces policy switches from 2000 to 92.8 on average over 10 simulations in linear mixture MDP.
- Execution time drops from 321.6 s to 15.9 s versus OPERA-style per-episode updates, with regret slightly larger than OPERA.
- The l2-EC-RS algorithm achieves O~(H sqrt(dK)) regret with O(dH log K) switching cost; batch algorithm gives O~(sqrt(dK)+dK/B) regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use lazy policy switches instead of updating the policy each episode | EC-RS on a linear mixture MDP · Linear mixture MDP, T=2000 | strategy transitions and optimization calls: 2000 -> 92.8 | Helped |
| use lazy policy switches instead of updating the policy each episode | EC-RS on a linear mixture MDP · Linear mixture MDP, T=2000 | execution time (seconds): 321.6 -> 15.9 | Helped |
| use EC-RS with lazy policy switches rather than OPERA | Linear mixture MDP · Linear mixture MDP, T=2000 | regret | Hurt |
Limitations
- Requires a stronger eluder-type assumption than standard eluder argument (square-sum bound with log k factor).
- Batch regret bound has an extra dK/B term; sqrt(K) regret requires B of order sqrt(K/d).
- Experiments limited to a single simulated linear mixture MDP setting.
Experimental setup
Datasets: simulated linear mixture MDP
Benchmarks: linear mixture MDP simulation (T=2000, 10 runs)
Metrics: regret number of policy switches execution time cumulative reward
Baselines: OPERA random policy
Builds on: GOLF OPERA Bellman eluder dimension decomposable loss function
Closest papers by meaning
- Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batching (NeurIPS 2026 · similarity 0.88)
- Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints (ICML 2024 · similarity 0.87)
- Eluder dimension: localise it! (NeurIPS 2025 · similarity 0.87)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.87)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.87)
- Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (NeurIPS 2026 · 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.