2021/06/24 by Andrea Tirinzoni, Tirinzoni, Andrea, Matteo Pirotta +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2106.13013
openalex publication_date 2021/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We derive a novel asymptotic problem-dependent lower-bound for regret minimization in finite-horizon tabular Markov Decision Processes (MDPs). While, similar to prior work (e.g., for ergodic MDPs), the lower-bound is the solution to an optimization problem, our derivation reveals the need for an additional constraint on the visitation distribution over state-action pairs that explicitly accounts for the dynamics of the MDP. We provide a characterization of our lower-bound through a series of examples illustrating how different MDPs may have significantly different complexity. 1) We first consider a "difficult" MDP instance, where the novel constraint based on the dynamics leads to a larger lower-bound (i.e., a larger regret) compared to the classical analysis. 2) We then show that our lower-bound recovers results previously derived for specific MDP instances. 3) Finally, we show that, in certain "simple" MDPs, the lower bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all. We show that this last result is attainable (up to poly(H) terms, where H is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.