Regret-optimal Q-learning With Low Cost For Single-agent And Federated Reinforcement Learning

Abstract

Motivated by real-world settings where data collection and policy deployment -- whether for a single agent or across multiple agents -- are costly, we study the problem of on-policy single-agent reinforcement learning (RL) and federated RL (FRL) with a focus on minimizing burn-in costs (the sample sizes needed to reach near-optimal regret) and policy switching or communication costs. In parallel finite-horizon episodic Markov Decision Processes (MDPs) with \(S\) states and \(A\) actions, existing methods either require superlinear burn-in costs in \(S\) and \(A\) or fail to achieve logarithmic switching or communication costs. We propose two novel model-free RL algorithms -- Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost -- that are the first in the literature to simultaneously achieve: (i) the best near-optimal regret among all known model-free RL or FRL algorithms, (ii) low burn-in cost that scales linearly with \(S\) and \(A\), and (iii) logarithmic policy switching cost for s

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhang2025regret

Related papers

• Federated Q-learning: Linear Regret Speedup With Low Communication Cost (2023)0.00
• Gap-dependent Bounds For Federated \(q\)-learning (2025)0.00
• Regret-optimal Model-free Reinforcement Learning For Discounted Mdps With Short Burn-in Time (2023)0.00
• Federated Q-learning With Reference-advantage Decomposition: Almost Optimal Regret And Logarithmic Communication Cost (2024)0.00
• Federated Offline Reinforcement Learning: Collaborative Single-policy Coverage Suffices (2024)0.00
• The Best Of Both Worlds: Reinforcement Learning With Logarithmic Regret And Policy Switches (2022)0.00
• Switching The Loss Reduces The Cost In Batch (offline) Reinforcement Learning (2024)0.00
• Provably Efficient Multi-agent Reinforcement Learning With Fully Decentralized Communication (2021)0.00