PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Inference of Reward Machines and Policies for Reinforcement Learning

Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, Bo Wu

arXiv:1909.05912v2cs.AI

TL;DR

Complex sparse-reward tasks can make RL difficult, while high-level reward-machine knowledge may be unavailable to the agent. JIRP jointly infers reward machines and policies from RL episodes, and experiments report faster convergence than the tested baselines across three scenarios.

  • Problem

    For complex tasks with sparse rewards, the high-level structure encoded by reward machines may be implicit and unknown to the learning agent.

    Source: §1 · p. 1

  • Method

    JIRP alternates q-learning with reward-machine inference, using episodes whose observed rewards conflict with the current hypothesis as counterexamples and transferring q-functions between equivalent machine states.

    Source: §1 · p. 2

  • Results

    Across three scenarios, JIRP converged to optimal policies; baselines stayed near zero for up to two million steps in autonomous vehicle and reached only 60% of optimal average cumulative reward in office world and Minecraft.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The experiments show improved RL performance from learning high-level knowledge in the form of reward machines in the tested scenarios.

    Source: §1 · p. 2, §6 · p. 10

    For exposition, the paper assumes a unique reward machine encoding the MDP’s reward function, though the algorithm also works when multiple such machines exist.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

Incorporating high-level knowledge is an effective way to expedite reinforcement learning (RL), especially for complex tasks with sparse rewards. We investigate an RL problem where the high-level knowledge is in the form of reward machines, i.e., a type of Mealy machine that encodes the reward functions. We focus on a setting in which this knowledge is a priori not available to the learning agent. We develop an iterative algorithm that performs joint inference of reward machines and policies for RL (more specifically, q-learning). In each iteration, the algorithm maintains a hypothesis reward machine and a sample of RL episodes. It derives q-functions from the current hypothesis reward machine, and performs RL to update the q-functions. While performing RL, the algorithm updates the sample by adding RL episodes along which the obtained rewards are inconsistent with the rewards based on the current hypothesis reward machine. In the next iteration, the algorithm infers a new hypothesis reward machine from the updated sample. Based on an equivalence relationship we defined between states of reward machines, we transfer the q-functions between the hypothesis reward machines in consecutive iterations. We prove that the proposed algorithm converges almost surely to an optimal policy in the limit if a minimal reward machine can be inferred and the maximal length of each RL episode is sufficiently long. The experiments show that learning high-level knowledge in the form of reward machines can lead to fast convergence to optimal policies in RL, while standard RL methods such as q-learning and hierarchical RL methods fail to converge to optimal policies after a substantial number of training steps in many tasks.

1 Introduction

The introduction motivates learning when complex, sparse-reward tasks have high-level structure that agents do not know in advance. It presents JIRP, which alternates reward-machine inference and reinforcement learning, and reports results across three scenarios.

1 Introduction

  • Complex tasks with sparse rewards can make learning challenging, and high-level knowledge may help agents explore more efficiently.Hierarchical RL is one approach, decomposing problems into subtasks with a meta-controller and controllers for actions within subtasks.Source: §1 · p. 1
  • JIRP jointly infers reward machines and policies by updating q-functions, adding reward-inconsistent episodes as counterexamples, and inferring a new machine from the updated sample.The paper proves almost-sure convergence to an optimal policy in the limit if a minimal reward machine can be inferred and episode length is sufficiently long.Source: §1 · p. 2
  • JIRP periodically batches counterexamples, transfers q-functions between equivalent machine states, and uses a polynomial-time reward-machine learning algorithm.These techniques are presented as optimizations for practical and efficient implementation.Source: §1 · p. 2
  • JIRP converged to optimal policies within 100,000 training steps in the autonomous-vehicle scenario, while baselines stayed near zero for up to two million steps; in office world and Minecraft, they reached only 60% of optimal average cumulative reward within JIRP’s convergence time.The comparisons are against q-learning in augmented state space and deep hierarchical RL.Source: §1 · p. 2

