# On Reward Structures of Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 61 references that are in the map.
- First posted on arXiv 28 Aug 2023.

## Builds on (most cited first, 10 of 10)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Towards Near-imperceptible Steganographic Text](https://mlsanity.com/paper/1907.06679/) (2019)
- [Improved Analysis of UCRL2 with Empirical Bernstein Inequality](https://mlsanity.com/paper/2007.05456/) (2020)
- [Glyph-aware Embedding of Chinese Characters](https://mlsanity.com/paper/1709.00028/) (2017)
- [Maximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards](https://mlsanity.com/paper/1907.02114/) (2019)
- [Renewal Monte Carlo: Renewal theory based reinforcement learning](https://mlsanity.com/paper/1804.01116/) (2018)
- [Instance-dependent ℓ_∞-bounds for policy evaluation in tabular reinforcement learning](https://mlsanity.com/paper/1909.08749/) (2019)
- [Loop Estimator for Discounted Values in Markov Reward Processes](https://mlsanity.com/paper/2002.06299/) (2020)

## Abstract (arXiv)

A Markov decision process can be parameterized by a transition kernel and a reward function. Both play essential roles in the study of reinforcement learning as evidenced by their presence in the Bellman equations. In our inquiry of various kinds of "costs" associated with reinforcement learning inspired by the demands in robotic applications, rewards are central to understanding the structure of a Markov decision process and reward-centric notions can elucidate important concepts in reinforcement learning. Specifically, we study the sample complexity of policy evaluation and develop a novel estimator with an instance-specific error bound of tildeO(√fracτsn) for estimating a single state value. Under the online regret minimization setting, we refine the transition-based MDP constant, diameter, into a reward-based constant, maximum expected hitting cost, and with it, provide a theoretical explanation for how a well-known technique, potential-based reward shaping, could accelerate learning with expert knowledge. In an attempt to study safe reinforcement learning, we model hazardous environments with irrecoverability and proposed a quantitative notion of safe learning via reset efficiency. In this setting, we modify a classic algorithm to account for resets achieving promising preliminary numerical results. Lastly, for MDPs with multiple reward functions, we develop a planning algorithm that computationally efficiently finds Pareto-optimal stochastic policies.