Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

Rodrigo Toro IcarteToryn Q. KlassenRichard Anthony ValenzanoSheila A. McIlraith

article2022JAIR354 citations2023 IJCAI-JAIR Best Paper Prize

Introduces reward machines, a finite state machine representation that exposes structured, non-Markovian reward functions to reinforcement learning agents to significantly improve sample efficiency through automated reward shaping, task decomposition, and counterfactual reasoning.

Listen

Standard reinforcement learning algorithms typically treat reward functions as opaque black boxes, requiring autonomous agents to learn purely through extensive and costly trial-and-error interaction. This design overlooks the fact that developers explicitly program these reward functions and could instead expose their underlying structural logic—such as sequential stages, conditional rules, safety constraints, and iterative loops—to accelerate learning.

The article introduces reward machines, a structured representation based on finite state automata that exposes the internal stages of reward functions, and presents several learning algorithms designed to exploit this structure. It evaluates whether these methods improve data efficiency and overall policy quality across both discrete environments and complex continuous control tasks.

To evaluate this framework, the authors conducted extensive simulated experiments comparing reward-machine-enabled methods against standard reinforcement learning baselines across discrete gridworlds, continuous 2D tracking environments, and continuous robot control benchmarks. The experimental methods included counterfactual experiences for reward machines, which generates synthetic training samples across all possible machine states from a single environmental action; hierarchical reinforcement learning for reward machines, which decomposes tasks into sub-policies corresponding to transitions between machine states; and automated potential-based reward shaping, which derives intermediate guidance rewards directly from the machine structure.

The empirical results show that methods exploiting reward structure consistently and significantly outperform standard baseline approaches. Counterfactual experiences for reward machines achieved optimal policy performance in nearly all benchmarks, demonstrating the largest performance advantages in complex, sparse-reward, and multitask settings. Hierarchical reinforcement learning learned very rapidly in initial phases and excelled in long sequential tasks, although it often converged to slightly suboptimal solutions due to localized, greedy decision-making. In continuous robot control benchmarks where the standard baseline failed to learn even after 30 million training steps, the proposed methods successfully mastered the tasks, with counterfactual reasoning achieving nine target laps per episode. However, automated reward shaping yielded mixed results, improving learning speeds in discrete domains but reducing performance in continuous settings, while both counterfactual and hierarchical approaches incurred higher computational runtime per training step.

These findings indicate that making reward structures visible resolves a major bottleneck in reinforcement learning: sample inefficiency caused by sparse feedback. Exposing reward logic lowers the physical or simulated interaction time needed to train functional policies, mitigating the high operational risks and deployment costs of real-world agent training. When choosing between these methodologies, practitioners face clear trade-offs: counterfactual reasoning is ideal when global optimality and sample efficiency are paramount, whereas hierarchical decomposition provides faster initial progress on long sequential objectives at the expense of slight suboptimality.

Organizations developing complex autonomous systems should consider representing staged or non-Markovian tasks as reward machines rather than monolithic black-box reward functions. Engineering teams can leverage standard parallel computing hardware to mitigate the additional per-step computational overhead observed during training. Because the current framework assumes deterministic and noise-free environmental event detection, future efforts should prioritize evaluating and developing methods resilient to noisy real-world sensors, learning machines directly from imperfect data, and extending these concepts to model-based reinforcement learning.

Pontificia Universidad Católica de Chile Ryerson University University of Toronto Vector Institute finite state machines linear temporal logic optimal policies reward machines reward function structure reinforcement learning

arXiv: 2010.03950 RodrigoToroIcarte/reward_machines

Paper: Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping, Andrew Y. Ng et al. (1999). This foundational paper formalizes potential-based reward shaping, establishing the theoretical guarantees of policy invariance that Reward Machines directly rely on for automated reward shaping.
Paper: Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning, Richard S. Sutton et al. (1999). This work introduces the options framework for temporal abstraction and semi-Markov decision processes, providing core conceptual foundations for decomposing tasks and learning over structured transitions as utilized by Reward Machines.
Paper: Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition, Thomas G. Dietterich (1999). This paper establishes hierarchical value function decomposition for reinforcement learning, laying groundwork for how Reward Machines decompose complex non-Markovian tasks into modular sub-problems.
Paper: Hindsight Experience Replay, Marcin Andrychowicz et al. (2017). This work develops goal-relabeling and counterfactual updates in off-policy learning, inspiring the counterfactual reasoning mechanisms used in Reward Machines to train multiple sub-policies simultaneously.
Paper: Q-learning, CHRISTOPHER J.C.H. WATKINS et al. (1992). This seminal work establishes Q-learning and off-policy value iteration, which serve as the baseline reinforcement learning mechanics augmented by Reward Machines.

Paper: Automaton-Guided Curriculum Generation for Reinforcement Learning Agents, Yash Shukla et al. (2023). This work builds directly upon formal automaton representations of temporal logic tasks to automatically synthesize structured learning curricula for reinforcement learning agents.
Paper: Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity, Abhishek Gupta et al. (2022). This paper deepens the theoretical understanding of reward engineering by analyzing the exact sample complexity reductions achieved through structured reward shaping.

Cover for Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

Abstract

Reinforcement learning (RL) methods usually treat reward functions as black boxes. As such, these methods must extensively interact with the environment in order to discover rewards and optimal policies. In most RL applications, however, users have to program the reward function and, hence, there is the opportunity to make the reward function visible – to show the reward function’s code to the RL agent so it can exploit the function’s internal structure to learn optimal policies in a more sample efficient manner. In this paper, we show how to accomplish this idea in two steps. First, we propose reward machines, a type of finite state machine that supports the specification of reward functions while exposing reward function structure. We then describe different methodologies to exploit this structure to support learning, including automated reward shaping, task decomposition, and counterfactual reasoning with off-policy learning. Experiments on tabular and continuous domains, across different tasks and RL agents, show the benefits of exploiting reward structure with respect to sample efficiency and the quality of resultant policies. Finally, by virtue of being a form of finite state machine, reward machines have the expressive power of a regular language and as such support loops, sequences and conditionals, as well as the expression of temporally extended properties typical of linear temporal logic and non-Markovian reward specification.

Topics