1.1 Motivating Example

  • In the motivating map, horizontal roads are priority roads and vertical roads are ordinary; the vehicle must stop once at ordinary-road intersections but not at priority-road intersections to earn the goal reward.The example assumes correct sensing of road type and forward travel except at intersections.Source: §1.1 · p. 2

2 Preliminaries

The preliminaries define labeled MDPs and reward machines as a way to represent high-level events and trajectory-dependent rewards. They then describe q-learning with reward machines and how traces support consistency checking.

2.1 Markov Decision Processes and Reward Machines

  • A labeled MDP adds propositions and transition labels for relevant high-level events, while a reward machine is a finite-state machine that maps those labels to rewards and next states.Reward machines are a special case of Mealy machines with propositions as inputs and real-valued outputs.Source: §2.1 · p. 3
  • A reward machine encodes an MDP’s reward function when it produces the reward sequence corresponding to each trajectory’s label sequence.Different machines can agree on all attainable label sequences yet differ on sequences the MDP does not permit.Source: §2.1 · p. 3

2.2 Reinforcement Learning With Reward Machines

  • QRM keeps a q-function for each reward-machine state, uses the current machine state to select actions, and updates q-functions for all machine states during each exploration step.Tabular q-learning converges in the limit when all state-action pairs are visited infinitely often for MDPs with Markovian rewards.Source: §2.2 · pp. 4–5
  • QRM ordinarily assumes rewards are known; observed rewards and collected traces instead let JIRP check an inferred machine against the environment.The traces pair label sequences with observed reward sequences.Source: §2.2 · p. 5

3 Joint Inference of Reward Machines and Policies (JIRP)

JIRP alternates reward-machine inference with QRM, using inconsistent observed traces to revise its hypothesis. Under sufficient exploration and minimal reward-machine inference, it converges almost surely to an optimal policy.

3.1 JIRP Algorithm

  • JIRP runs QRM using a hypothesis reward machine, stores traces whose rewards disagree with that hypothesis as counterexamples, and infers a new machine from the sample.The new hypothesis is required to be minimal.Source: §3.1 · p. 5

3.2 Passive Inference of Minimal Reward Machines

  • Passive inference seeks a minimal reward machine consistent with the counterexample sample; finding one is computationally hard, and SAT-based approaches do not scale to large problems.The paper notes that polynomial-time heuristics may therefore be needed.Source: §3.2 · p. 6

3.3 Convergence in the Limit

  • With episode length at least m, JIRP almost surely explores every m-attainable trajectory at least once in the limit.This exploration result supports the convergence argument based on attainable label sequences.Source: §3.3 · p. 6
  • With sufficiently long episodes, JIRP almost surely converges in the limit to an optimal policy by learning a reward machine equivalent on attainable label sequences.Learning the equivalent reward machine is the key step in the policy-convergence proof.Source: §3.3 · p. 7

4 Algorithmic Optimizations

JIRP’s optimizations batch counterexamples, transfer q-functions across equivalent reward-machine states, and use polynomial-time reward-machine inference. The first two retain the convergence guarantee under an episode-length condition, while the third does not.

4 Algorithmic Optimizations

  • Optimizations 1–2 retain convergence to an optimal policy in the limit under Theorem 2’s episode-length condition; Optimization 3 does not retain that guarantee.In the case studies, policies usually still converge to optimal policies with Optimization 3.Source: §4 · p. 7

4.1 Batching of Counterexamples

  • Algorithm 3 collects counterexamples over N episodes and updates the sample and hypothesis reward machine only when the batch is non-empty.Batching adjusts how often a new hypothesis is inferred, avoiding inference after every counterexample.Source: §4.1 · p. 7

4.2 Transfer of Q-functions

  • Equivalent reward-machine states have identical optimal q-functions, allowing JIRP to transfer those functions between consecutive hypotheses rather than reinitialize them.The equivalence requires the machines to produce the same outputs for every label sequence from those states.Source: §4.2 · p. 8

