Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
Mirror Decent Algorithm for a Multi-Armed Bandit Governed by a Stationary Finite State Markov Chain
Conference Name: 2013 European Control Conference (ECC)
Publisher: EUCA
Conference Location: Z?rich, Switzerland
ISBN Number: 978-3-952-41734-8

This article further develops an adaptive approach to the control of observable Markov chains with a finite number of states. We apply the Mirror Descent Randomized Control Algorithm (MDRCA) to a class of homogeneous finite Markov chains governed by the multi-armed bandit with unknown mean losses. The article develops the approach represented in [18]. As opposed to the partially observable Markov decision process an adaptive approach does not presuppose the knowledge of probabilistic characteristics of random perturbations and permits to obtain the control strategy with known rate of convergence to the optimal solution. We propose the concrete MDRCA and prove the explicit, non-asymptotic upper bound for the mean losses at a given (finite) time horizon. Numerical example illustrates theoretical results.

Авторы: Nazin Alexander , Miller, B

Дата: 16 ноября 2014

Статус: опубликована

Год: 2013

Google scholar:

Направления исследований

Primal-dual subgradient methods

Huge-scale problems

Дополнительные материалы