Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access

• URL: http://arxiv.org/abs/2303.12718v2
• Date: Mon, 24 Apr 2023 12:23:30 GMT
• Title: Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access
• Authors: Christel Baier, Clemens Dubslaff, Patrick Wienh\"oft, Stefan J. Kiebel
• Abstract summary: In environments modeled by gray-box Markov decision processes (MDPs), the impact of the agents' actions are known in terms of successor states but not the synthesiss involved. In this paper, we devise a strategy algorithm for gray-box MDPs via reinforcement learning that utilizes interval MDPs as internal model.
• Score: 3.441021278275805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A central task in control theory, artificial intelligence, and formal methods is to synthesize reward-maximizing strategies for agents that operate in partially unknown environments. In environments modeled by gray-box Markov decision processes (MDPs), the impact of the agents' actions are known in terms of successor states but not the stochastics involved. In this paper, we devise a strategy synthesis algorithm for gray-box MDPs via reinforcement learning that utilizes interval MDPs as internal model. To compete with limited sampling access in reinforcement learning, we incorporate two novel concepts into our algorithm, focusing on rapid and successful learning rather than on stochastic guarantees and optimality: lower confidence bound exploration reinforces variants of already learned practical strategies and action scoping reduces the learning action space to promising actions. We illustrate benefits of our algorithms by means of a prototypical implementation applied on examples from the AI and formal methods communities.

Related papers

• Burning RED: Unlocking Subtask-Driven Reinforcement Learning and Risk-Awareness in Average-Reward Markov Decision Processes [7.028778922533688]
  Average-reward Markov decision processes (MDPs) provide a foundational framework for sequential decision-making under uncertainty. We study a unique structural property of average-reward MDPs and utilize it to introduce Reward-Extended Differential (or RED) reinforcement learning.
  arXiv  Detail & Related papers  (2024-10-14T14:52:23Z)
• RLIF: Interactive Imitation Learning as Reinforcement Learning [56.997263135104504]
  We show how off-policy reinforcement learning can enable improved performance under assumptions that are similar but potentially even more practical than those of interactive imitation learning. Our proposed method uses reinforcement learning with user intervention signals themselves as rewards. This relaxes the assumption that intervening experts in interactive imitation learning should be near-optimal and enables the algorithm to learn behaviors that improve over the potential suboptimal human expert.
  arXiv  Detail & Related papers  (2023-11-21T21:05:21Z)
• Context-Aware Bayesian Network Actor-Critic Methods for Cooperative Multi-Agent Reinforcement Learning [7.784991832712813]
  We introduce a Bayesian network to inaugurate correlations between agents' action selections in their joint policy. We develop practical algorithms to learn the context-aware Bayesian network policies. Empirical results on a range of MARL benchmarks show the benefits of our approach.
  arXiv  Detail & Related papers  (2023-06-02T21:22:27Z)
• Safe Multi-agent Learning via Trapping Regions [89.24858306636816]
  We apply the concept of trapping regions, known from qualitative theory of dynamical systems, to create safety sets in the joint strategy space for decentralized learning. We propose a binary partitioning algorithm for verification that candidate sets form trapping regions in systems with known learning dynamics, and a sampling algorithm for scenarios where learning dynamics are not known.
  arXiv  Detail & Related papers  (2023-02-27T14:47:52Z)
• Bayesian Soft Actor-Critic: A Directed Acyclic Strategy Graph Based Deep Reinforcement Learning [1.8220718426493654]
  This paper proposes a novel directed acyclic strategy graph decomposition approach based on Bayesian chaining. We integrate this approach into the state-of-the-art DRL method -- soft actor-critic (SAC) We build the corresponding Bayesian soft actor-critic (BSAC) model by organizing several sub-policies as a joint policy.
  arXiv  Detail & Related papers  (2022-08-11T20:36:23Z)
• A Deep Reinforcement Learning Approach to Marginalized Importance Sampling with the Successor Representation [61.740187363451746]
  Marginalized importance sampling (MIS) measures the density ratio between the state-action occupancy of a target policy and that of a sampling distribution. We bridge the gap between MIS and deep reinforcement learning by observing that the density ratio can be computed from the successor representation of the target policy. We evaluate the empirical performance of our approach on a variety of challenging Atari and MuJoCo environments.
  arXiv  Detail & Related papers  (2021-06-12T20:21:38Z)
• Model-free Representation Learning and Exploration in Low-rank MDPs [64.72023662543363]
  We present the first model-free representation learning algorithms for low rank MDPs. Key algorithmic contribution is a new minimax representation learning objective. Result can accommodate general function approximation to scale to complex environments.
  arXiv  Detail & Related papers  (2021-02-14T00:06:54Z)
• Deep RL With Information Constrained Policies: Generalization in Continuous Control [21.46148507577606]
  We show that a natural constraint on information flow might confer onto artificial agents in continuous control tasks. We implement a novel Capacity-Limited Actor-Critic (CLAC) algorithm. Our experiments show that compared to alternative approaches, CLAC offers improvements in generalization between training and modified test environments.
  arXiv  Detail & Related papers  (2020-10-09T15:42:21Z)
• SAMBA: Safe Model-Based & Active Reinforcement Learning [59.01424351231993]
  SAMBA is a framework for safe reinforcement learning that combines aspects from probabilistic modelling, information theory, and statistics. We evaluate our algorithm on a variety of safe dynamical system benchmarks involving both low and high-dimensional state representations. We provide intuition as to the effectiveness of the framework by a detailed analysis of our active metrics and safety constraints.
  arXiv  Detail & Related papers  (2020-06-12T10:40:46Z)
• Discrete Action On-Policy Learning with Action-Value Critic [72.20609919995086]
  Reinforcement learning (RL) in discrete action space is ubiquitous in real-world applications, but its complexity grows exponentially with the action-space dimension. We construct a critic to estimate action-value functions, apply it on correlated actions, and combine these critic estimated action values to control the variance of gradient estimation. These efforts result in a new discrete action on-policy RL algorithm that empirically outperforms related on-policy algorithms relying on variance control techniques.
  arXiv  Detail & Related papers  (2020-02-10T04:23:09Z)

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.