2022/11/03 by Nicolas Gast, Gast, Nicolas, Bruno Gaujal +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Probability (math.PR) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2211.01961
openalex publication_date 2022/11/03 · openalex created_date 2022/11/09 · openalex updated_date 2026/07/28
We propose a new policy, called the LP-update policy, to solve finite horizon weakly-coupled Markov decision processes. The latter can be seen as multi-constraint multi-action bandits, and generalize the classical restless bandit problems. Our solution is based on re-solving periodically a relaxed version of the original problem, that can be cast as a linear program (LP). When the problem is made of N statistically identical sub-components, we show that the LP-update policy becomes asymptotically optimal at rate O(T2/√(N)). This rate can be improved to O(T/√(N)) if the problem satisfies some ergodicity property and to O(1/N) if the problem is non-degenerate. The definition of non-degeneracy extends the same notion for restless bandits. By using this property, we also improve the computational efficiency of the LP-update policy. We illustrate the performance of our policy on randomly generated examples, as well as a generalized applicant screening problem, and show that it outperforms existing heuristics.