Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost

2022-02-13 · Dan Qiao, Ming Yin, Ming Min, Yu-Xiang Wang

We study the problem of reinforcement learning (RL) with low (policy) switching cost - a problem well-motivated by real-life RL applications in which deployments of new policies are costly and the number of policy updates must be low. In this paper, we propose a new algorithm based on stage-wise exploration and adaptive policy elimination that achieves a regret of $\widetilde{O}(\sqrt{H^4S^2AT})$ while requiring a switching cost of $O(HSA \log\log T)$. This is an exponential improvement over the best-known switching cost $O(H^2SA\log T)$ among existing methods with $\widetilde{O}(\mathrm{poly}(H,S,A)\sqrt{T})$ regret. In the above, $S,A$ denotes the number of states and actions in an $H$-horizon episodic Markov Decision Process model with unknown transitions, and $T$ is the number of steps. As a byproduct of our new techniques, we also derive a reward-free exploration algorithm with a switching cost of $O(HSA)$. Furthermore, we prove a pair of information-theoretical lower bounds which say that (1) Any no-regret algorithm must have a switching cost of $\Omega(HSA)$; (2) Any $\widetilde{O}(\sqrt{T})$ regret algorithm must incur a switching cost of $\Omega(HSA\log\log T)$. Both our algorithms are thus optimal in their switching costs.

📄 PDF Abstract BibTeX arXiv:2202.06385

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs

2023-02-24 · Dan Qiao, Ming Yin, Yu-Xiang Wang

In many real-life reinforcement learning (RL) problems, deploying new policies is costly. In those scenarios, algorithms must solve exploration (which requires adaptivity) while switching the deployed policy sparsely (wh…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

A Benchmark for Low-Switching-Cost Reinforcement Learning

2021-12-13 · Shusheng Xu, Yancheng Liang, Yunfei Li, Simon Shaolei Du 외

A ubiquitous requirement in many practical reinforcement learning (RL) applications, including medical treatment, recommendation system, education and robotics, is that the deployed policy that actually interacts with th…

Atari Games reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

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

2025-06-05 · Haochen Zhang, Zhong Zheng, Lingzhou Xue

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 (R…

Q-Learning Reinforcement Learning (RL)

Deep Q-Learning with Low Switching Cost

2021-01-01 · Shusheng Xu, Simon Shaolei Du, Yi Wu

We initiate the study on deep reinforcement learning problems that require low switching cost, i.e., small number of policy switches during training. Such a requirement is ubiquitous in many applications, such as medica…

Atari Games Deep Reinforcement Learning Q-Learning Recommendation Systems+1

Is there a universal parametric city size distribution? Empirical evidence for 70 countries

2023-08-19 · Miguel Puente-Ajovín, Arturo Ramos, Fernando Sanz-Gracia

We study the parametric description of the city size distribution (CSD) of 70 different countries (developed and developing) using seven models, as follows: the lognormal (LN), the loglogistic (LL), the double Pareto log…