¿Cuál es el operador de Bellman en el aprendizaje por refuerzo?

10

En matemáticas, la palabra operador puede referirse a varios conceptos distintos pero relacionados. Un operador se puede definir como una función entre dos espacios vectoriales, se puede definir como una función donde el dominio y el codominio son iguales, o se puede definir como una función desde funciones (que son vectores) a otras funciones (para ejemplo, el operador diferencial ), es decir, una función de orden superior (si está familiarizado con la programación funcional).

¿Cuál es el operador de Bellman en el aprendizaje por refuerzo (RL)? ¿Por qué lo necesitamos? ¿Cómo se relaciona el operador de Bellman con las ecuaciones de Bellman en RL?

nbro
fuente
Algunos documentos relacionados con este tema son Métodos basados ​​en características para la programación dinámica a gran escala (por John N. Tsitsiklis y Benjamin Van Roy, 1996), Un análisis del aprendizaje de diferencias temporales con aproximación de funciones (por John N. Tsitsiklis y Benjamin Van Roy, 1997) e Iteration de política de mínimos cuadrados (por Michail G. Lagoudakis y Ronald Parr, 2003).
nbro
Algunos documentos relacionados más que encontré son Procesos de decisión generalizados de Markov: Algoritmos de programación dinámica y aprendizaje de refuerzo (por Csaba Szepesvári y Michael L. Littman, 1997) yϵ-MDPs: Aprendizaje en diferentes ambientes (por István Szita, Bálint Takács, András Lörincz, 2002).
nbro

Respuestas:

11

La notación que usaré es de dos conferencias diferentes de David Silver y también está informada por estas diapositivas .

La ecuación de Bellman esperada es

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

Si dejamos

(2)Pssπ=aAπ(a|s)Pssa
y
(3)Rsπ=aAπ(a|s)Rsa
entonces podemos reescribir (1) como

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

Esto se puede escribir en forma de matriz

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

Or, more compactly,

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

Notice that both sides of (6) are n-dimensional vectors. Here n=|S| is the size of the state space. We can then define an operator Tπ:RnRn as

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

for any vRn. This is the expected Bellman operator.

Similarly, you can rewrite the Bellman optimality equation

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

as the Bellman optimality operator

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

The Bellman operators are "operators" in that they are mappings from one point to another within the vector space of state values, Rn.

Rewriting the Bellman equations as operators is useful for proving that certain dynamic programming algorithms (e.g. policy iteration, value iteration) converge to a unique fixed point. This usefulness comes in the form of a body of existing work in operator theory, which allows us to make use of special properties of the Bellman operators.

Specifically, the fact that the Bellman operators are contractions gives the useful results that, for any policy π and any initial vector v,

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

(11)limk(T)kv=v

where vπ is the value of policy π and v is the value of an optimal policy π. The proof is due to the contraction mapping theorem.

Philip Raeisghasem
fuente