Towards Instance-Optimality in Online PAC Reinforcement Learning

2023-10-31 · Aymen Al-Marjani, Andrea Tirinzoni, Emilie Kaufmann

Several recent works have proposed instance-dependent upper bounds on the number of episodes needed to identify, with probability $1-\delta$, an $\varepsilon$-optimal policy in finite-horizon tabular Markov Decision Processes (MDPs). These upper bounds feature various complexity measures for the MDP, which are defined based on different notions of sub-optimality gaps. However, as of now, no lower bound has been established to assess the optimality of any of these complexity measures, except for the special case of MDPs with deterministic transitions. In this paper, we propose the first instance-dependent lower bound on the sample complexity required for the PAC identification of a near-optimal policy in any tabular episodic MDP. Additionally, we demonstrate that the sample complexity of the PEDEL algorithm of \cite{Wagenmaker22linearMDP} closely approaches this lower bound. Considering the intractability of PEDEL, we formulate an open question regarding the possibility of achieving our lower bound using a computationally-efficient algorithm.

📄 PDF Abstract BibTeX arXiv:2311.05638

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning

Deep Reinforcement Learning for Online Routing of Unmanned Aerial Vehicles with Wireless Power Transfer

2022-04-25 · Kaiwen Li, Tao Zhang, Rui Wang, Ling Wang

The unmanned aerial vehicle (UAV) plays an vital role in various applications such as delivery, military mission, disaster rescue, communication, etc., due to its flexibility and versatility. This paper proposes a deep r…

Combinatorial Optimization Deep Reinforcement Learning reinforcement-learning Reinforcement Learning+1

Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning

2024-03-14 · Zhishuai Liu, Pan Xu

Distributionally robust offline reinforcement learning (RL), which seeks robust policy training against environment perturbation by modeling dynamics uncertainty, calls for function approximations when facing large state…

Offline RL Reinforcement Learning (RL)

A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics

2026-07-28 · Zheshun Wu, Renjie Zheng, Jinhang Zuo, Zenglin Xu 외 arxiv

This paper investigates a hybrid reinforcement learning setting in tabular Markov Decision Processes (MDPs), where an agent aims to learn an optimal policy by combining online interactions with a target environment and o…

Reinforcement Learning

Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory

2023-04-24 · Andrew Wagenmaker, Dylan J. Foster

We consider the development of adaptive, instance-dependent algorithms for interactive decision making (bandits, reinforcement learning, and beyond) that, rather than only performing well in the worst case, adapt to favo…

Decision Making reinforcement-learning Reinforcement Learning

Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation

2024-12-13 · Federico Julian Camerota Verdù, Lorenzo Castelli, Luca Bortolussi

We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based combinatorial optimization improvement heuristics. Utilizing pre-trained models on the Euclidean Traveli…

Combinatorial Optimization Deep Reinforcement Learning