A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints

2020-09-23 · Krishna C. Kalagarla, Rahul Jain, Pierluigi Nuzzo

Constrained Markov Decision Processes (CMDPs) formalize sequential decision-making problems whose objective is to minimize a cost function while satisfying constraints on various cost functions. In this paper, we consider the setting of episodic fixed-horizon CMDPs. We propose an online algorithm which leverages the linear programming formulation of finite-horizon CMDP for repeated optimistic planning to provide a probably approximately correct (PAC) guarantee on the number of episodes needed to ensure an $\epsilon$-optimal policy, i.e., with resulting objective value within $\epsilon$ of the optimal value and satisfying the constraints within $\epsilon$-tolerance, with probability at least $1-\delta$. The number of episodes needed is shown to be of the order $\tilde{\mathcal{O}}\big(\frac{|S||A|C^{2}H^{2}}{\epsilon^{2}}\log\frac{1}{\delta}\big)$, where $C$ is the upper bound on the number of possible successor states for a state-action pair. Therefore, if $C \ll |S|$, the number of episodes needed have a linear dependence on the state and action space sizes $|S|$ and $|A|$, respectively, and quadratic dependence on the time horizon $H$.

📄 PDF Abstract BibTeX arXiv:2009.11348

Code (0)

등록된 구현이 없습니다.

Tasks

Decision MakingSequential Decision Making

Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding

2026-01-31 · Jiamin Xu, Kyra Gan arxiv

Online reinforcement learning in non-episodic, finite-horizon MDPs remains underexplored and is challenged by the need to estimate returns to a fixed terminal time. Existing infinite-horizon methods, which often rely on …

Reinforcement Learning

Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP

2019-01-27 · ICLR 2020 1 · Kefan Dong, Yuanhao Wang, Xiaoyu Chen, Li-Wei Wang

A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. \cite{jin2018q} proposed a Q-learning algorithm with UCB exploration policy, and proved it has …

Q-Learning Reinforcement Learning

Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

2015-10-29 · NeurIPS 2015 12 · Christoph Dann, Emma Brunskill

Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-worl…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

e-COP : Episodic Constrained Optimization of Policies

2024-06-13 · Akhil Agnihotri, Rahul Jain, Deepak Ramachandran, Sahil Singla

In this paper, we present the $\texttt{e-COP}$ algorithm, the first policy optimization algorithm for constrained Reinforcement Learning (RL) in episodic (finite horizon) settings. Such formulations are applicable when t…

LEMMA reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methods

2021-09-13 · Xin Guo, Anran Hu, Junzi Zhang

When designing algorithms for finite-time-horizon episodic reinforcement learning problems, a common approach is to introduce a fictitious discount factor and use stationary policies for approximations. Empirically, it h…

Policy Gradient Methods reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)