The Impatient May Use Limited Optimism to Minimize Regret

摘要

Discounted-sum games provide a formal model for the study of reinforcement learning, where the agent is enticed to get rewards early since later rewards are discounted. When the agent interacts with the environment, she may realize that, with hindsight, she could have increased her reward by playing differently: this difference in outcomes constitutes her regret value. The agent may thus elect to follow a regret-minimal strategy. In this paper, it is shown that (1) there always exist regret-minimal strategies that are admissible -a strategy being inadmissible if there is another strategy that always performs better; (2) computing the minimum possible regret or checking that a strategy is regret-minimal can be done in coNP~(NP), disregarding the computational cost of numerical analysis (otherwise, this bound becomes PSpace).