# Regret Bounds for Reinforcement Learning with Policy Advice

arXiv: https://arxiv.org/abs/1305.1027 · HTML: https://mlsanity.com/paper/1305.1027/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2013.

## Built on by (most cited first, 3 of 3)

- [Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations](https://mlsanity.com/paper/2106.11519/) (2021)
- [A Taxonomy of Similarity Metrics for Markov Decision Processes](https://mlsanity.com/paper/2103.04706/) (2021)
- [Learning Policy Committees for Effective Personalization in MDPs with Diverse Tasks](https://mlsanity.com/paper/2503.01885/) (2025)

## Abstract (arXiv)

In some reinforcement learning problems an agent may be provided with a set of input policies, perhaps learned from prior experience or provided by advisors. We present a reinforcement learning with policy advice (RLPA) algorithm which leverages this input set and learns to use the best policy in the set for the reinforcement learning task at hand. We prove that RLPA has a sub-linear regret of tilde O(√T) relative to the best input policy, and that both this regret and its computational complexity are independent of the size of the state and action space. Our empirical simulations support our theoretical analysis. This suggests RLPA may offer significant advantages in large domains where some prior good policies are provided.