Learning Probabilistic Reward Machines from Non-Markovian Stochastic Reward Processes

• URL: http://arxiv.org/abs/2107.04633v1
• Date: Fri, 9 Jul 2021 19:00:39 GMT
• Title: Learning Probabilistic Reward Machines from Non-Markovian Stochastic Reward Processes
• Authors: Alvaro Velasquez, Andre Beckus, Taylor Dohmen, Ashutosh Trivedi, Noah Topper, George Atia
• Abstract summary: We introduce probabilistic reward machines (PRMs) as a representation of non-Markovian rewards. We present an algorithm to learn PRMs from the underlying decision process as well as to learn the PRM representation of a given decision-making policy.
• Score: 8.800797834097764
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The success of reinforcement learning in typical settings is, in part, predicated on underlying Markovian assumptions on the reward signal by which an agent learns optimal policies. In recent years, the use of reward machines has relaxed this assumption by enabling a structured representation of non-Markovian rewards. In particular, such representations can be used to augment the state space of the underlying decision process, thereby facilitating non-Markovian reinforcement learning. However, these reward machines cannot capture the semantics of stochastic reward signals. In this paper, we make progress on this front by introducing probabilistic reward machines (PRMs) as a representation of non-Markovian stochastic rewards. We present an algorithm to learn PRMs from the underlying decision process as well as to learn the PRM representation of a given decision-making policy.

Related papers

• Maximally Permissive Reward Machines [8.425937972214667]
  We propose a new approach to synthesising reward machines based on the set of partial order plans for a goal. We prove that learning using such "maximally permissive" reward machines results in higher rewards than learning using RMs based on a single plan.
  arXiv  Detail & Related papers  (2024-08-15T09:59:26Z)
• Walking the Values in Bayesian Inverse Reinforcement Learning [66.68997022043075]
  Key challenge in Bayesian IRL is bridging the computational gap between the hypothesis space of possible rewards and the likelihood. We propose ValueWalk - a new Markov chain Monte Carlo method based on this insight.
  arXiv  Detail & Related papers  (2024-07-15T17:59:52Z)
• Dense Reward for Free in Reinforcement Learning from Human Feedback [64.92448888346125]
  We leverage the fact that the reward model contains more information than just its scalar output. We use these attention weights to redistribute the reward along the whole completion. Empirically, we show that it stabilises training, accelerates the rate of learning, and, in practical cases, may lead to better local optima.
  arXiv  Detail & Related papers  (2024-02-01T17:10:35Z)
• Let's reward step by step: Step-Level reward model as the Navigators for Reasoning [64.27898739929734]
  Process-Supervised Reward Model (PRM) furnishes LLMs with step-by-step feedback during the training phase. We propose a greedy search algorithm that employs the step-level feedback from PRM to optimize the reasoning pathways explored by LLMs. To explore the versatility of our approach, we develop a novel method to automatically generate step-level reward dataset for coding tasks and observed similar improved performance in the code generation tasks.
  arXiv  Detail & Related papers  (2023-10-16T05:21:50Z)
• On Reward Structures of Markov Decision Processes [4.13365552362244]
  A Markov decision process can be parameterized by a transition kernel and a reward function. We study various kinds of "costs" associated with reinforcement learning inspired by the demands in robotic applications. We develop a novel estimator with an instance-specific error bound to $tildeO(sqrtfractau_sn)$ for estimating a single state value.
  arXiv  Detail & Related papers  (2023-08-28T22:29:16Z)
• Distributional Reward Estimation for Effective Multi-Agent Deep Reinforcement Learning [19.788336796981685]
  We propose a novel Distributional Reward Estimation framework for effective Multi-Agent Reinforcement Learning (DRE-MARL) Our main idea is to design the multi-action-branch reward estimation and policy-weighted reward aggregation for stabilized training. The superiority of the DRE-MARL is demonstrated using benchmark multi-agent scenarios, compared with the SOTA baselines in terms of both effectiveness and robustness.
  arXiv  Detail & Related papers  (2022-10-14T08:31:45Z)
• Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes [90.53326983143644]
  We show that Markov abstractions can be learned during reinforcement learning. We show that our approach has PAC guarantees when the employed algorithms have PAC guarantees.
  arXiv  Detail & Related papers  (2022-04-29T16:53:00Z)
• Reinforcement Learning in Reward-Mixing MDPs [74.41782017817808]
  episodic reinforcement learning in a reward-mixing Markov decision process (MDP) cdot S2 A2)$ episodes, where $H$ is time-horizon and $S, A$ are the number of states and actions respectively. epsilon$-optimal policy after exploring $tildeO(poly(H,epsilon-1) cdot S2 A2)$ episodes, where $H$ is time-horizon and $S, A$ are the number of states and actions respectively.
  arXiv  Detail & Related papers  (2021-10-07T18:55:49Z)
• Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
  We derive a novel policy gradient-style robust optimization approach, PG-BROIL, to balance expected performance and risk. Results suggest PG-BROIL can produce a family of behaviors ranging from risk-neutral to risk-averse.
  arXiv  Detail & Related papers  (2021-06-11T16:49:15Z)
• Online Learning of Non-Markovian Reward Models [2.064612766965483]
  We consider a non-Markovian reward decision process (MDP) that models the dynamics of the environment in which the agent evolves. While the MDP is known by the agent, the reward function is unknown to the agent and must be learned. We use Angluin's $L*$ active learning algorithm to learn a Mealy machine representing the underlying non-Markovian reward machine.
  arXiv  Detail & Related papers  (2020-09-26T13:54:34Z)
• Learning Non-Markovian Reward Models in MDPs [0.0]
  We show how to formalise the non-Markovian reward function using a Mealy machine. In our formal setting, we consider a Markov decision process (MDP) that models the dynamic of the environment in which the agent evolves. While the MDP is known by the agent, the reward function is unknown from the agent and must be learnt.
  arXiv  Detail & Related papers  (2020-01-25T10:51:42Z)

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.