Maximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards

2019/07/03 by Falcon Z. Dai, Dai, Falcon Z., Matthew R. Walter +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Formal Methods in Verification #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1907.02114

openalex publication_date 2019/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a new complexity measure for Markov decision processes (MDPs), the maximum expected hitting cost (MEHC). This measure tightens the closely related notion of diameter [JOA10] by accounting for the reward structure. We show that this parameter replaces diameter in the upper bound on the optimal value span of an extended MDP, thus refining the associated upper bounds on the regret of several UCRL2-like algorithms. Furthermore, we show that potential-based reward shaping [NHR99] can induce equivalent reward functions with varying informativeness, as measured by MEHC. We further establish that shaping can reduce or increase MEHC by at most a factor of two in a large class of MDPs with finite MEHC and unsaturated optimal average rewards.

Citations

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Reinforcement learning in robotics: A survey

Related

• On Reward Structures of Markov Decision Processes
• Finding good policies in average-reward Markov Decision Processes without prior knowledge
• Multiplicative Rewards in Markovian Models
• Large Scale Markov Decision Processes with Changing Rewards
• Optimal Sample Complexity for Average Reward Markov Decision Processes