4.3 A Polynomial Time Learning Algorithm for Reward Machines

  • RPNI-RM accepts state merges only when the resulting machine remains consistent with the sample, and its runtime is polynomial in the sample’s number of symbols.The adapted RPNI algorithm addresses scalability issues of SAT-based reward-machine inference.Source: §4.3 · pp. 8–9

5 Case Studies

JIRP is evaluated against augmented-state q-learning and hierarchical RL in autonomous-vehicle, office-world, and Minecraft scenarios. Across all three, JIRP reaches optimal policies sooner than the baselines, which achieve only partial or near-zero rewards within the reported intervals.

5 Case Studies

  • The case studies compare optimized JIRP with q-learning in augmented state space and hierarchical reinforcement learning across three scenarios.Reward machines are inferred using libalf's RPNI implementation.Source: §5 · p. 9

5.1 Autonomous Vehicle Scenario

  • JIRP reaches optimal policies within 100,000 training steps; its inferred machine differs from the true machine but is equivalent on all attainable label sequences.Figure 4 shows the inferred machine from a typical final iteration.Source: §5.1 · pp. 9–10, Figure 4 · p. 10

5.2 Office World Scenario

  • JIRP converges to the optimal policy within 150,000 training steps, while QAS and HRL reach only 60% of optimal average cumulative reward within 200,000 steps.The office-world evaluation uses four tasks with different high-level relationships among subtasks.Source: §5.2 · p. 10

5.3 Minecraft World Scenario

  • JIRP converges to the optimal policy within 400,000 training steps, while QAS and HRL reach only 50% of optimal average cumulative reward within 600,000 steps.The Minecraft evaluation includes four crafting tasks: making plank, stick, bow, and bridge.Source: §5.3 · p. 10

6 Conclusion

The paper concludes that alternating reward-machine inference with RL improves RL performance. It identifies applications to other RL methods and transfer between tasks as directions for further work.

6 Conclusion

  • The proposed approach alternates reward-machine inference with reinforcement learning for the inferred machine.The paper reports improved RL performance using this approach.Source: §6 · p. 10
  • Future directions include applying the methodology to model-based RL or actor-critic methods and incrementally inferring reward machines.The authors also propose using q-function transfer between equivalent reward-machine states for transfer learning across tasks.Source: §6 · p. 10

A Proof of Lemma 1

The proof shows that when episode length is at least m, JIRP explores every m-attainable trajectory with positive probability. Consequently, every such trajectory is explored almost surely in the limit.

A Proof of Lemma 1

  • JIRP explores every m-attainable trajectory with positive probability when episode length is at least m.The proof proceeds by induction on trajectory length, starting with the initial state, which is always explored.Source: A Proof of Lemma 1 · p. 12
  • Every m-attainable trajectory is almost surely explored in the limit because its probability of remaining unexplored tends to zero as episodes accumulate.This follows from positive-probability exploration of each trajectory.Source: A Proof of Lemma 1 · pp. 12–13

B Proof of Lemma 2

The proof bounds how long an attainable sequence must be to distinguish disagreeing reward machines, then uses exploration and the growing sample to show that JIRP eventually infers a machine matching the true one on attainable sequences.

B Proof of Lemma 2

  • A reward machine can be represented by a DFA accepting label-reward sequences it produces, while an MDP can be represented by a DFA for its attainable label sequences.The reward-machine DFA adds one sink state; the MDP DFA has at most 2^|M| states.Source: B Proof of Lemma 2 · pp. 13–14
  • If two reward machines disagree on any attainable sequence, they disagree on an m-attainable sequence with m ≤ 2|M|(|A1| + |A2| + 2) − 1.The bound follows by converting disagreement into distinct product-DFA languages and using a short distinguishing word.Source: B Proof of Lemma 2 · pp. 13–14
  • Synchronizing the MDP and reward-machine DFAs represents attainable label sequences paired with their corresponding reward outputs.The product DFA has 2|M|(|A_i| + 1) states.Source: B Proof of Lemma 2 · p. 14
  • The sample grows strictly as counterexamples are added, and each hypothesis is consistent with the current sample and has size no greater than the next hypothesis.The true reward machine remains consistent with every generated sample.Source: B Proof of Lemma 2 · pp. 14–15
  • Hypotheses generated during the run are semantically distinct, so their nondecreasing sizes and the true machine's size bound imply that eventually no new hypothesis is inferred.Only finitely many reward machines have size at most the true machine's size.Source: B Proof of Lemma 2 · pp. 14–15
  • With episode length sufficient to explore the distinguishing sequence, a persistent disagreement triggers a counterexample and another hypothesis, contradicting eventual cessation; the final hypothesis therefore matches the true machine on attainable sequences.The proof relies on almost-sure exploration of the bounded witness sequence.Source: B Proof of Lemma 2 · p. 15

