Model-free Reinforcement Learning For Branching Markov Decision Processes

Abstract

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyhahn2021model

Related papers

• Asymptotically Optimal Reinforcement Learning In Block Markov Decision Processes (2025)0.00
• A General Markov Decision Process Framework For Directly Learning Optimal Control Policies (2019)0.00
• Value-biased Maximum Likelihood Estimation For Model-based Reinforcement Learning In Discounted Linear Mdps (2023)0.00
• Non-stationary Markov Decision Processes, A Worst-case Approach Using Model-based Reinforcement Learning, Extended Version (2019)0.00
• Bayesian Learning Of The Optimal Action-value Function In A Markov Decision Process (2025)0.00
• Bayesian Learning Of Optimal Policies In Markov Decision Processes With Countably Infinite State-space (2023)0.00
• Model-based Exploration In Monitored Markov Decision Processes (2025)0.00
• Model-free Reinforcement Learning In Infinite-horizon Average-reward Markov Decision Processes (2019)0.00