Research map / Bandits and online learning / RL theory and MDPs
Test-Time Regret Minimization in Meta Reinforcement Learning
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.
Studies test-time regret minimization in meta RL over a finite set of MDPs with perfectly known tasks, giving a regret lower bound under separation and three "strong identifiability" structures (clusters, tree, revealing policies) that achieve faster rates.
Problem
Test-time regret minimization in meta RL when the set of finite MDP tasks is perfectly known after training: under the separation condition, regret scales with M^2 in known upper bounds, and it is unclear whether linear or sublinear dependence on the number of tasks M is achievable with log(H) rates
Approach
Proves a lower bound Omega(TM log H / lambda) for test-time regret under lambda-separation, showing a linear dependence on M is unavoidable, by linking regret to best policy identification; then proposes strong identifiability assumptions (clustering, tree structure, few revealing policies) with algorithms whose regret depends sublinearly on M.
Key results
- Proves a lower bound Omega(TM log(H)/lambda) on test-time regret under separation, nearly matching the O(TM^2 log(MH)/lambda^4) upper bound of Identify-then-Commit.
- Clustering assumption yields regret O(T(K^2+N^2) log(NH)/lambda^4); tree structure yields O(T d log(dH)/lambda^4) with d = log_{1/beta} M; revealing policies yield O(T I log(MH)/lambda^4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Rely only on separation to minimize test-time regret | Test-time regret minimization in finite-horizon MDPs · Finite-horizon MDPs under separation | regret lower bound: \Omega (TM \log(H)) | Hurt |
| Use coherent clusters and identify the cluster before the task within it | Test-time regret minimization in finite-horizon MDPs · Finite-horizon MDPs with clustering | regret upper bound: \mathcal{O} (T (K^2 + N^2) \log(N H)) | Helped |
| Use a tree structure to split candidate tasks at each identification step | Test-time regret minimization in finite-horizon MDPs · Finite-horizon MDPs with a tree structure | regret upper bound: \mathcal{O} (T d \log (d H)) | Helped |
| Use a small set of revealing policies to collect identification data before offline identification | Test-time regret minimization in finite-horizon MDPs · Finite-horizon MDPs with revealing policies | regret upper bound: \mathcal{O} (T I \log (M H)) | Helped |
| Use clustering for task identification | Test-time regret minimization in finite-horizon MDPs · Finite-horizon MDPs with clustering | regret upper bound: K^2 + N^2 \approx K^2 + M^2 / K^2 | Mixed |
Surprising findings
- Under separation alone, any algorithm achieving log(H) regret must scale at least linearly with M, so the M^2 dependence of prior work is nearly optimal in M up to a factor M.
Limitations
- Assumes perfect knowledge of the task set after training; approximate training is left as future work.
- Strong identifiability assumptions are structural and may not hold in practice; revealing-policy sampling relies on non-standard trajectory rewards and robust MDP solutions.
- Results are for finite task sets; infinite task sets remain open.
Experimental setup
Metrics: test-time regret (upper and lower bounds)
Baselines: Identify-then-Commit
Builds on: Identify-then-Commit domain randomization sim-to-real analysis best policy identification
Closest papers by meaning
- Optimizing Test-Time Compute via Meta Reinforcement Finetuning (ICML 2025 · similarity 0.89)
- Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design (NeurIPS 2025 · similarity 0.88)
- Policy-Regret Minimization in Markov Games with Function Approximation (ICML 2025 · similarity 0.88)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.88)
- Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback (ICML 2025 · similarity 0.88)
- Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning (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.