A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP
- URL: http://arxiv.org/abs/2207.06147v1
- Date: Wed, 13 Jul 2022 12:13:38 GMT
- Title: A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP
- Authors: Fan Chen, Junyu Zhang, Zaiwen Wen
- Abstract summary: Constrained Markov Decision Process (CMDP) is an important framework for safe Reinforcement Learning.
In this paper, we focus on solving the CMDP problems where only offline data are available.
By adopting the concept of the single-policy concentrability coefficient $C*$, we establish an $Omegaleft(fracminleft|mathcalS||mathcalA|,|mathcalS|+Iright C*(fracminleft|mathcalS
- Score: 12.37249250512371
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: As an important framework for safe Reinforcement Learning, the Constrained
Markov Decision Process (CMDP) has been extensively studied in the recent
literature. However, despite the rich results under various on-policy learning
settings, there still lacks some essential understanding of the offline CMDP
problems, in terms of both the algorithm design and the information theoretic
sample complexity lower bound. In this paper, we focus on solving the CMDP
problems where only offline data are available. By adopting the concept of the
single-policy concentrability coefficient $C^*$, we establish an
$\Omega\left(\frac{\min\left\{|\mathcal{S}||\mathcal{A}|,|\mathcal{S}|+I\right\}
C^*}{(1-\gamma)^3\epsilon^2}\right)$ sample complexity lower bound for the
offline CMDP problem, where $I$ stands for the number of constraints. By
introducing a simple but novel deviation control mechanism, we propose a
near-optimal primal-dual learning algorithm called DPDL. This algorithm
provably guarantees zero constraint violation and its sample complexity matches
the above lower bound except for an $\tilde{\mathcal{O}}((1-\gamma)^{-1})$
factor. Comprehensive discussion on how to deal with the unknown constant $C^*$
and the potential asynchronous structure on the offline dataset are also
included.
Related papers
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators.
Key to our solution is a novel projection technique based on ideas from harmonic analysis.
Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
arXiv Detail & Related papers (2024-05-10T09:58:47Z) - Achieving $\tilde{O}(1/ε)$ Sample Complexity for Constrained Markov Decision Process [4.685121820790546]
We consider the reinforcement learning problem for the constrained Markov decision process (CMDP)
We derive a logarithmic regret bound, which translates into a $O(frac1Deltacdotepscdotlog2(1/eps))$ sample complexity bound.
Our algorithm operates in the primal space and we resolve the primal LP for the CMDP problem at each period in an online manner.
arXiv Detail & Related papers (2024-02-26T06:08:25Z) - Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
This paper considers the best policy identification problem in online Constrained Markov Decision Processes (CMDPs)
We are interested in algorithms that are model-free, have low regret, and identify an approximately optimal policy with a high probability.
Existing model-free algorithms for online CMDPs with sublinear regret and constraint violation do not provide any convergence guarantee to an optimal policy.
arXiv Detail & Related papers (2023-09-27T04:33:09Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP)
We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
arXiv Detail & Related papers (2022-12-01T15:57:58Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model.
The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
arXiv Detail & Related papers (2022-08-11T04:12:50Z) - Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
We provide minimax upper and lower bounds on the sample complexity for learning near-optimal policies in a discounted CMDP.
We show that learning CMDPs is as easy as MDPs when small constraint violations are allowed, but inherently more difficult when we demand zero constraint violation.
arXiv Detail & Related papers (2022-06-13T15:58:14Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
offline reinforcement learning (RL) learns using pre-collected data without further exploration.
Prior algorithms or analyses either suffer from suboptimal sample complexities or incur high burn-in cost to reach sample optimality.
We demonstrate that the model-based (or "plug-in") approach achieves minimax-optimal sample complexity without burn-in cost.
arXiv Detail & Related papers (2022-04-11T17:26:19Z) - Locally Differentially Private Reinforcement Learning for Linear Mixture
Markov Decision Processes [78.27542864367821]
Reinforcement learning (RL) algorithms can be used to provide personalized services, which rely on users' private and sensitive data.
To protect the users' privacy, privacy-preserving RL algorithms are in demand.
We propose a novel $(varepsilon, delta)$-LDP algorithm for learning a class of Markov decision processes (MDPs) dubbed linear mixture MDPs.
arXiv Detail & Related papers (2021-10-19T17:44:09Z) - Achieving Zero Constraint Violation for Constrained Reinforcement
Learning via Primal-Dual Approach [37.80609997145897]
Reinforcement learning is widely used in applications where one needs to perform sequential decisions while interacting with the environment.
The problem becomes more challenging when the decision requirement includes satisfying some safety constraints.
Various algorithms are available to solve CMDP problems in a model-free manner to achieve $epsilon$-optimal cumulative reward with $epsilon$ feasible policies.
An important question here is whether we can achieve $epsilon$-optimal cumulative reward with zero constraint violations or not.
arXiv Detail & Related papers (2021-09-13T21:27:03Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy.
For small enough $epsilon$, we show an improved algorithm with sample complexity.
arXiv Detail & Related papers (2020-06-06T13:34:41Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
This paper considers the peak Constrained Markov Decision Process (PCMDP), where the agent chooses the policy to maximize total reward in the finite horizon as well as satisfy constraints at each epoch with probability 1.
We propose a model-free algorithm that converts PCMDP problem to an unconstrained problem and a Q-learning based approach is applied.
arXiv Detail & Related papers (2020-03-11T23:23:29Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.