An Optimal Online Method of Selecting Source Policies for Reinforcement Learning

Siyuan Li, Chongjie Zhang

Introduction

Reinforcement Learning (RL) agents typically learn from scratch, which is computationally expensive and time-consuming. Reusing policies from previous tasks can accelerate learning, but identifying which past policy is relevant to a new, unknown target task is challenging. Most existing methods rely on heuristics or prior knowledge, which can lead to sub-optimal performance or "negative transfer"—where the agent performs worse than if it had learned from scratch.

This paper addresses the need for a robust, automated selection mechanism. The authors propose a framework that treats a library of source policies as "arms" in a Multi-Armed Bandit (MAB) problem, allowing the agent to dynamically identify and exploit useful knowledge while maintaining the ability to explore the new environment effectively.

Proposed Methodology

The core of the proposed approach is a two-layered algorithm that separates policy selection from the learning process.

  1. Source Policy Selection ($\pi$-selection): The agent maintains a library of past policies. At the start of an episode, it uses the UCB1 (Upper Confidence Bound) algorithm to select a source policy. This selection process treats each policy as a bandit arm, balancing the exploitation of policies that have previously yielded high rewards with the exploration of less-tried policies. The probability of selecting any source policy, $p_t$, decays over time, ensuring the agent eventually transitions to standard autonomous learning.
  2. Source Policy Reuse ($\pi$-reuse): Once a policy is selected, the agent does not follow it exclusively. Instead, it combines the selected policy's actions with random exploration. This "directed exploration" guides the agent toward promising regions of the state space while allowing it to discover task-specific optimal actions.
  3. Off-Policy Q-Learning: The agent employs Q-learning to update its value functions. Because Q-learning is off-policy, it can learn the optimal target policy regardless of whether the actions were generated by a source policy, random exploration, or the current greedy policy.
Flowchart of the proposed source policy selection and reuse algorithm.

The authors provide mathematical guarantees that this selection method achieves optimal logarithmic regret and that the Q-learning process converges to the true optimal policy for the target task.

Experimental Evaluation

The method was evaluated in a Grid-Based Robot Navigation Domain, a $21 \times 24$ stochastic environment with multiple rooms and obstacles. The agent was provided with a library of four pre-trained source policies, each optimized for reaching different rooms. Target tasks were designed to vary in their similarity to these source policies, testing the algorithm's ability to identify relevant knowledge and ignore useless information.

Key Results and Insights

The experimental results highlight three major advantages of the proposed MAB-based selection method:

  • Accelerated Convergence: When a relevant source policy was available, the proposed method reached high reward levels significantly faster than both standard Q-learning and the heuristic Policy Reuse Q-Learning (PRQL) baseline.
  • Resilience to Negative Transfer: In scenarios where no source policies were relevant, the algorithm's UCB1 mechanism quickly identified the low rewards and decayed the selection probability. Consequently, the agent's performance matched standard Q-learning, successfully avoiding the performance degradation seen in other transfer methods.
  • Convergence to Global Optima: Unlike heuristic methods that might settle for sub-optimal policies when source tasks are "close enough," the proposed method's integration with off-policy learning ensures it always converges to the true optimal policy of the target task.
Comparison of average evaluation rewards over episodes for the proposed approach, PRQL, and standard Q-learning.

Conclusion and Future Directions

This paper demonstrates that framing source policy selection as a Multi-Armed Bandit problem provides a mathematically rigorous and empirically effective solution for transfer learning in RL. By leveraging UCB1 and off-policy learning, the method achieves faster training while guaranteeing convergence and safety.

Future work includes extending this approach to Deep Reinforcement Learning to handle high-dimensional state spaces. Additionally, the authors suggest exploring state-dependent policy selection, where the agent can switch between different source policies within a single episode based on its current location in the environment.

Summary updated

BibTeX
@inproceedings{li2018optimal,
  author = {Siyuan Li and Chongjie Zhang},
  title = {{An Optimal Online Method of Selecting Source Policies for Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=Sk-aVxb_-r},
}
Figure