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

Rajarshi Roy; Anirban Majumdar; Ritam Raha; David Parker; Marta Kwiatkowska

IJCAI 20260 citations

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

Rajarshi Roy, Anirban Majumdar, Ritam Raha, David Parker, Marta Kwiatkowska

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 TRM's structure to improve 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.

Agent-based and Multi-agent Systems: Formal verification, validation and synthesisKnowledge Representation and Reasoning: Knowledge representation languagesPlanning and Scheduling: Learning in planning and scheduling

BibTeX

@inproceedings{ijcai2026_abouttimemodelfr,
  title = {About Time: Model-Free Reinforcement Learning with Timed Reward Machines},
  author = {Rajarshi Roy and Anirban Majumdar and Ritam Raha and David Parker and Marta Kwiatkowska},
  booktitle = {IJCAI 2026},
  year = {2026}
}