About Time: Model-free Reinforcement Learning with Timed Reward Machines

AI summary

Overview

Research area: Reinforcement learning (RL) with formal, non-Markovian reward specification, specifically extending reward machines with timing constraints drawn from timed automata theory.

Technical level: Advanced. The paper assumes familiarity with MDPs, Q-learning, automata theory, timed automata, clock valuations, and discounting with sojourn times.

Scope: The paper defines timed reward machines (TRMs), develops model-free tabular Q-learning algorithms for digital-clock and real-time interpretations of TRMs, and evaluates them with counterfactual-imagining heuristics on standard RL benchmarks.

What This Paper Is About

Standard reward machines can express history-dependent objectives but cannot express how long things take or when they must happen. This paper introduces timed reward machines, which add clocks and timing guards so that rewards and costs can depend on delays between events, deadlines, and dwell times. The goal is to learn optimal policies in a model-free RL setting under two interpretations of time: digital-clock (integer) and real-time (continuous), covering both a discretized-time approach and a corner-point abstraction.

Key Contributions

1. The timed reward machine (TRM) formalism. A finite-state machine with clocks, guards, clock resets, terminal states, and both state-based and transition-based reward functions. Rewards can be negative (costs) and can be assigned to delay behavior, giving designers tunable reward logic — for example, costs for delaying and rewards for timely actions. The formalism is inspired by priced timed automata but generalized for RL.

2. Model-free RL algorithms over product MDPs. The authors augment the MDP action space with explicit delay actions, giving actions of the form (delay, action), and construct a cross-product MDP that tracks the MDP state, the TRM state, and bounded clock valuations. Tabular Q-learning is then applied on this product, with the discount applied to the elapsed delay rather than to a single unit step.

3. Two timing semantics plus a corner-point abstraction. The digital-clock setting uses clock values in the natural numbers and integer delays; the real-time setting uses non-negative real clocks and continuous delays in [0, M], handled either by discretization or by a corner-point abstraction based on timed automata region construction, which encourages delays close to integers.

4. Counterfactual imagining (CI) for delays, plus theory. The learning update is enriched with synthesized alternative experiences that vary the TRM state, the clock valuation (within a fixed radius, typically less than 5), and the delay (chosen so that guards are satisfied). The paper also proves that an optimal positional deterministic delay-discounted policy exists for the product MDP, that Q-learning on it converges under standard assumptions, and provides delay-bounding lemmas.

Main Findings

• Timing constraints change achievable returns. A running example shows a TRM enforcing slow driving (a self-loop with guard x > 1) and a pickup deadline (guard y ≤ 14) on the Gym Taxi domain, and the paper reports that TRM-based algorithms can obtain higher rewards than standard reward machines without delay actions.

• Digital and real-time semantics can differ qualitatively. In Example 3, a real-time policy achieves a discounted reward of approximately 11.13 with γ = 0.9, while the paper states there is no positive-valued policy in the digital-clock setting; corresponding digital trajectories achieve approximately −3.7.

• Real-time can yield higher returns on the same trajectories. In Table 1's example with γ = 0.9, the same delay choices give approximately 6.4 (digital) and 6.6 (real-time) for one trajectory, and approximately 5.1 (digital) and 5.4 (real-time) for another, preserving the ordering between trajectories.

• Delay bounding is safe and can be beneficial. Lemma 1 shows that delaying beyond the maximum guard constant M is equivalent to delaying exactly M for the TRM run. Lemma 2 shows that under negative state rewards and positive returns at every decision point, bounding delays yields a discounted return at least as high as the unbounded trajectory.

• Corner-point abstraction helps with large delays. The paper reports that in scenarios requiring substantial delays, the corner-point abstraction often yields better returns than the alternative real-time treatment.

• Counterfactual imagining helps consistently. The paper reports that CI heuristics consistently produce higher returns across the experiments.

• Benchmark details are not reported in the available content. The paper states that several TRMs are interpreted over standard RL benchmarks, but the truncated content does not name the benchmarks, episode counts, or numerical tables from the experimental section.

Methodology in Plain English

