On the bottleneck concept for options discovery: theoretical underpinnings and extension in continuous state spaces
Pierre‐Luc Bacon · eScholarship@McGill (McGill) · 2014
L'identification automatique de goulots d'étranglement dans la structure de solution a joué un rôle important en apprentissage par renforcement hiérarchique au cours des dernières années. Bien que populaire, cette approche manque toujours de fondements théoriques adaptés. Ce mémoire tente de pallier ces lacunes en établissant des liens en théorie spectrale des graphes, espérant ainsi obtenir une meilleure compréhension des conditions garantissant son applicabilité. Une revue des efforts réalisés concernant les chaines de Markov presque complètement décomposable (NCD) permet de croire qu'elles pourraient être utiles au problème ici considéré. Un algorithme de découverte d'options motivé par la théorie spectrale des graphes est proposé et semble être le premier du genre à pouvoir être aussi appliqué dans un espace d'états continu. Contraire- ment à d'autres approches similaires, la complexité algorithmique en temps peut être de l'ordre de O(n^2 log n) plutôt que O(n^3), rendant possible la résolution de problèmes de plus grande envergure.