Boosting for Reinforcement Learning in Structured MDPs

Boosting is a powerful machine learning technique that constructs a strong learner by sequentially combining weak learners, each of which performs only slightly better than random. Recent work has adapted boosting to reinforcement learning and established global convergence guarantees under the assumption of access to a multiplicative weak learner. These guarantees critically depend on occupancy mismatch terms relative to the optimal policy, however the mismatch ratio between the boosted policy class and the optimal policy can become unbounded unless the policy class ensures sufficient state-space coverage. In this work, we remove this assumption and show that, whenever weak learning is feasible, boosting can achieve convergence guarantees that depend only on the intrinsic complexity of the underlying Markov Decision Process