The researchers start from an MDP that describes the stochastic environment, then add a delay to the action space so the agent can choose to wait before acting. A timed reward machine runs alongside the environment: it has states, clocks, and transition rules guarded by clock comparisons. When the agent takes a delay-action pair, the clocks advance by the delay plus one unit (the one-unit offset represents the action's execution time), and the machine checks which guard is satisfied by the new clock values. Clocks that exceed the largest constant used in any guard are collapsed to a special "infinity" value, which keeps the state space finite.

To learn, the agent builds a product of the environment state, the machine state, and the bounded clock valuation, and runs tabular Q-learning on it. The discount is applied to the delay, so waiting costs more in discounted terms. For real-time delays, one option is to discretize time; the other is a corner-point abstraction that restricts attention to delay choices near integer or region boundaries. On top of the base learner, counterfactual imagining generates extra training updates by pretending the agent had been in a nearby TRM state, a nearby clock valuation, or had chosen a delay that satisfies an available guard, rather than only learning from what actually happened.

Why This Matters

Research impact. The paper connects timed automata theory, which is traditionally used in model-based verification and synthesis, to model-free RL. It extends the reward machine line of work — which has already been extended to stochastic transitions, ω-regular properties, partial observability, multi-agent settings, and continuous-time MDPs — into the domain of fine-grained timing constraints, which the authors state is not addressed by any of those prior extensions. It also contrasts with prior RL work on timed specifications, which translates Metric Temporal Logic or Duration Calculus into timed automata used only as binary satisfaction monitors, and which the authors note covers only the digital-clock setting.

Real-world applications cited or implied by the paper:

• Autonomous driving, with examples such as slowing down for 3 seconds to let a pedestrian cross, or avoiding an unsafe road for at least 10 seconds.
• Taxi-style navigation tasks with deadlines and traffic-dependent driving behavior, illustrated by the paper's running Gym Taxi example.
• Robotics, which the paper lists alongside autonomous driving as a domain where time-sensitive requirements are vital.
• Any control setting where doing a task too slowly or too quickly should change the payoff rather than just determine whether the task succeeds.

Industry relevance. Safety-critical and time-sensitive systems need reward specifications that can express deadlines and dwell-time requirements while still being learned from interaction rather than from a hand-built model. The tunable reward logic of TRMs — state-based costs, transition-based rewards, and delay-dependent terms — gives designers a more expressive and interpretable interface than pass/fail timed monitors.

Future Directions

• Scaling beyond tabular Q-learning. All algorithms presented are tabular; the product space multiplies the environment state, machine state, and clock valuations, so extending to function approximation or deep RL is an open question the paper does not resolve in the available content.
• A sharper characterization of digital versus real-time. The paper shows a case where only the real-time setting admits a positive-valued policy, and reports that corner-point abstraction often wins when large delays are needed; a fuller account of when each semantics or abstraction is preferable would be a natural next step.
• Tuning and bounding the counterfactual-imagining search. The radius r_crm (typically less than 5) and the selection of alternative delays are heuristic choices; understanding the trade-off between coverage and computational cost remains open.
• Formal comparison with other timed-specification RL methods. The paper states that a more detailed technical comparison with related work appears in its Section 7, which is outside the truncated content, and positions TRMs against MTL- and Duration-Calculus-based approaches.

Target Audience

Researchers and graduate students working at the intersection of reinforcement learning and formal methods, particularly those interested in reward machines, temporal logic specifications, timed automata, and safe or time-constrained sequential decision-making. Practitioners designing reward structures for robotics, autonomous driving, or other time-sensitive control problems would also benefit, provided they are comfortable with automata-theoretic notation and discounted-return definitions over sojourn times.

Authors’ abstract

Reward specification plays a central role in reinforcement learning (RL), guiding the agent's behavior. To express non-Markovian rewards, formalisms such as reward machines have been introduced to capture dependencies on histories. However, traditional reward machines lack the ability to model precise timing constraints, limiting their use in time-sensitive applications. In this paper, we propose timed reward machines (TRMs), which are an extension of reward machines that incorporate timing constraints into the reward structure. TRMs enable more expressive specifications with tunable reward logic, for example, imposing costs for delays and granting rewards for timely actions. We study model-free RL frameworks (i.e., tabular Q-learning) for learning optimal policies with TRMs under digital and real-time semantics. Our algorithms integrate the TRM into learning via abstractions of timed automata, and employ counterfactual-imagining heuristics that exploit the structure of the TRM to improve the search. Experimentally, we demonstrate that our algorithm learns policies that achieve high rewards while satisfying the timing constraints specified by the TRM on popular RL benchmarks. Moreover, we conduct comparative studies of performance under different TRM semantics, along with ablations that highlight the benefits of counterfactual-imagining.