Analysis of Classification-based Policy Iteration Algorithms - Archive ouverte HAL Access content directly
Journal Articles Journal of Machine Learning Research Year : 2016

Analysis of Classification-based Policy Iteration Algorithms

(1) , (2, 1) , (3, 1)
1
2
3
Alessandro Lazaric
Mohammad Ghavamzadeh
  • Function : Author
  • PersonId : 868946
Rémi Munos
  • Function : Author
  • PersonId : 836863

Abstract

We introduce a variant of the classification-based approach to policy iteration which uses a cost-sensitive loss function weighting each classification mistake by its actual regret, that is, the difference between the action-value of the greedy action and of the action chosen by the classifier. For this algorithm, we provide a full finite-sample analysis. Our results state a performance bound in terms of the number of policy improvement steps, the number of rollouts used in each iteration, the capacity of the considered policy space (classifier), and a capacity measure which indicates how well the policy space can approximate policies that are greedy with respect to any of its members. The analysis reveals a tradeoff between the estimation and approximation errors in this classification-based policy iteration setting. Furthermore it confirms the intuition that classification-based policy iteration algorithms could be favorably compared to value-based approaches when the policies can be approximated more easily than their corresponding value functions. We also study the consistency of the algorithm when there exists a sequence of policy spaces with increasing capacity.
Fichier principal
Vignette du fichier
10-364.pdf (558.38 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01401513 , version 1 (23-11-2016)

Identifiers

  • HAL Id : hal-01401513 , version 1

Cite

Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos. Analysis of Classification-based Policy Iteration Algorithms. Journal of Machine Learning Research, 2016, 17, pp.1 - 30. ⟨hal-01401513⟩
130 View
71 Download

Share

Gmail Facebook Twitter LinkedIn More