C Proof of Theorem 1

The proof connects a learned reward machine equivalent on attainable traces to an MDP with Markovian rewards, then applies q-learning convergence. The optimized algorithm retains the convergence argument under its stated episode-length condition.

C Proof of Theorem 1

  • An equivalent learned reward machine preserves rewards on attainable traces, so an optimal policy for its product MDP is optimal for the original problem.The product MDP has Markovian rewards matching the reward machine's non-Markovian reward function.Source: C Proof of Theorem 1 · pp. 15–16
  • With episodes meeting the stated length bound, q-learning visits every state-action pair in the product MDP infinitely often, yielding convergence to an optimal policy.The proof gives a sufficient episode-length lower bound of 2|M|+1(|A| + 1) −1.Source: C Proof of Theorem 1 · p. 16

D Proof of Theorem 2

  • With Optimizations 1 and 2 and the same episode-length condition, JIRP learns a reward machine equivalent on all attainable traces in the limit.Theorem 2 follows from this equivalence result and the analysis of Theorem 1.Source: D Proof of Theorem 2 · p. 16

E Proof of Theorem 3

The proof shows that equivalent reward-machine states remain equivalent after transitions and have matching action values. The appendix also details the autonomous-vehicle map and the office-world tasks.

E Proof of Theorem 3

  • State equivalence means matching outputs for every label sequence, and equivalent states transition to equivalent states for each input.The output function is extended to nonempty label sequences by concatenating outputs across transitions.Source: E Proof of Theorem 3 · pp. 16–17
  • Equivalent reward-machine states have equal k-horizon action values, and their values converge to the same fixed point.This establishes the basis for transferring q-functions between equivalent states.Source: E Proof of Theorem 3 · pp. 17–18

F Details in Autonomous Vehicle Scenario

G Details in Office World Scenario

  • The office-world tasks specify coffee and mail deliveries, ordered visits to the office, and repeated coffee delivery to the office and front desk.The four tasks use different high-level relationships among subtasks.Source: G Details in Office World Scenario · p. 19

G.1 Task 2.1

The office-world appendix describes four tasks and presents, for each, a final-iteration JIRP reward-machine hypothesis and cumulative-reward plots. It also lists the Minecraft task sequences.

G.1 Task 2.1

  • Task 2.1 is to get coffee at c and deliver it to office o; the appendix shows its final JIRP reward machine and cumulative-reward curves.The curves average 10 independent runs every 10 training steps.Source: Figure 8 · p. 19, §G.1 · p. 19, Figure 9 · p. 21

G.2 Task 2.2

  • Task 2.2 is to get mail at m and deliver it to office o; the appendix shows its final JIRP reward machine and cumulative-reward curves.The curves average 10 independent runs every 10 training steps.Source: §G.2 · p. 19, Figure 10 · p. 20, Figure 11 · p. 21

G.3 Task 2.3

G.4 Task 2.4

  • Task 2.4 requires two coffee deliveries, first to office o and then to front desk d; its appendix includes the final JIRP machine and reward curves.Source: Figure 14 · p. 22, Figure 15 · p. 22

H Details in Minecraft World Scenario

H.1 Task 3.1

For each Minecraft task, the appendix shows JIRP's final inferred reward machine and cumulative-reward curves averaged over independent runs.

H.1 Task 3.1

H.2 Task 3.2

H.3 Task 3.3

H.4 Task 3.4

Loading 1909.05912v2…