2019/09/13 by Marianne Akian, Akian, Marianne, Stéphane Gaubert +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1909.06185
openalex publication_date 2019/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently, Sidford, Wang, Wu and Ye (2018) developed an algorithm combining\nvariance reduction techniques with value iteration to solve discounted Markov\ndecision processes. This algorithm has a sublinear complexity when the discount\nfactor is fixed. Here, we extend this approach to mean-payoff problems,\nincluding both Markov decision processes and perfect information zero-sum\nstochastic games. We obtain sublinear complexity bounds, assuming there is a\ndistinguished state which is accessible from all initial states and for all\npolicies. Our method is based on a reduction from the mean payoff problem to\nthe discounted problem by a Doob h-transform, combined with a deflation\ntechnique. The complexity analysis of this algorithm uses at the same time the\ntechniques developed by Sidford et al. in the discounted case and non-linear\nspectral theory techniques (Collatz-Wielandt characterization of the\neigenvalue).\n