Model-free Reinforcement Learning for Branching Markov Decision Processes

2021-06-12 · Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, Dominik Wojtczak

We study reinforcement learning for the optimal control of Branching Markov Decision Processes (BMDPs), a natural extension of (multitype) Branching Markov Chains (BMCs). The state of a (discrete-time) BMCs is a collection of entities of various types that, while spawning other entities, generate a payoff. In comparison with BMCs, where the evolution of a each entity of the same type follows the same probabilistic pattern, BMDPs allow an external controller to pick from a range of options. This permits us to study the best/worst behaviour of the system. We generalise model-free reinforcement learning techniques to compute an optimal control strategy of an unknown BMDP in the limit. We present results of an implementation that demonstrate the practicality of the approach.

📄 PDF Abstract BibTeX arXiv:2106.06777

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

A Markov Decision Process for Variable Selection in Branch & Bound

2025-10-22 · Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan 외 arxiv

Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and Bound (B&B). A key factor influencing the performanc…

Reinforcement Learning

Learning to branch with Tree MDPs

2022-05-23 · Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse 외

State-of-the-art Mixed Integer Linear Program (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as the branching rule. The idea of learning branching rules from data has receive…

Reinforcement Learning (RL)

Regular Decision Processes for Grid Worlds

2021-11-05 · Nicky Lenaers, Martijn van Otterlo

Markov decision processes are typically used for sequential decision making under uncertainty. For many aspects however, ranging from constrained or safe specifications to various kinds of temporal (non-Markovian) depend…

Decision Making Decision Making Under Uncertainty Incremental Learning Sequential Decision Making

Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes

2019-10-15 · ICML 2020 1 · Chen-Yu Wei, Mehdi Jafarnia-Jahromi, Haipeng Luo, Hiteshi Sharma 외

Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Model-Free Reinforcement Learning for Optimal Control of MarkovDecision Processes Under Signal Temporal Logic Specifications

2021-09-27 · Krishna C. Kalagarla, Rahul Jain, Pierluigi Nuzzo

We present a model-free reinforcement learning algorithm to find an optimal policy for a finite-horizon Markov decision process while guaranteeing a desired lower bound on the probability of satisfying a signal temporal …

Motion Planning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)