finite state machines linear temporal logic optimal policies reasoning regular languages reward function temporal logic reinforcement learning method average reward imitation learning

Keywords

reward machines reward function structure reinforcement learning reward shaping sparse rewards Markov decision processes subgoal automata off-policy learning deterministic policy gradient

1. Introduction
2. Reinforcement Learning
2.1 Tabular Q-Learning
2.2 Deep Q-Networks (DQN)
2.3 Deep Deterministic Policy Gradient (DDPG)
3. Reward Machines
4. Exploiting the RM Structure in Reinforcement Learning
4.1 The Cross-Product Baseline
4.2 Counterfactual Experiences for Reward Machines (CRM)
4.2.1 Q-Learning for Reward Machines (QRM)
4.3 Hierarchical Reinforcement Learning for Reward Machines (HRM)
4.4 Automated Reward Shaping (RS)
5. Experimental Evaluation
5.1 Results on Discrete Domains
5.2 Results on Continuous State Domains
5.3 Results on Continuous Control Tasks
5.4 Runtime Comparison
5.5 Code
6. Related Work
6.1 Reward Machine Research
6.1.1 Average Reward Per Step vs Normalized Discounted Return
6.2 Reward Specification
6.3 Exploiting Prior Knowledge
7. Concluding Remarks
Acknowledgments
References

Knowls

Knowl 1 — Definitions of Reward Machine and MDPRM
definition
Let $S$ be a set of environment states, $A$ a set of actions, and $\mathcal{P}$ a finite set of propositional symbols representing high-level detectable events. A reward machine (RM) is a tuple: $\mathcal{R}_{PSA} = \langle U, u_0, F, \delta_u, \delta_r \rangle$ where:
- $U$ is a finite set of internal machine states,
- $u_0 \in U$ is the initial state,
- $F$ is a finite set of terminal states disjoint from $U$ ( $U \cap F = \emptyset$ ),
- $\delta_u : U \times 2^\mathcal{P} \to U \cup F$ is the state-transition function, and
- $\delta_r : U \to [S \times A \times S \to \mathbb{R}]$ is the state-reward function that maps each state $u \in U$ to a Markovian reward function over environment transitions.
A simple reward machine is a specialized variant $\mathcal{R}_\mathcal{P} = \langle U, u_0, F, \delta_u, \delta_r \rangle$ where the reward function $\delta_r : U \times 2^\mathcal{P} \to \mathbb{R}$ outputs a scalar real reward directly from the current RM state and truth assignment rather than returning a state-dependent reward function.

