Regret Analysis in Deterministic Reinforcement Learning
This work addresses the fundamental performance limits of learning algorithms in deterministic MDPs, which is an incremental advancement in reinforcement learning theory.
The paper tackles regret minimization in deterministic Markov Decision Processes (MDPs) by deriving logarithmic problem-specific regret lower bounds that depend on system parameters, and it numerically determines these bounds for specific classes like deterministic line search and state-dependent reward MDPs.
We consider Markov Decision Processes (MDPs) with deterministic transitions and study the problem of regret minimization, which is central to the analysis and design of optimal learning algorithms. We present logarithmic problem-specific regret lower bounds that explicitly depend on the system parameter (in contrast to previous minimax approaches) and thus, truly quantify the fundamental limit of performance achievable by any learning algorithm. Deterministic MDPs can be interpreted as graphs and analyzed in terms of their cycles, a fact which we leverage in order to identify a class of deterministic MDPs whose regret lower bound can be determined numerically. We further exemplify this result on a deterministic line search problem, and a deterministic MDP with state-dependent rewards, whose regret lower bounds we can state explicitly. These bounds share similarities with the known problem-specific bound of the multi-armed bandit problem and suggest that navigation on a deterministic MDP need not have an effect on the performance of a learning algorithm.