---
title: "Increasingly Cautious Optimism for Practical PAC-MDP Exploration"
authors:
  - "Liangpeng Zhang"
  - "Ke Tang"
  - "Xin Yao"
doi: ""
url: "https://ijcai.org/proceedings/2015/566"
pdf: "https://ijcai.org/proceedings/2015/0566.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "4041-4047"
track: "Special Track on Machine Learning"
keywords:
---

# Increasingly Cautious Optimism for Practical PAC-MDP Exploration

Liangpeng Zhang, Ke Tang, Xin Yao

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 4041-4047.

## Abstract

Exploration strategy is an essential part of learning agents in model-based Reinforcement Learning. R-MAX and V-MAX are PAC-MDP strategies proved to have polynomial sample complexity; yet, their exploration behavior tend to be overly cautious in practice. We propose the principle of Increasingly Cautious Optimism (ICO) to automatically cut off unnecessarily cautious exploration, and apply ICO to R-MAX and V-MAX, yielding two new strategies, namely Increasingly Cautious R-MAX (ICR) and Increasingly Cautious V-MAX (ICV). We prove that both ICR and ICV are PACMDP, and show that their improvement is guaranteed by a tighter sample complexity upper bound. Then, we demonstrate their significantly improved performance through empirical results.