A Markov Decision Process with a Reward Machine (MDPRM) combines an environment with an RM and is defined as a tuple: $\mathcal{T} = \langle S, A, p, \gamma, \mathcal{P}, L, U, u_0, F, \delta_u, \delta_r \rangle$ where $S$ is the environment state space, $A$ is the action space, $p(s_{t+1} \mid s_t, a_t)$ is the environment transition probability distribution, $\gamma \in (0, 1]$ is the discount factor, $\mathcal{P}$ is the set of propositional symbols, $L : S \times A \times S \to 2^\mathcal{P}$ is a labeling function that assigns truth values to propositions given an environment transition $(s, a, s')$ , and $\langle U, u_0, F, \delta_u, \delta_r \rangle$ constitutes the reward machine.
Knowl 2 — Equivalence Between MDPRMs and Cross-Product MDPs
theoretical result
An MDPRM can be solved by formulating an equivalent standard Markov Decision Process over the cross-product of the environment state space and the reward machine state space.

Given an MDPRM $\mathcal{T} = \langle S, A, p, \gamma, \mathcal{P}, L, U, u_0, F, \delta_u, \delta_r \rangle$ , the equivalent cross-product MDP is defined as $\mathcal{M}_\mathcal{T} = \langle S', A', r', p', \gamma' \rangle$ , where:
- $S' = S \times (U \cup F)$ ,
- $A' = A$ ,
- $\gamma' = \gamma$ ,
- The transition probability distribution $p'(\langle s', u' \rangle \mid \langle s, u \rangle, a)$ is given by: $p'(\langle s', u' \rangle \mid \langle s, u \rangle, a) = \begin{cases} p(s' \mid s, a) & \text{if } u \in F \text{ and } u' = u \\ p(s' \mid s, a) & \text{if } u \in U \text{ and } u' = \delta_u(u, L(s, a, s')) \\ 0 & \text{otherwise} \end{cases}$
- The reward function $r'(\langle s, u \rangle, a, \langle s', u' \rangle)$ is defined by: $r'(\langle s, u \rangle, a, \langle s', u' \rangle) = \begin{cases} \delta_r(u)(s, a, s') & \text{if } u \notin F \\ 0 & \text{otherwise} \end{cases}$
Any policy $\pi(a \mid \langle s, u \rangle)$ evaluated on $\mathcal{M}_\mathcal{T}$ achieves the exact same expected discounted return in $\mathcal{T}$ , and vice versa.
Knowl 3 — Counterfactual Experiences for Reward Machines (CRM)
algorithm
Counterfactual Experiences for Reward Machines (CRM) is an off-policy reinforcement learning technique for MDPRMs. When an agent executes action $a$ in environment state $s$ , transitions to $s'$ , and observes label $\sigma = L(s, a, s')$ , CRM generates synthetic experiences for all possible RM states $\bar{u} \in U$ simultaneously using the RM transition and reward functions: $\{\langle s, \bar{u}, a, \delta_r(\bar{u})(s, a, s'), s', \delta_u(\bar{u}, L(s, a, s')) \rangle \mid \forall \bar{u} \in U\}$

In tabular Q-learning, these generated experiences are used to update the cross-product Q-value function $\tilde{q}(s, u, a)$ for every $\bar{u} \in U$ .
Input: S, A, \gamma \in (0, 1], \alpha \in (0, 1], \epsilon \in (0, 1], \mathcal{P}, L, U, u_0, F, \delta_u, \delta_r
Initialize \tilde{q}(s, u, a) arbitrarily for all s \in S, u \in U, a \in A
for l = 0 to num_episodes do
    Initialize u \leftarrow u_0 and s \leftarrow EnvInitialState()
    while s is not terminal and u \notin F do
        Choose action a from (s, u) using \epsilon-greedy policy derived from \tilde{q}
        Take action a and observe next environment state s'
        experience \leftarrow {\langle s, \bar{u}, a, \delta_r(\bar{u})(s, a, s'), s', \delta_u(\bar{u}, L(s, a, s')) \rangle \mid \forall \bar{u} \in U}
        for \langle s, \bar{u}, a, \bar{r}, s', \bar{u}' \rangle \in experience do
            if s' is terminal or \bar{u}' \in F then
                \tilde{q}(s, \bar{u}, a) \leftarrow \tilde{q}(s, \bar{u}, a) + \alpha (\bar{r} - \tilde{q}(s, \bar{u}, a))
            else
                \tilde{q}(s, \bar{u}, a) \leftarrow \tilde{q}(s, \bar{u}, a) + \alpha (\bar{r} + \gamma \max_{a' \in A} \tilde{q}(s', \bar{u}', a') - \tilde{q}(s, \bar{u}, a))
        Update s \leftarrow s' and u \leftarrow \delta_u(u, L(s, a, s'))
For deep RL algorithms (such as Double DQN or DDPG), CRM adds the set of all $|U|$ counterfactual transitions into the replay buffer at each time step, and mini-batches of size proportional to $|U|$ are sampled for gradient updates.
Knowl 4 — Tabular Convergence of Q-Learning with CRM
theoretical result
Given an MDPRM $\mathcal{T} = \langle S, A, p, \gamma, \mathcal{P}, L, U, u_0, F, \delta_u, \delta_r \rangle$ , tabular Q-learning augmented with Counterfactual Experiences for Reward Machines (CRM) converges to the optimal policy $\pi^*$ for $\mathcal{T}$ in the limit, provided that every state-action pair $\langle \langle s, u \rangle, a \rangle \in (S \times U) \times A$ is visited infinitely often and the learning rate sequence satisfies standard Robbins-Monro conditions.

This convergence holds because each counterfactual transition $\langle \langle s, \bar{u} \rangle, a, \bar{r}, \langle s', \bar{u}' \rangle \rangle$ generated by CRM follows the true transition probability distribution of the cross-product MDP: $p'(\langle s', \bar{u}' \rangle \mid \langle s, \bar{u} \rangle, a) = p(s' \mid s, a)$ where $\bar{u}' = \delta_u(\bar{u}, L(s, a, s'))$ , allowing off-policy Q-learning convergence guarantees to apply directly.
Knowl 5 — Relationship Between CRM and QRM Under Function Approximation
model/method
Q-learning for Reward Machines (QRM) maintains a collection of separate Q-value functions $\tilde{q}_u(s, a)$ , one for each reward machine state $u \in U$ , updating each function using any observed transition $(s, a, s')$ via: $\tilde{q}_u(s, a) \stackrel{\alpha}{\leftarrow} \delta_r(u)(s, a, s') + \gamma \max_{a' \in A} \tilde{q}_{\delta_u(u, L(s, a, s'))}(s', a')$

In the tabular setting, QRM and Counterfactual Experiences for Reward Machines (CRM) are mathematically identical because partitioning a joint function $\tilde{q}(s, u, a)$ over $u$ yields the isolated tabular functions $\tilde{q}_u(s, a)$ .

When using deep neural network function approximation:
- QRM trains $|U|$ independent neural networks $\tilde{q}_u(s, a; \theta_u)$ , requiring custom multi-network forward/backward propagation schemes.
- CRM trains a single unified neural network $\tilde{q}(s, u, a; \theta)$ parameterized over both the environment state and the RM state. CRM integrates with standard off-policy deep RL frameworks (such as DQN and DDPG) simply by storing counterfactual tuples in a shared replay buffer.
Knowl 6 — Hierarchical Reinforcement Learning for Reward Machines (HRM)
algorithm
Hierarchical Reinforcement Learning for Reward Machines (HRM) decomposes an MDPRM into subproblems using the options framework. HRM automatically instantiates one option for each directed edge $\langle u, u_t \rangle$ in the RM, where $u_t = \delta_u(u, \sigma)$ for some $\sigma \in 2^\mathcal{P}$ .

For an option $\langle u, u_t \rangle$ , the initiation set is $I_{\langle u, u_t \rangle} = \{\langle s, u \rangle : s \in S\}$ , the deterministic termination condition is: $\beta_{\langle u, u_t \rangle}(s', u') = \begin{cases} 1 & \text{if } u' \neq u \text{ or } s' \text{ is terminal} \\ 0 & \text{otherwise} \end{cases}$ and the option policy $\pi_{u, u_t}(a \mid s)$ is trained using the internal reward function: $r_{u, u_t}(s, a, s') = \begin{cases} \delta_r(u)(s, a, s') + r^+ & \text{if } u_t \neq u \text{ and } u_t = \delta_u(u, L(s, a, s')) \\ \delta_r(u)(s, a, s') + r^- & \text{if } u_t \neq u \text{ and } u_t \neq \delta_u(u, L(s, a, s')) \\ \delta_r(u)(s, a, s') & \text{otherwise} \end{cases}$ where $r^+$ is a positive bonus for completing the transition to $u_t$ , and $r^-$ is a penalty for transitioning to an unintended state $\bar{u} \notin \{u, u_t\}$ .
Input: S, A, \gamma \in (0, 1], \alpha \in (0, 1], \epsilon \in (0, 1], \mathcal{P}, L, U, u_0, F, \delta_u, \delta_r, r^+, r^-
Define A(u) \leftarrow {u_t \mid u_t = \delta_u(u, \sigma) \text{ for some } u_t \in U \cup F, \sigma \in 2^\mathcal{P}} for all u \in U
Initialize high-level \tilde{q}(s, u, u_t) arbitrarily for all s \in S, u \in U, u_t \in A(u)
Initialize option \tilde{q}_{u, u_t}(s, a) arbitrarily for all s \in S, u \in U, u_t \in A(u), a \in A
for l = 0 to num_episodes do
    Initialize u \leftarrow u_0, s \leftarrow EnvInitialState(), u_t \leftarrow \emptyset
    while s is not terminal and u \notin F do
        if u_t = \emptyset then
            Choose option u_t \in A(u) using \epsilon-greedy policy from high-level \tilde{q}
            r_t \leftarrow 0 and k \leftarrow 0
        Choose action a from s using \epsilon-greedy policy from option \tilde{q}_{u, u_t}
        Take action a and observe next state s'
        Compute r \leftarrow \delta_r(u)(s, a, s') and next RM state u' \leftarrow \delta_u(u, L(s, a, s'))
        for \bar{u} \in U, \bar{u}_t \in A(\bar{u}) do
            if \delta_u(\bar{u}, L(s, a, s')) \neq \bar{u} or s' is terminal then
                \tilde{q}_{\bar{u}, \bar{u}_t}(s, a) \leftarrow \tilde{q}_{\bar{u}, \bar{u}_t}(s, a) + \alpha (r_{\bar{u}, \bar{u}_t}(s, a, s') - \tilde{q}_{\bar{u}, \bar{u}_t}(s, a))
            else
                \tilde{q}_{\bar{u}, \bar{u}_t}(s, a) \leftarrow \tilde{q}_{\bar{u}, \bar{u}_t}(s, a) + \alpha (r_{\bar{u}, \bar{u}_t}(s, a, s') + \gamma \max_{a' \in A} \tilde{q}_{\bar{u}, \bar{u}_t}(s', a') - \tilde{q}_{\bar{u}, \bar{u}_t}(s, a))
        if s' is terminal or u' \neq u then
            if s' is terminal or u' \in F then
                \tilde{q}(s, u, u_t) \leftarrow \tilde{q}(s, u, u_t) + \alpha (r_t + \gamma^k r - \tilde{q}(s, u, u_t))
            else
                \tilde{q}(s, u, u_t) \leftarrow \tilde{q}(s, u, u_t) + \alpha (r_t + \gamma^k r + \gamma^{k+1} \max_{u'_t \in A(u')} \tilde{q}(s', u', u'_t) - \tilde{q}(s, u, u_t))
            u_t \leftarrow \emptyset
        Update s \leftarrow s', u \leftarrow u', r_t \leftarrow r_t + \gamma^k r, k \leftarrow k + 1
Knowl 7 — Automated Potential-Based Reward Shaping for Simple Reward Machines
algorithm
Automated reward shaping derives a potential function $\Phi(s, u)$ directly from the topological structure and state rewards of a simple reward machine $\mathcal{R}_\mathcal{P} = \langle U, u_0, F, \delta_u, \delta_r \rangle$ .

An abstract deterministic MDP $\mathcal{M} = \langle S_M, A_M, r_M, p_M, \gamma_M \rangle$ is formed over the RM states, where $S_M = U \cup F$ , $A_M = 2^\mathcal{P}$ , $r_M(u, \sigma) = \delta_r(u, \sigma)$ for $u \in U$ (and 0 for $u \in F$ ), $\gamma_M < 1$ , and transitions are $p_M(\delta_u(u, \sigma) \mid u, \sigma) = 1$ .

Value iteration is executed over this abstract MDP to compute the optimal state values $v^*(u)$ :
Input: U, F, \mathcal{P}, \delta_u, \delta_r, \gamma
for u \in U \cup F do
    v(u) \leftarrow 0
e \leftarrow 1
while e > 0 do
    e \leftarrow 0
    for u \in U do
        v' \leftarrow \max_{\sigma \in 2^\mathcal{P}} [\delta_r(u, \sigma) + \gamma v(\delta_u(u, \sigma))]
        e \leftarrow \max(e, |v(u) - v'|)
        v(u) \leftarrow v'
return v
The potential function is defined as $\Phi(s, u) = -v^*(u)$ for all $s \in S, u \in U \cup F$ (with $v^*(u) = 0$ for $u \in F$ ). The shaped reward is computed during learning as: $r'(s, a, s') = r(s, a, s') + \gamma \Phi(s', u') - \Phi(s, u) = r(s, a, s') - \gamma v^*(u') + v^*(u)$ where $u' = \delta_u(u, L(s, a, s'))$ . This formulation preserves the optimal policy set while generating non-zero intermediate rewards that guide the agent toward RM task completion.
Knowl 8 — Expressive Power and Regular Language Equivalence of Reward Machines
theoretical result
Reward machines define reward functions over histories of environment state-action transitions $(S \times A)^*$ .

Given an environment with state space $S$ and action space $A$ :
1. Any standard Markovian reward function $r : S \times A \times S \to \mathbb{R}$ can be expressed by a reward machine with a single state ( $|U| = 1$ ).
2. A non-Markovian reward function $R : (S \times A)^* \to \mathbb{R}$ can be expressed by a reward machine if and only if the reward depends on the history only to the extent of distinguishing among histories described by a finite set of regular expressions over elements in $S \times A \times S$ .
3. Non-Markovian reward functions that require distinguishing histories based on non-regular properties (such as unbounded counting of state visits) cannot be expressed by a finite reward machine without external memory.
Because regular languages are exactly those recognized by deterministic finite state automata, reward machines support complex compositional structures including sequences, loops, conditionals, interleaving subtasks, and temporally extended safety constraints.
Knowl 9 — Empirical Performance of Reward Machine Learning Methods
empirical result
Empirical evaluations of CRM, HRM, and cross-product baselines across discrete gridworlds (Office World, Craft World), continuous-state domains (Water World using Double DQN), and continuous-control benchmarks (HalfCheetah-v3 using DDPG) established several core properties:
1. Superior Sample Efficiency: CRM and HRM consistently outperform standard cross-product baselines across discrete, continuous-state, and continuous-action environments.
2. Policy Optimality: CRM converges to optimal policies in tabular settings and achieves the highest asymptotic return in almost all tasks, whereas HRM often converges to suboptimal policies due to myopic sub-goal optimization.
3. Early Learning Rate: HRM frequently learns faster than CRM during initial training episodes because it learns low-level sub-policies for local RM transitions directly, but it is surpassed by CRM as training progresses.
4. Multitask Synergy: In multitask settings where the agent alternates between distinct RM tasks, the performance gap between CRM/HRM and baseline methods increases substantially because counterfactual experiences are transferred across all task machines simultaneously.
5. Reward Shaping Effectiveness: Potential-based reward shaping accelerates learning in discrete tabular domains (e.g., Office World and Craft World), but does not improve performance in continuous domains (such as Water World or HalfCheetah-v3) and degrades HRM performance across most hyperparameter choices.

Knowl 10 — Runtime and Computational Overhead of CRM and HRM

data/table

Exploiting reward machine structure introduces computational overhead relative to the standard cross-product baseline (CP). Tabular CRM computes $|U|$ Q-updates per environment step, while tabular HRM computes $|A|$ updates across all instantiated options. In deep RL, counterfactual experiences expand the replay buffer and necessitate larger training batch sizes ( $100 \times |U|$ for CRM, $100 \times |A|$ for HRM).

Domain	Setup	CP	CP+RS	HRM	HRM+RS	CRM	CRM+RS
Office World	ST	$2.5 \pm 0.1$	$3.3 \pm 0.1$	$16.1 \pm 0.5$	$17.7 \pm 0.4$	$11.9 \pm 0.3$	$12.1 \pm 0.4$
(in seconds)	MT	$2.9 \pm 0.1$	$3.7 \pm 0.1$	$38.6 \pm 0.5$	$40.6 \pm 0.7$	$32.1 \pm 0.9$	$32.3 \pm 0.9$
Craft World	ST	$0.9 \pm 0.0$	$1.1 \pm 0.0$	$8.8 \pm 0.2$	$9.4 \pm 0.4$	$6.3 \pm 0.1$	$6.4 \pm 0.3$
(in minutes)	MT	$1.3 \pm 0.0$	$1.6 \pm 0.0$	$62.4 \pm 1.5$	$64.1 \pm 2.4$	$49.2 \pm 2.5$	$50.3 \pm 2.2$
Water World	ST	$3.1 \pm 0.1$	$3.0 \pm 0.1$	$3.8 \pm 0.2$	$3.7 \pm 0.2$	$3.4 \pm 0.2$	$3.5 \pm 0.2$
(in hours)	MT	$3.1 \pm 0.2$	$3.1 \pm 0.1$	$37.1 \pm 3.0$	$36.4 \pm 2.8$	$23.4 \pm 2.8$	$21.1 \pm 0.4$
Half-Cheetah	T1	$7.7 \pm 0.1$	$6.9 \pm 0.5$	$5.2 \pm 0.2$	$4.8 \pm 0.5$	$6.4 \pm 0.2$	$6.2 \pm 0.8$
(in hours)	T2	$7.1 \pm 0.7$	$6.8 \pm 0.5$	$5.7 \pm 0.2$	$6.3 \pm 0.5$	$7.4 \pm 0.6$	$6.9 \pm 0.4$

In the table, ST denotes single-task, MT denotes multitask, and T1/T2 denote specific HalfCheetah tasks. Office and Craft domains ran on a single CPU core (Intel Xeon Gold 6148); Water and Half-Cheetah ran on a Tesla P100 GPU. Across environments, HRM exhibits the highest execution time, followed by CRM, with reward shaping (RS) adding minimal wall-clock overhead.

Knowl 11 — Methodological Limitations of Reward Machine Exploitation
limitation
The reward machine formulation and its associated exploitation algorithms have several explicit structural and practical limitations:
1. Myopic Option Suboptimality in HRM: Option policies in HRM greedily optimize transitions to target RM states as rapidly as possible without accounting for post-transition state dynamics (e.g., reaching a subgoal with high velocity when subsequent tasks require moving in the reverse direction), which often leads to convergence to globally suboptimal policies.
2. Assumption of Perfect Labeling Functions: The framework assumes deterministic and noise-free event detection via the labeling function $L(s, a, s')$ . The methodology does not handle stochastic or uncertain proposition observations.
3. Terminal State Potential Restriction in Reward Shaping: Potential-based reward shaping requires all terminal states $u \in F$ to have identical potentials (zero), preventing the method from differentiating between desirable goal states and failure terminal states (e.g., triggering safety violations).
4. Scalability of Counterfactual Generation: Generating counterfactual experiences across every state of every task in multitask or large-automaton settings scales linearly with $\sum |U_i|$ , increasing computation and memory overhead per environment step.
5. Expressiveness Ceiling: Reward machines are bounded by the expressive power of regular languages; non-regular specifications (such as unbounded state-counting dependencies) cannot be modeled without external memory.

Coverage note — None was omitted; all key definitions, baseline reductions, algorithms (CRM, QRM, HRM, Automated Reward Shaping), theoretical guarantees, empirical findings, runtime benchmarks, and stated limitations were fully captured.

References

1.Abbeel, P., & Ng, A. Y. (2004). Apprenticeship learning via inverse reinforcement learning. In Proceedings of the 21st International Conference on Machine Learning (ICML).
2.Akrour, R., Schoenauer, M., & Sebag, M. (2012). APRIL: Active preference learning-based reinforcement learning. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Vol. 7524 of Lecture Notes in Computer Science, pp. 116–131. Springer.
3.Aksaray, D., Jones, A., Kong, Z., Schwager, M., & Belta, C. (2016). Q-learning for robust satisfaction of signal temporal logic specifications. In Proceedings of the 55th IEEE Conference on on Decision and Control (CDC), pp. 6565–6570.
4.Amodei, D., Olah, C., Steinhardt, J., Christiano, P. F., Schulman, J., & Man´e, D. (2016). Concrete problems in AI safety. CoRR, abs/1606.06565.
5.Andreas, J., Klein, D., & Levine, S. (2017). Modular multitask reinforcement learning with policy sketches. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 166–175.
6.Andrychowicz, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Abbeel, O. P., & Zaremba, W. (2017). Hindsight experience replay. In Proceedings of the 30th Conference on Advances in Neural Information Processing Systems (NIPS), pp. 5048–5058.
7.Araki, B., Li, X., Vodrahalli, K., Decastro, J., Fry, M., & Rus, D. (2021). The logical options framework. In Proceedings of the 38th International Conference on Machine Learning (ICML), Vol. 139, pp. 307–317.
8.Bacchus, F., Boutilier, C., & Grove, A. J. (1996). Rewarding behaviors. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI), pp. 1160–1167.
9.Bertram, J. R., Yang, X., & Wei, P. (2018). Fast online exact solutions for deterministic MDPs with sparse rewards. CoRR, abs/1805.02785.
10.Bozkurt, A. K., Wang, Y., & Pajic, M. (2021). Learning optimal strategies for temporal tasks in stochastic games. CoRR, abs/2102.04307.
11.Bozkurt, A. K., Wang, Y., Zavlanos, M. M., & Pajic, M. (2020). Control synthesis from linear temporal logic specifications using model-free reinforcement learning. In Proceedings of the 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 10349–10355.
12.Brafman, R. I., De Giacomo, G., & Patrizi, F. (2018). LTLf/LDLf non-Markovian rewards. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 1771–1778.
13.Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., & Zaremba, W. (2016). OpenAI gym. CoRR, abs/1606.01540.
14.Cai, M., Hasanbeig, M., Xiao, S., Abate, A., & Kan, Z. (2021). Modular deep reinforcement learning for continuous motion planning with temporal logic. CoRR, abs/2102.12855.
15.Camacho, A., Chen, O., Sanner, S., & McIlraith, S. A. (2017). Non-Markovian rewards expressed in LTL: Guiding search via reward shaping. In Proceedings of the 10th Symposium on Combinatorial Search (SOCS), pp. 159–160.
16.Camacho, A., Chen, O., Sanner, S., & McIlraith, S. A. (2018). Non-Markovian rewards expressed in LTL: Guiding search via reward shaping (extended version). In 1st Workshop on Goal Specifications for Reinforcement Learning. Workshop held jointly at ICML, IJCAI, and AAMAS 2018.
17.Camacho, A., Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A. (2019). LTL and beyond: Formal languages for reward function specification in reinforcement learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 6065–6073.
18.Camacho, A., Varley, J., Jain, D., Iscen, A., & Kalashnikov, D. (2020). Disentangled planning and control in vision based robotics via reward machines. CoRR, abs/2012.14464.
19.Camacho, A., Varley, J., Zeng, A., Jain, D., Iscen, A., & Kalashnikov, D. (2021). Reward machines for vision-based robotic manipulation. In Proceedings of the 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 14284–14290.
20.Christiano, P. F., Leike, J., Brown, T. B., Martic, M., Legg, S., & Amodei, D. (2017). Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp. 4299–4307.
21.De Giacomo, G., Favorito, M., Iocchi, L., Patrizi, F., & Ronca, A. (2020). Temporal logic monitoring rewards via transducers. In Proceedings of the 17th International Conference on Knowledge Representation and Reasoning (KR), pp. 860–870.
22.De Giacomo, G., Iocchi, L., Favorito, M., & Patrizi, F. (2019). Foundations for restraining bolts: Reinforcement learning with LTLf/LDLf restraining specifications. In Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS), pp. 128–136.
23.De Giacomo, G., Iocchi, L., Favorito, M., & Patrizi, F. (2020). Restraining bolts for reinforcement learning agents.. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 13659–13662.
24.DeFazio, D., & Zhang, S. (2021). Learning quadruped locomotion policies with reward machines. CoRR, abs/2107.10969.
25.Dietterich, T. G. (2000). Hierarchical reinforcement learning with the MAXQ value function decomposition. Journal of Artificial Intelligence Research, 13, 227–303.
26.Fu, J., Luo, K., & Levine, S. (2018). Learning robust rewards with adverserial inverse reinforcement learning. In 6th International Conference on Learning Representations, ICLR 2018. OpenReview.net.
27.Furelos-Blanco, D., Law, M., Jonsson, A., Broda, K., & Russo, A. (2020a). Induction and exploitation of subgoal automata for reinforcement learning. CoRR, abs/2009.03855.
28.Furelos-Blanco, D., Law, M., Russo, A., Broda, K., & Jonsson, A. (2020b). Induction of subgoal automata for reinforcement learning.. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 3890–3897.
29.Gaon, M., & Brafman, R. (2020). Reinforcement learning with non-Markovian rewards. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 3980–3987.
30.Ghasemi, M., Bulgur, E. A., & Topcu, U. (2020). Task-oriented active perception and planning in environments with partially known semantics. In Proceedings of the 37th International Conference on Machine Learning (ICML).
31.Hadfield-Menell, D., Milli, S., Abbeel, P., Russell, S. J., & Dragan, A. D. (2017). Inverse reward design. In Proceedings of the 30th Conference on Advances in Neural Information Processing Systems (NIPS), pp. 6765–6774.
32.Hammond, L., Abate, A., Gutierrez, J., & Wooldridge, M. (2021). Multi-agent reinforcement learning with temporal logic specifications. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 583–592.
33.Hasanbeig, M., Abate, A., & Kroening, D. (2018). Logically-constrained reinforcement learning. CoRR, abs/1801.08099.
34.Hasanbeig, M., Abate, A., & Kroening, D. (2019a). Certified reinforcement learning with logic guidance. CoRR, abs/1902.00778.
35.Hasanbeig, M., Abate, A., & Kroening, D. (2019b). Logically-constrained neural fitted Q-iteration. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 2012–2014.
36.Hasanbeig, M., Abate, A., & Kroening, D. (2020). Cautious reinforcement learning with logical constraints. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 483–491.
37.Hasanbeig, M., Jeppu, N. Y., Abate, A., Melham, T., & Kroening, D. (2021). DeepSynth: Automata synthesis for automatic task segmentation in deep reinforcement learning. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 7647–7656.
38.Hasanbeig, M., Kantaros, Y., Abate, A., Kroening, D., Pappas, G. J., & Lee, I. (2019a). Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees. In Proceedings of the 58th IEEE Conference on on Decision and Control (CDC), pp. 5338–5343.
39.Hasanbeig, M., Kroening, D., & Abate, A. (2019b). Towards verifiable and safe model-free reinforcement learning. In Proceedings of the 1st Workshop on Artificial Intelligence and Formal Verification, Logic, Automata, and Synthesis (OVERLAY), pp. 1–9.
40.Hasanbeig, M., Kroening, D., & Abate, A. (2020). Deep reinforcement learning with temporal logics. In Proceedings of the 18th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS), pp. 1–22.
41.Hesse, C., Plappert, M., Radford, A., Schulman, J., Sidor, S., & Wu, Y. (2017). OpenAI baselines. https://github.com/openai/baselines.
42.Hopcroft, J. E., & Ullman, J. D. (1979). Introduction to Automata Theory, Languages and Computation. Addison-Wesley.
43.Illanes, L., Yan, X., Toro Icarte, R., & McIlraith, S. A. (2019). Symbolic planning and model-free reinforcement learning: Training taskable agents. In Proceedings of the 4th Multi-disciplinary Conference on Reinforcement Learning and Decision (RLDM), pp. 191–195.
44.Illanes, L., Yan, X., Toro Icarte, R., & McIlraith, S. A. (2020). Symbolic plans as high-level instructions for reinforcement learning. In Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS), pp. 540–550.
45.Jiang, Y., Bharadwaj, S., Wu, B., Shah, R., Topcu, U., & Stone, P. (2021). Temporal-logic-based reward shaping for continuing reinforcement learning tasks. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 7995–8003.
46.Jothimurugan, K., Alur, R., & Bastani, O. (2019). A composable specification language for reinforcement learning tasks. In Proceedings of the 32nd Conference on Advances in Neural Information Processing Systems (NeurIPS), pp. 13041–13051.
47.Karpathy, A. (2015). REINFORCEjs: WaterWorld demo. http://cs.stanford.edu/people/karpathy/reinforcejs/waterworld.html.
48.Knox, W. B., & Stone, P. (2008). Tamer: Training an agent manually via evaluative reinforcement. In Proceedings of the 7th IEEE International Conference on Development and Learning (ICDL), pp. 292–297.
49.Koroglu, Y., & Sen, A. (2019). Reinforcement learning-driven test generation for Android GUI applications using formal specifications. CoRR, abs/1911.05403.
50.Kulkarni, T. D., Narasimhan, K., Saeedi, A., & Tenenbaum, J. (2016). Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In Proceedings of the 29th Conference on Advances in Neural Information Processing Systems (NIPS), pp. 3675–3683.
51.Lacerda, B., Parker, D., & Hawes, N. (2014). Optimal and dynamic planning for Markov decision processes with co-safe LTL specifications. In Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1511–1516.
52.Lacerda, B., Parker, D., & Hawes, N. (2015). Optimal policy generation for partially satisfiable co-safe LTL specifications. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1587–1593.
53.Leon, B. G., Shanahan, M., & Belardinelli, F. (2020). Systematic generalisation through task temporal logic and deep reinforcement learning. CoRR, abs/2006.08767.
54.Li, X. (2020). A formal methods approach to interpretability, safety and composability for reinforcement learning. Ph.D. thesis, Boston University.
55.Li, X., & Belta, C. (2019). Temporal logic guided safe reinforcement learning using control barrier functions. CoRR, abs/1903.09885.
56.Li, X., Ma, Y., & Belta, C. (2018). A policy search method for temporal logic specified reinforcement learning tasks. In Proceedings of the 2018 Annual American Control Conference (ACC), pp. 240–245.
57.Li, X., Serlin, Z., Yang, G., & Belta, C. (2019). A formal methods approach to interpretable reinforcement learning for robotic planning. Science Robotics, 4 (37).
58.Li, X., Vasile, C. I., & Belta, C. (2017). Reinforcement learning with temporal logic rewards. In Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3834–3839.
59.Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., & Wierstra, D. (2016). Continuous control with deep reinforcement learning. In Bengio, Y., & LeCun, Y. (Eds.), Proceedings of the 4th International Conference on Learning Representations (ICLR).
60.Littman, M. L., Topcu, U., Fu, J., Isbell, C., Wen, M., & MacGlashan, J. (2017). Environment-independent task specifications via GLTL. CoRR, abs/1704.04341.
61.Luo, X., & Zavlanos, M. M. (2021). Temporal logic task allocation in heterogeneous multi-robot systems. CoRR, abs/2101.05694.
62.MacGlashan, J., Ho, M. K., Loftin, R. T., Peng, B., Wang, G., Roberts, D. L., Taylor, M. E., & Littman, M. L. (2017). Interactive learning from policy-dependent human feedback. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 2285–2294.
63.Mann, T. A., Mannor, S., & Precup, D. (2015). Approximate value iteration with temporally extended actions. Journal of Artificial Intelligence Research, 53, 375–438.
64.Middleton, J., Klassen, T. Q., Baier, J. A., & McIlraith, S. A. (2020). FL-AT: A formal language–automaton transmogrifier. System demonstration at The 30th International Conference on Automated Planning and Scheduling (ICAPS).
65.Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015). Human-level control through deep reinforcement learning. Nature, 518 (7540), 529–533.
66.Neary, C., Xu, Z., Wu, B., & Topcu, U. (2021). Reward machines for cooperative multi-agent reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 934–942.
67.Ng, A. Y., Harada, D., & Russell, S. J. (1999). Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the 16th International Conference on Machine Learning (ICML), pp. 278–287.
68.Ng, A. Y., & Russell, S. J. (2000). Algorithms for inverse reinforcement learning. In Proceedings of the 17th International Conference on Machine Learning (ICML), pp. 663–670.
69.Parr, R., & Russell, S. J. (1998). Reinforcement learning with hierarchies of machines. In Proceedings of the 11th Conference on Advances in Neural Information Processing Systems (NIPS), pp. 1043–1049.
70.Pitis, S., Creager, E., & Garg, A. (2020). Counterfactual data augmentation using locally factored dynamics. Proceedings of the 33rd Conference on Advances in Neural Information Processing Systems (NeurIPS), 33.
71.Post, I., & Ye, Y. (2015). The simplex method is strongly polynomial for deterministic Markov decision processes. Mathematics of Operations Research, 40 (4), 859–868.
72.Quint, E., Xu, D., Dogan, H., Hakguder, Z., Scott, S., & Dwyer, M. (2019). Formal language constraints for Markov decision processes. CoRR, abs/1910.01074.
73.Rens, G., & Raskin, J.-F. (2020). Learning non-Markovian reward models in MDPs. CoRR, abs/2001.09293.
74.Ringstrom, T. J., & Schrater, P. R. (2019). Constraint satisfaction propagation: non-stationary policy synthesis for temporal logic planning. CoRR, abs/1901.10405.
75.Shah, A., Li, S., & Shah, J. (2020). Planning with uncertain specifications (PUnS). IEEE Robotics and Automation Letters, 5 (2), 3414–3421.
76.Shah, A., & Shah, J. (2020). Interactive robot training for non-Markov tasks. CoRR, abs/2003.02232.
77.Sidor, S. (2016). Reinforcement learning with natural language signals. Ph.D. thesis, Massachusetts Institute of Technology.
78.Singh, S. (1992a). Reinforcement learning with a hierarchy of abstract models. In Proceedings of the 10th National Conference on Artificial Intelligence (AAAI), pp. 202–207.
79.Singh, S. (1992b). Transfer of learning by composing solutions of elemental sequential tasks. Machine Learning, 8 (3-4), 323–339.
80.Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning - an introduction. Adaptive computation and machine learning. MIT Press.
81.Sutton, R. S., Precup, D., & Singh, S. (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112 (1-2), 181–211.
82.Thomaz, A. L., Hoffman, G., & Breazeal, C. (2006). Reinforcement learning with human teachers: Understanding how people want to teach robots. In Proceedings of the 15th IEEE International Symposium on Robot and Human Interactive Communication (ROMAN), pp. 352–357.
83.Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A. (2017). Using advice in model-based reinforcement learning. In Proceedings of the 3rd Multi-disciplinary Conference on Reinforcement Learning and Decision (RLDM), pp. 199–203.
84.Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A. (2018a). Advice-based exploration in model-based reinforcement learning. In Proceedings of the 31st Canadian Conference on Artificial Intelligence (Canadian AI), pp. 72–83.
85.Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A. (2018b). Teaching multiple tasks to an RL agent using LTL. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 452–461.
86.Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A. (2018c). Using reward machines for high-level task specification and decomposition in reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 2112–2121.
87.Toro Icarte, R., Waldie, E., Klassen, T. Q., Valenzano, R., Castro, M. P., & McIlraith, S. A. (2021). Learning reward machines: A study in partially observable reinforcement learning. CoRR, abs/2112.09477.
88.Toro Icarte, R., Waldie, E., Klassen, T. Q., Valenzano, R., Castro, M. P., & McIlraith, S. A. (2019a). Learning reward machines for partially observable reinforcement learning. In Proceedings of the 32nd Conference on Advances in Neural Information Processing Systems (NeurIPS), pp. 15497–15508.
89.Toro Icarte, R., Waldie, E., Klassen, T. Q., Valenzano, R., Castro, M. P., & McIlraith, S. A. (2019b). Searching for Markovian subproblems to address partially observable reinforcement learning. In Proceedings of the 4th Multi-disciplinary Conference on Reinforcement Learning and Decision (RLDM), pp. 22–26.
90.Vaezipoor, P., Li, A., Toro Icarte, R., & McIlraith, S. (2021). LTL2Action: Generalizing LTL instructions for multi-task RL. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 10497–10508.
91.Van Hasselt, H., Guez, A., & Silver, D. (2016). Deep reinforcement learning with Double Q-learning. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 2094–2100.
92.Velasquez, A., Beckus, A., Dohmen, T., Trivedi, A., Topper, N., & Atia, G. (2021). Learning probabilistic reward machines from non-Markovian stochastic reward processes. CoRR, abs/2107.04633.
93.Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine learning, 8 (3-4), 279–292.
94.Xu, Z., Gavran, I., Ahmad, Y., Majumdar, R., Neider, D., Topcu, U., & Wu, B. (2020a). Joint inference of reward machines and policies for reinforcement learning. In Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS), Vol. 30, pp. 590–598.
95.Xu, Z., Wu, B., Neider, D., & Topcu, U. (2020b). Active finite reward automaton inference and reinforcement learning using queries and counterexamples. CoRR, abs/2006.15714.
96.Yuan, L. Z., Hasanbeig, M., Abate, A., & Kroening, D. (2019). Modular deep reinforcement learning with temporal logic specifications. CoRR, abs/1909.11591.
97.Zheng, X., Yu, C., Chen, C., Hao, J., & Zhuo, H. H. (2021). Lifelong reinforcement learning with temporal logic formulas and reward machines. CoRR, abs/2111.09475.
98.Ziebart, B. D., Maas, A. L., Bagnell, J. A., & Dey, A. K. (2008). Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI), pp. 1433–1438.

Citation

MLA

Toro Icarte, R., et al. “Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning”. Journal of Artificial Intelligence Research, vol. 73, 2022, pp. 173–208, https://doi.org/10.1613/jair.1.12440.

APA

Toro Icarte, R., Klassen, T. Q., Valenzano, R., & McIlraith, S. A. (2022). Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research, 73, 173–208. https://doi.org/10.1613/jair.1.12440

Chicago

Toro Icarte, R., T. Q. Klassen, R. Valenzano, and S. A. McIlraith. 2022. “Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning”. Journal of Artificial Intelligence Research 73: 173–208. https://doi.org/10.1613/jair.1.12440.

Harvard

Toro Icarte, R. et al. (2022) “Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning”, Journal of Artificial Intelligence Research, 73, pp. 173–208. Available at: https://doi.org/10.1613/jair.1.12440.

Vancouver

1. Toro Icarte R, Klassen TQ, Valenzano R, McIlraith SA (2022) Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning. Journal of Artificial Intelligence Research 73:173–208

BibTeX

@article{Toro_Icarte_2022, title={Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning}, volume={73}, ISSN={1076-9757}, url={http://dx.doi.org/10.1613/jair.1.12440}, DOI={10.1613/jair.1.12440}, journal={Journal of Artificial Intelligence Research}, publisher={AI Access Foundation}, author={Toro Icarte, Rodrigo and Klassen, Toryn Q. and Valenzano, Richard and McIlraith, Sheila A.}, year={2022}, month=Jan, pages={173–208} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Definitions of Reward Machine and MDPRM

Knowl 2 — Equivalence Between MDPRMs and Cross-Product MDPs

Knowl 3 — Counterfactual Experiences for Reward Machines (CRM)

Knowl 4 — Tabular Convergence of Q-Learning with CRM

Knowl 5 — Relationship Between CRM and QRM Under Function Approximation

Knowl 6 — Hierarchical Reinforcement Learning for Reward Machines (HRM)

Knowl 7 — Automated Potential-Based Reward Shaping for Simple Reward Machines

Knowl 8 — Expressive Power and Regular Language Equivalence of Reward Machines