Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity

2023-10-02 · Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini

We theoretically explore the relationship between sample-efficiency and adaptivity in reinforcement learning. An algorithm is sample-efficient if it uses a number of queries $n$ to the environment that is polynomial in the dimension $d$ of the problem. Adaptivity refers to the frequency at which queries are sent and feedback is processed to update the querying strategy. To investigate this interplay, we employ a learning framework that allows sending queries in $K$ batches, with feedback being processed and queries updated after each batch. This model encompasses the whole adaptivity spectrum, ranging from non-adaptive 'offline' ($K=1$) to fully adaptive ($K=n$) scenarios, and regimes in between. For the problems of policy evaluation and best-policy identification under $d$-dimensional linear function approximation, we establish $\Omega(\log \log d)$ lower bounds on the number of batches $K$ required for sample-efficient algorithms with $n = O(poly(d))$ queries. Our results show that just having adaptivity ($K>1$) does not necessarily guarantee sample-efficiency. Notably, the adaptivity-boundary for sample-efficiency is not between offline reinforcement learning ($K=1$), where sample-efficiency was known to not be possible, and adaptive settings. Instead, the boundary lies between different regimes of adaptivity and depends on the problem dimension.

📄 PDF Abstract BibTeX arXiv:2310.01616

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning

Multi-batch Reinforcement Learning via Sample Transfer and Imitation Learning

2021-09-29 · Di wu, Tianyu Li, David Meger, Michael Jenkin 외

Reinforcement learning (RL), especially deep reinforcement learning, has achieved impressive performance on different control tasks. Unfortunately, most online reinforcement learning algorithms require a large number of …

continuous-control Continuous Control Deep Reinforcement Learning Imitation Learning+4

Benchmarking Sample Selection Strategies for Batch Reinforcement Learning

2021-09-29 · Yuwei Fu, Di wu, Benoit Boulet

Training sample section techniques, such as prioritized experience replay (PER), have been recognized as of significant importance for online reinforcement learning algorithms. Efficient sample selection can help further…

Benchmarking Imitation Learning reinforcement-learning Reinforcement Learning+1

Scaling Off-Policy Reinforcement Learning with Batch and Weight Normalization

2025-02-11 · Daniel Palenicek, Florian Vogt, Jan Peters

Reinforcement learning has achieved significant milestones, but sample efficiency remains a bottleneck for real-world applications. Recently, CrossQ has demonstrated state-of-the-art sample efficiency with a low update-t…

continuous-control Continuous Control reinforcement-learning Reinforcement Learning

CrossQ: Batch Normalization in Deep Reinforcement Learning for Greater Sample Efficiency and Simplicity

2019-02-14 · Aditya Bhatt, Daniel Palenicek, Boris Belousov, Max Argus 외

Sample efficiency is a crucial problem in deep reinforcement learning. Recent algorithms, such as REDQ and DroQ, found a way to improve the sample efficiency by increasing the update-to-data (UTD) ratio to 20 gradient up…

continuous-control Continuous Control Deep Reinforcement Learning reinforcement-learning+2

Switching the Loss Reduces the Cost in Batch Reinforcement Learning

2024-03-08 · Alex Ayoub, Kaiwen Wang, Vincent Liu, Samuel Robertson 외

We propose training fitted Q-iteration with log-loss (FQI-LOG) for batch reinforcement learning (RL). We show that the number of samples needed to learn a near-optimal policy with FQI-LOG scales with the accumulated cost…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)