|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints | | Krishna C. Kalagarla
; Rahul Jain
; Pierluigi Nuzzo
; | | Date: |
23 Sep 2020 | | Abstract: | 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
$ ilde{mathcal{O}}ig(frac{|S||A|C^{2}H^{2}}{epsilon^{2}}logfrac{1}{delta}ig)$,
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$. | | Source: | arXiv, 2009.11348 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER