Maximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards
Maximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards
复制标题
DOI：
--
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Falcon Z. Dai;Matthew R. Walter
中科院分区：
文献类型：
--
作者：
Falcon Z. Dai;Matthew R. Walter
本文提出了一种新的马尔可夫决策过程复杂性测度--最大期望命中代价。这种措施通过考虑奖励结构来收紧密切相关的直径概念[JOA 10]。我们发现，这个参数取代直径的最佳值跨度的扩展MDP的上限，从而完善相关的上限上的遗憾的几个UCRL 2-like算法。此外，我们表明，基于潜力的奖励塑造[NHR 99]可以诱导具有不同信息量的等效奖励函数，如MEHC所测量的。我们进一步建立，塑造可以减少或增加MEHC最多的一个因素，在一个大类的MDP有限MEHC和不饱和的最佳平均奖励的两个。
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.