Active Coverage for PAC Reinforcement Learning

2023-06-23 · Aymen Al-Marjani, Andrea Tirinzoni, Emilie Kaufmann

Collecting and leveraging data with good coverage properties plays a crucial role in different aspects of reinforcement learning (RL), including reward-free exploration and offline learning. However, the notion of "good coverage" really depends on the application at hand, as data suitable for one context may not be so for another. In this paper, we formalize the problem of active coverage in episodic Markov decision processes (MDPs), where the goal is to interact with the environment so as to fulfill given sampling requirements. This framework is sufficiently flexible to specify any desired coverage property, making it applicable to any problem that involves online exploration. Our main contribution is an instance-dependent lower bound on the sample complexity of active coverage and a simple game-theoretic algorithm, CovGame, that nearly matches it. We then show that CovGame can be used as a building block to solve different PAC RL tasks. In particular, we obtain a simple algorithm for PAC reward-free exploration with an instance-dependent sample complexity that, in certain MDPs which are "easy to explore", is lower than the minimax one. By further coupling this exploration algorithm with a new technique to do implicit eliminations in policy space, we obtain a computationally-efficient algorithm for best-policy identification whose instance-dependent sample complexity scales with gaps between policy values.

📄 PDF Abstract BibTeX arXiv:2306.13601

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Scheduling Out-of-Coverage Vehicular Communications Using Reinforcement Learning

2022-07-13 · Taylan Şahin, Ramin Khalili, Mate Boban, Adam Wolisz

Performance of vehicle-to-vehicle (V2V) communications depends highly on the employed scheduling approach. While centralized network schedulers offer high V2V communication reliability, their operation is conventionally …

Management reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Cooperative Informative Sensing for Monitoring Dynamic Indoor Environments via Multi-Agent Reinforcement Learning

2026-04-25 · Kanghoon Lee, Matthew M. Sato, Jinnyeong Yang, Seungro Lee 외 arxiv

Monitoring human activity in indoor environments is important for applications such as facility management, safety assessment, and space utilization analysis. While mobile robot teams offer the potential to actively impr…

Multi-agent Reinforcement Learning

Sample Efficient Active Algorithms for Offline Reinforcement Learning

2026-02-01 · Soumyadeep Roy, Shashwat Kushwaha, Ambedkar Dukkipati arxiv

Offline reinforcement learning (RL) enables policy learning from static data but often suffers from poor coverage of the state-action space and distributional shift problems. This problem can be addressed by allowing lim…

Reinforcement Learning

Anatomical Landmark-Guided Deep Reinforcement Learning for Autonomous Gastric Navigation

2026-05-08 · Haoxuan Wu, Sishen Yuan, Haitao Gao, Zhen Li 외 arxiv

Wireless capsule endoscopy (WCE) enables painless visualization of the gastrointestinal tract, but its diagnostic potential is limited by incomplete mucosal coverage and poor transferability of existing navigation method…

Reinforcement Learning

Attraction-Repulsion Actor-Critic for Continuous Control Reinforcement Learning

2019-09-17 · Thang Doan, Bogdan Mazoure, Moloud Abdar, Audrey Durand 외

Continuous control tasks in reinforcement learning are important because they provide an important framework for learning in high-dimensional state spaces with deceptive rewards, where the agent can easily become trapped…

continuous-control Continuous Control MuJoCo reinforcement-learning+2