Regularization Guarantees Generalization in Bayesian Reinforcement Learning through Algorithmic Stability

Authors

  • Aviv Tamar Technion Israel Institute of Technology
  • Daniel Soudry Technion Israel Institute of Technology
  • Ev Zisselman Technion Israel Institute of Technology

DOI:

https://doi.org/10.1609/aaai.v36i8.20818

Keywords:

Machine Learning (ML), Planning, Routing, And Scheduling (PRS), Reasoning Under Uncertainty (RU)

Abstract

In the Bayesian reinforcement learning (RL) setting, a prior distribution over the unknown problem parameters -- the rewards and transitions -- is assumed, and a policy that optimizes the (posterior) expected return is sought. A common approximation, which has been recently popularized as meta-RL, is to train the agent on a sample of N problem instances from the prior, with the hope that for large enough N, good generalization behavior to an unseen test instance will be obtained. In this work, we study generalization in Bayesian RL under the probably approximately correct (PAC) framework, using the method of algorithmic stability. Our main contribution is showing that by adding regularization, the optimal policy becomes uniformly stable in an appropriate sense. Most stability results in the literature build on strong convexity of the regularized loss -- an approach that is not suitable for RL as Markov decision processes (MDPs) are not convex. Instead, building on recent results of fast convergence rates for mirror descent in regularized MDPs, we show that regularized MDPs satisfy a certain quadratic growth criterion, which is sufficient to establish stability. This result, which may be of independent interest, allows us to study the effect of regularization on generalization in the Bayesian RL setting.

Downloads

Published

2022-06-28

How to Cite

Tamar, A., Soudry, D., & Zisselman, E. (2022). Regularization Guarantees Generalization in Bayesian Reinforcement Learning through Algorithmic Stability. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8), 8423-8431. https://doi.org/10.1609/aaai.v36i8.20818

Issue

Section

AAAI Technical Track on Machine Learning III