Qu'est-ce que l'opérateur Bellman dans l'apprentissage par renforcement?

10

En mathématiques, l' opérateur de mot peut faire référence à plusieurs concepts distincts mais liés. Un opérateur peut être défini comme une fonction entre deux espaces vectoriels, il peut être défini comme une fonction où le domaine et le domaine de codage sont identiques, ou il peut être défini comme une fonction de fonctions (qui sont des vecteurs) à d'autres fonctions (pour exemple, l' opérateur différentiel ), c'est-à-dire une fonction d'ordre élevé (si vous êtes familier avec la programmation fonctionnelle).

Qu'est-ce que l' opérateur Bellman dans l'apprentissage par renforcement (RL)? Pourquoi en avons-nous même besoin? Comment l'opérateur Bellman est-il lié aux équations de Bellman dans RL?

nbro
la source
Quelques articles liés à ce sujet sont les méthodes basées sur les fonctionnalités pour la programmation dynamique à grande échelle (par John N. Tsitsiklis et Benjamin Van Roy, 1996), Une analyse de l'apprentissage des différences temporelles avec approximation des fonctions (par John N. Tsitsiklis et Benjamin Van Roy, 1997) et Least-Squares Policy Iteration (par Michail G. Lagoudakis et Ronald Parr, 2003).
nbro
Quelques autres articles connexes que j'ai trouvés sont les processus de décision de Markov généralisés: algorithmes de programmation dynamique et d'apprentissage par renforcement (par Csaba Szepesvári et Michael L. Littman, 1997) etϵ-MDPs: Learning in Varying Environments (par István Szita, Bálint Takács, András Lörincz, 2002).
nbro

Réponses:

11

La notation que j'utiliserai provient de deux conférences différentes de David Silver et est également informée par ces diapositives .

L'équation de Bellman attendue est

(1)vπ(s)=aAπ(a|s)(Rsa+γsSPssavπ(s))

Si nous laissons

(2)Pssπ=aAπ(a|s)Pssa
et
(3)Rsπ=aAπ(a|s)Rsa
alors nous pouvons réécrire (1) comme

(4)vπ(s)=Rsπ+γsSPssπvπ(s)

Cela peut être écrit sous forme de matrice

(5)[vπ(1)vπ(n)]=[R1πRnπ]+γ[P11πP1nπPn1πPnnπ][vπ(1)vπ(n)]

Ou, de façon plus compacte,

(6)vπ=Rπ+γPπvπ

Notez que les deux côtés de (6) sont n-vecteurs dimensionnels. Icin=|S|est la taille de l'espace d'état. On peut alors définir un opérateurTπ:RnRn comme

(7)Tπ(v)=Rπ+γPπv

pour toute vRn. Il s'agit de l'opérateur Bellman attendu.

De même, vous pouvez réécrire l'équation d'optimalité de Bellman

(8)v(s)=maxaA(Rsa+γsSPssav(s))

comme opérateur d'optimalité Bellman

(9)T(v)=maxaA(Ra+γPav)

Les opérateurs Bellman sont des "opérateurs" en ce sens qu'ils sont des correspondances d'un point à un autre dans l'espace vectoriel des valeurs d'état, Rn.

La réécriture des équations de Bellman en opérateurs est utile pour prouver que certains algorithmes de programmation dynamique (par exemple, itération de politique, itération de valeur) convergent vers un point fixe unique. Cette utilité se présente sous la forme d'un corpus de travaux existants en théorie des opérateurs, qui nous permet d'utiliser les propriétés spéciales des opérateurs de Bellman.

Plus précisément, le fait que les opérateurs de Bellman soient des contractions donne des résultats utiles qui, pour toute politiqueπ et tout vecteur initial v,

(10)limk(Tπ)kv=vπ

(11)limk(T)kv=v

vπ est la valeur de la politique π et v est la valeur d'une politique optimale π. La preuve est due au théorème de cartographie de contraction .

Philip Raeisghasem
la source