mlsanityData to 7 Oct 2026

Test-Time Regret Minimization in Meta Reinforcement Learning

arXiv 2406.02282 ↗First posted 4 Jun 2024cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

Meta reinforcement learning sets a distribution over a set of tasks on which the agent can train at will, then is asked to learn an optimal policy for any test task efficiently. In this paper, we consider a finite set of tasks modeled through Markov decision processes with various dynamics. We assume to have endured a long training phase, from which the set of tasks is perfectly recovered, and we focus on regret minimization against the optimal policy in the unknown test task. Under a separation condition that states the existence of a state-action pair revealing a task against another, Chen et al. (2022) show that O(M2 log(H)) regret can be achieved, where M, H are the number of tasks in the set and test episodes, respectively. In our first contribution, we demonstrate that the latter rate is nearly optimal by developing a novel lower bound for test-time regret minimization under separation, showing that a linear dependence with M is unavoidable. Then, we present a family of stronger yet reasonable assumptions beyond separation, which we call strong identifiability, enabling algorithms achieving fast rates log (H) and sublinear dependence with M simultaneously. Our paper provides a new understanding of the statistical barriers of test-time regret minimization and when fast rates can be achieved.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 38 of its 50 references that are in the map. First posted on arXiv 4 Jun 2024.

Builds on

38 of 50 references.

References · 38

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2020Learning to summarize from human feedbackcited by 2,562
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  5. 2016RL2: Fast Reinforcement Learning via Slow Reinforcement Learningcited by 490
  6. 2019Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variablescited by 372
  7. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  8. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  9. 2019VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learningcited by 210
  10. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  11. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  12. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
26 more
  1. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  2. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  3. 2020Adaptive Reward-Free Explorationcited by 77
  4. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  5. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  6. 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
  7. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  8. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  9. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  10. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  11. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
  12. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  13. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20
  14. 2022Dexterous Manipulation from Images: Autonomous Real-World RL via Substep Guidancecited by 20
  15. 2023Explore to Generalize in Zero-Shot RLcited by 20
  16. 2022On the Effectiveness of Fine-tuning Versus Meta-reinforcement Learningcited by 18
  17. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  18. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  19. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  20. 2022Learning Mixtures of Markov Chains and MDPscited by 12
  21. 2021Regularization Guarantees Generalization in Bayesian Reinforcement Learning through Algorithmic Stabilitycited by 7
  22. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  23. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  24. 2022Meta Reinforcement Learning with Finite Training Tasks -- a Density Estimation Approachcited by 6
  25. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  26. 2023Prospective Side Information for Latent MDPscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 2.

5 papers.

  1. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  2. 2025Test-Time Visual In-Context Tuningcited by 7
  3. 2025A Classification View on Meta Learning Banditscited by 1
  4. 2026Constrained Meta Reinforcement Learning with Provable Test-Time Safetycited by 1
  5. 2026Provably Safe Sim-to-Real Transfercited by 0