# Reward Shaping for Reinforcement Learning with Omega-Regular Objectives

arXiv: https://arxiv.org/abs/2001.05977 · HTML: https://mlsanity.com/paper/2001.05977/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2020.

## Built on by (most cited first, 4 of 4)

- [Multi-Agent Reinforcement Learning with Temporal Logic Specifications](https://mlsanity.com/paper/2102.00582/) (2021)
- [Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives](https://mlsanity.com/paper/2202.02404/) (2022)
- [COOL-MC: Verifying and Explaining RL Policies for Platelet Inventory Management](https://mlsanity.com/paper/2603.02396/) (2026)
- [COOL-MC: Verifying and Explaining RL Policies for Multi-bridge Network Maintenance](https://mlsanity.com/paper/2603.07546/) (2026)

## Abstract (arXiv)

Recently, successful approaches have been made to exploit good-for-MDPs automata (B"uchi automata with a restricted form of nondeterminism) for model free reinforcement learning, a class of automata that subsumes good for games automata and the most widespread class of limit deterministic automata. The foundation of using these B"uchi automata is that the B"uchi condition can, for good-for-MDP automata, be translated to reachability. The drawback of this translation is that the rewards are, on average, reaped very late, which requires long episodes during the learning process. We devise a new reward shaping approach that overcomes this issue. We show that the resulting model is equivalent to a discounted payoff objective with a biased discount that simplifies and improves on prior work in this direction.