paper-with-me

홈 › Papers

On Bellman's principle of optimality and Reinforcement learning for safety-constrained Markov decision process

2023-02-25 · Rahul Misra, Rafał Wisniewski, Carsten Skovmose Kallesøe

We study optimality for the safety-constrained Markov decision process which is the underlying framework for safe reinforcement learning. Specifically, we consider a constrained Markov decision process (with finite states and finite actions) where the goal of the decision maker is to reach a target set while avoiding an unsafe set(s) with certain probabilistic guarantees. Therefore the underlying Markov chain for any control policy will be multichain since by definition there exists a target set and an unsafe set. The decision maker also has to be optimal (with respect to a cost function) while navigating to the target set. This gives rise to a multi-objective optimization problem. We highlight the fact that Bellman's principle of optimality may not hold for constrained Markov decision problems with an underlying multichain structure (as shown by the counterexample due to Haviv. We resolve the counterexample by formulating the aforementioned multi-objective optimization problem as a zero-sum game and thereafter construct an asynchronous value iteration scheme for the Lagrangian (similar to Shapley's algorithm). Finally, we consider the reinforcement learning problem for the same and construct a modified $Q$-learning algorithm for learning the Lagrangian from data. We also provide a lower bound on the number of iterations required for learning the Lagrangian and corresponding error bounds.

📄 PDF Abstract BibTeX arXiv:2302.13152

Code (0)

등록된 구현이 없습니다.

Tasks

Q-Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)Safe Reinforcement Learning

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Similar Papers 제목 키워드 기반

CertRL: Formalizing Convergence Proofs for Value and Policy Iteration in Coq

2020-09-23 · Koundinya Vajjha, Avraham Shinnar, Vasily Pestun, Barry Trager 외

Reinforcement learning algorithms solve sequential decision-making problems in probabilistic environments by optimizing for long-term reward. The desire to use reinforcement learning in safety-critical settings inspires …

Decision Makingreinforcement-learningReinforcement LearningReinforcement Learning (RL)+1

Classical Policy Gradient: Preserving Bellman's Principle of Optimality

2019-06-06 · Philip S. Thomas, Scott M. Jordan, Yash Chandak, Chris Nota 외

We propose a new objective function for finite-horizon episodic Markov decision processes that better captures Bellman's principle of optimality, and provide an expression for the gradient of the objective.

A Unified Bellman Optimality Principle Combining Reward Maximization and Empowerment

2019-07-26 · NeurIPS 2019 12 · Felix Leibfried, Sergio Pascual-Diaz, Jordi Grau-Moya

Empowerment is an information-theoretic method that can be used to intrinsically motivate learning agents. It attempts to maximize an agent's control over the environment by encouraging visiting states with a large numbe…

MuJoCoReinforcement LearningReinforcement Learning (RL)

Budgeted Reinforcement Learning in Continuous State Space

2019-03-03 · NeurIPS 2019 12 · Nicolas Carrara, Edouard Leurent, Romain Laroche, Tanguy Urvoy 외

A Budgeted Markov Decision Process (BMDP) is an extension of a Markov Decision Process to critical applications requiring safety constraints. It relies on a notion of risk implemented in the shape of a cost signal constr…

Autonomous DrivingDeep Reinforcement Learningreinforcement-learningReinforcement Learning+1

Gradual Transition from Bellman Optimality Operator to Bellman Operator in Online Reinforcement Learning

2025-06-06 · Motoki Omura, Kazuki Ota, Takayuki Osa, Yusuke Mukuta 외

For continuous action spaces, actor-critic methods are widely used in online reinforcement learning (RL). However, unlike RL algorithms for discrete actions, which generally model the optimal value function using the Bel…

Reinforcement Learning (RL)