{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,17]],"date-time":"2026-11-17T12:17:11Z","timestamp":1794917831472,"version":"4.9.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,9]]},"abstract":"<jats:p>Reward specification plays a central role in reinforcement learning (RL), guiding the agent\u2019s 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.<\/jats:p>","DOI":"10.24963\/ijcai.2026\/36","type":"proceedings-article","created":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T22:01:13Z","timestamp":1789596073000},"page":"314-322","source":"Crossref","is-referenced-by-count":0,"title":["About Time: Model-Free Reinforcement Learning with Timed Reward Machines"],"prefix":"10.24963","author":[{"given":"Rajarshi","family":"Roy","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anirban","family":"Majumdar","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ritam","family":"Raha","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Software Systems, Kaiserslautern, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Parker","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marta","family":"Kwiatkowska","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirty-Fifth International Joint Conference on Artificial Intelligence {IJCAI-26}","theme":"Artificial Intelligence","location":"Bremen, Germany","acronym":"IJCAI-2026","number":"35","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2026,8,15]]},"end":{"date-parts":[[2026,8,21]]}},"container-title":["Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2026,11,17]],"date-time":"2026-11-17T11:27:21Z","timestamp":1794914841000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2026\/36"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2026,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2026\/36","relation":{},"subject":[],"published":{"date-parts":[[2026,9]]}}}