A theoretical analysis of Model-Based Interval Estimation

Alexander L. Strehl, Michael L. Littman

Abstract

Several algorithms for learning near-optimal policies in Markov Decision Processes have been analyzed and proven efficient. Empirical results have suggested that Model-based Interval Estimation (MBIE) learns efficiently in practice, effectively balancing exploration and exploitation. This paper presents the first theoretical analysis of MBIE, proving its efficiency even under worst-case conditions. The paper also introduces a new performance metric, average loss, and relates it to its less "online" cousins from the literature.
BibTeX
@inproceedings{strehl2005theoretical,
  author = {Alexander L. Strehl and Michael L. Littman},
  title = {{A theoretical analysis of Model-Based Interval Estimation}},
  booktitle = {International Conference on Machine Learning},
  year = {2005},
  doi = {10.1145/1102351.1102459},
}

Loading related content...

Figure