Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning

• URL: http://arxiv.org/abs/2506.04626v1
• Date: Thu, 05 Jun 2025 04:36:38 GMT
• Title: Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning
• Authors: Haochen Zhang, Zhong Zheng, Lingzhou Xue,
• Abstract summary: We study the problem of on-policy single-agent reinforcement learning (RL) and federated RL (FRL)<n>We propose two novel model-free RL algorithms -- Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost.
• Score: 4.895986534376972
• License: http://creativecommons.org/licenses/by/4.0/
• 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 single-agent RL or communication cost for FRL. Additionally, we establish gap-dependent theoretical guarantees for both regret and switching/communication costs, improving or matching the best-known gap-dependent bounds.

Related papers

• Accelerating RL for LLM Reasoning with Optimal Advantage Regression [52.0792918455501]
  We propose a novel two-stage policy optimization framework that directly approximates the optimal advantage function.<n>$A$*-PO achieves competitive performance across a wide range of mathematical reasoning benchmarks.<n>It reduces training time by up to 2$times$ and peak memory usage by over 30% compared to PPO, GRPO, and REBEL.
  arXiv  Detail & Related papers  (2025-05-27T03:58:50Z)
• Adaptive $Q$-Network: On-the-fly Target Selection for Deep Reinforcement Learning [18.579378919155864]
  We propose Adaptive $Q$Network (AdaQN) to take into account the non-stationarity of the optimization procedure without requiring additional samples.<n>AdaQN is theoretically sound and empirically validate it in MuJoCo control problems and Atari $2600 games.
  arXiv  Detail & Related papers  (2024-05-25T11:57:43Z)
• Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning [57.154674117714265]
  We show that the number of samples needed to learn a near-optimal policy with FQI-log scales with the accumulated cost of the optimal policy. We empirically verify that FQI-log uses fewer samples than FQI trained with squared loss on problems where the optimal policy reliably achieves the goal.
  arXiv  Detail & Related papers  (2024-03-08T15:30:58Z)
• Imitate the Good and Avoid the Bad: An Incremental Approach to Safe Reinforcement Learning [11.666700714916065]
  Constrained RL is a framework for enforcing safe actions in Reinforcement Learning. Most recent approaches for solving Constrained RL convert the trajectory based cost constraint into a surrogate problem. We present an approach that does not modify the trajectory based cost constraint and instead imitates good'' trajectories.
  arXiv  Detail & Related papers  (2023-12-16T08:48:46Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [66.26739783789387]
  We propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for reinforcement learning. MQL-UCB achieves minimax optimal regret of $tildeO(dsqrtHK)$ when $K$ is sufficiently large and near-optimal policy switching cost. Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.
  arXiv  Detail & Related papers  (2023-11-26T08:31:57Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  We show how to achieve minimax-optimal regret without incurring any burn-in cost.<n>We extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances.
  arXiv  Detail & Related papers  (2023-07-25T15:42:11Z)
• Near-Optimal Adversarial Reinforcement Learning with Switching Costs [43.895798638743784]
  We show how to develop a provably efficient algorithm for adversarial RL with switching costs. Our lower bound indicates that, due to the fundamental challenge of switching costs in adversarial RL, the best achieved regret is no longer achievable. We propose two novel switching-reduced algorithms with regrets that match our lower bound when the transition function is known.
  arXiv  Detail & Related papers  (2023-02-08T23:41:29Z)
• Model-Free $\mu$ Synthesis via Adversarial Reinforcement Learning [2.2725929250900947]
  We develop a model-free version of the well-known $DK$-iteration for solving state-feedback $mu$ synthesis with static $D$-scaling. In the proposed algorithm, the $K$ step mimics the classical central path algorithm via a recently-developed double-loop adversarial RL method as a subroutine. Our study sheds new light on the connections between adversarial RL and robust control.
  arXiv  Detail & Related papers  (2021-11-30T16:29:49Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)
• A Simple Reward-free Approach to Constrained Reinforcement Learning [33.813302183231556]
  This paper bridges reward-free RL and constrained RL. Particularly, we propose a simple meta-algorithm such that given any reward-free RL oracle, the approachability and constrained RL problems can be directly solved with negligible overheads in sample complexity.
  arXiv  Detail & Related papers  (2021-07-12T06:27:30Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.