Research map / Reinforcement learning / MDPs and planning
Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated 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.
Proposes Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost, model-free single-agent and federated RL algorithms that combine LCB-based early reference settling with round-based delayed policy updates to achieve near-optimal regret, linear-in-S,A burn-in, and logarithmic switching/communication cost.
Problem
Model-free RL and federated RL in tabular episodic MDPs need near-optimal regret while keeping burn-in cost linear in S and A and switching/communication cost logarithmic in T; prior methods trade off one of these.
Approach
Integrate LCB-based early settlement of the reference function (from Q-EarlySettled-Advantage) with a round-based, event-triggered delayed policy update scheme, and handle the resulting double non-adaptiveness via a surrogate reference function combined with round-wise approximation, plus a refined bonus term.
Key results
- Worst-case regret of Q-EarlySettled-LowCost is O((1+beta) sqrt(H^2 SAT iota^2) + H^6 SA iota^2/beta) with burn-in ~O(SAH^10), linear in S and A, versus S^6A^3H^28 for UCB-Advantage.
- Switching cost of Q-EarlySettled-LowCost is bounded by max{2C+4C log(T/C), 3C} with C = H^2(H+1)SA, i.e. O(H^3 SA log(T/(HSA))) logarithmic in T.
- FedQ-EarlySettled-LowCost burn-in O(MSAH^10) versus O(MS^3A^2H^12) for FedQ-Advantage, with communication rounds logarithmic in T.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Q-EarlySettled-LowCost instead of Q-EarlySettled-Advantage | Single-agent model-free tabular RL · Single-agent tabular episodic MDP | regret: \log(SAT/p) | Helped |
| Use Q-EarlySettled-LowCost instead of Q-EarlySettled-Advantage | Single-agent model-free tabular RL · Single-agent tabular episodic MDP | switching cost | Helped |
| Use Q-EarlySettled-LowCost instead of UCB-Advantage | Single-agent model-free tabular RL · Single-agent tabular episodic MDP | burn-in cost: \tilde{O}(S^6 A^3 H^{28}) -> \tilde{O}(SAH^{10}) | Helped |
| Use FedQ-EarlySettled-LowCost instead of FedQ-Advantage | Federated model-free tabular RL · Federated tabular episodic MDP | burn-in cost: \tilde{O}(MS^3A^2H^{12}) -> \tilde{O}(MSAH^{10}) | Helped |
| Use FedQ-EarlySettled-LowCost instead of FedQ-Advantage | Federated model-free tabular RL · Federated tabular episodic MDP | regret | Helped |
| Add an LCB estimate to settle the reference function early | Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost · Single-agent and federated tabular episodic MDP | burn-in cost: \tilde{O}(S^6A^4H^{28}) -> \tilde{O}(SAH^{10}); O(MS^3A^2H^{12}) -> O(MSAH^{10}) | Helped |
| Remove dependence on (N_h^k)^{3/4} from the reference-advantage cumulative bonus | Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost · Single-agent and federated tabular episodic MDP | regret | Helped |
| Replace the empirical-process treatment with surrogate reference functions and round-wise approximation | Worst-case regret analysis of the proposed algorithms · Single-agent and federated tabular episodic MDP | regret: \log(SAT/p) | Helped |
| Use FedQ-EarlySettled-LowCost instead of FedQ-Hoeffding | Federated model-free tabular RL · Federated tabular episodic MDP, positive gap | gap-dependent regret: a factor of H | Helped |
Limitations
- Gap-dependent switching cost analysis requires full synchronization, random initialization and G-MDP assumptions.
- Regret bound's logarithmic switching cost entails a slight regret increase compared with some prior methods.
- Experiments limited to small synthetic MDPs.
Experimental setup
Datasets: synthetic tabular MDP (H,S,A)=(5,3,2) and (7,10,5)
Benchmarks: synthetic tabular MDP
Metrics: regret switching cost communication cost
Baselines: UCB-Hoeffding UCB-Bernstein UCB2-Hoeffding UCB2-Bernstein UCB-Advantage Q-EarlySettled-Advantage FedQ-Hoeffding FedQ-Bernstein FedQ-Advantage
Builds on: Q-EarlySettled-Advantage UCB-Advantage FedQ-Advantage Fed-UCBVI reference-advantage decomposition
Closest papers by meaning
- Federated $Q$-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost (ICLR 2025 · similarity 0.93)
- Federated Q-Learning: Linear Regret Speedup with Low Communication Cost (ICLR 2024 · similarity 0.93)
- Gap-Dependent Bounds for Federated $Q$-Learning (ICML 2025 · similarity 0.92)
- Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices (ICML 2024 · similarity 0.90)
- Switching the Loss Reduces the Cost in Batch Reinforcement Learning (ICML 2024 · similarity 0.89)
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · 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.