Online learning in Markov Decision Processes with changing reward sequences

Abstract

In this paper we consider online learning in fi-nite Markov decision processes (MDPs) with changing cost sequences under full and bandit-information. We propose to view this prob-lem as an instance of online linear optimiza-tion. We propose two methods for this problem: MD2 (mirror descent with approximate projec-tions) and the continuous exponential weights al-gorithm with Dikin walks. We provide a rigorous complexity analysis of these techniques, while providing near-optimal regret-bounds (in particu-lar, we take into account the computational costs of performing approximate projections in MD2). In the case of full-information feedback, our re-sults complement existing ones. In the case of bandit-information feedback we consider the on-line stochastic shortest path problem, a special case of the above MDP problems, and man-age to improve the existing results by removing the previous restrictive assumption that the state-visitation probabilities are uniformly bounded away from zero under all policies. 1.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 42 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.