Online Regret Bounds for Satisficing in Markov Decision Processes
研究了平均奖励准则下马尔可夫决策过程中的一般强化学习，当学习者的目标不是学习最优策略，而是接受任何平均奖励高于给定满意水平的策略时，给出了具有常数遗憾的算法。
We consider general reinforcement learning under the average reward criterion in Markov decision processes (MDPs), when the learner’s goal is not to learn an optimal policy, but accepts any policy whose average reward is above a given satisfaction level [Formula: see text]. We show that with this more modest objective, it is possible to give algorithms that only have constant regret with respect to the level [Formula: see text], provided that there is a policy above this level. This is a generalization of known results from the bandit setting to MDPs. Further, we present a more general algorithm that achieves the best of both worlds: If the optimal policy has average reward above [Formula: see text], this algorithm has bounded regret with respect to [Formula: see text]. On the other hand, if all policies are below [Formula: see text], then the expected regret with respect to the optimal policy is bounded as for the UCRL2 algorithm. Funding: Financial support from the Austrian Science Fund (FWF) [Grant TAI 590-N] is gratefully acknowledged.