2015/04/20 by Reinaldo Uribe Muriel, Muriel, Reinaldo Uribe, Fernando Lozando +4
Business, Management and Accounting · Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Supply Chain and Inventory Management #cs.AI #cs.LG
paper · pdf · doi:10.48550/arxiv.1504.05122
arxiv created 2015/04/20 · openalex publication_date 2015/04/20 · arxiv updated 2015/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper describes a novel method to solve average-reward semi-Markov decision processes, by reducing them to a minimal sequence of cumulative reward problems. The usual solution methods for this type of problems update the gain (optimal average reward) immediately after observing the result of taking an action. The alternative introduced, optimal nudging, relies instead on setting the gain to some fixed value, which transitorily makes the problem a cumulative-reward task, solving it by any standard reinforcement learning method, and only then updating the gain in a way that minimizes uncertainty in a minmax sense. The rule for optimal gain update is derived by exploiting the geometric features of the w-l space, a simple mapping of the space of policies. The total number of cumulative reward tasks that need to be solved is shown to be small. Some experiments are presented to explore the features of the algorithm and to compare its performance with other approaches.