O que é o operador Bellman na aprendizagem por reforço?

10

Em matemática, a palavra operador pode se referir a vários conceitos distintos, mas relacionados. Um operador pode ser definido como uma função entre dois espaços vetoriais, pode ser definido como uma função em que o domínio e o codomain são iguais ou pode ser definido como uma função de funções (que são vetores) para outras funções (por por exemplo, o operador diferencial ), ou seja, uma função de alta ordem (se você estiver familiarizado com a programação funcional).

O que é o operador Bellman na aprendizagem por reforço (RL)? Por que precisamos disso? Como o operador Bellman está relacionado às equações de Bellman na RL?

nbro
fonte
Alguns artigos relacionados a este tópico são Métodos Baseados em Recursos para Programação Dinâmica em Grande Escala (por John N. Tsitsiklis e Benjamin Van Roy, 1996), Uma Análise da Aprendizagem por Diferenças Temporais com Aproximação de Funções (por John N. Tsitsiklis e Benjamin Van Roy, 1997) e Iteração de política de mínimos quadrados (por Michail G. Lagoudakis e Ronald Parr, 2003).
nbro
Outros artigos relacionados que encontrei são Processos de Decisão Generalizados de Markov: Algoritmos de programação dinâmica e aprendizado de reforço (por Csaba Szepesvári e Michael L. Littman, 1997) eϵ-DPM: Aprendizagem em ambientes variados (por István Szita, Bálint Takács, András Lörincz, 2002).
nbro

Respostas:

11

A notação que vou usar é de duas palestras diferentes de David Silver e também é informada por esses slides .

A equação de Bellman esperada é

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

Se deixarmos

(2)Pssπ=aAπ(a|s)Pssa
e
(3)Rsπ=aAπ(a|s)Rsa
então podemos reescrever (1) Como

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

Isso pode ser escrito em forma de matriz

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

Ou, de forma mais compacta,

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

Observe que os dois lados da (6) estamos ntridimensionais. Aquin=|S|é o tamanho do espaço de estado. Podemos então definir um operadorTπ:RnRn Como

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

para qualquer vRn. Este é o operador esperado da Bellman.

Da mesma forma, você pode reescrever a equação de otimização de Bellman

(8)v(s)=maxumaUMA(Rsuma+γsSPssumav(s))

como o operador de otimização Bellman

(9)T(v)=maxumaUMA(Ruma+γPumav)

Os operadores Bellman são "operadores", pois são mapeamentos de um ponto para outro no espaço vetorial de valores de estado, Rn.

Reescrever as equações de Bellman como operadores é útil para provar que certos algoritmos de programação dinâmica (por exemplo, iteração de política, iteração de valor) convergem para um ponto fixo exclusivo. Essa utilidade vem na forma de um corpo de trabalho existente na teoria dos operadores, o que nos permite fazer uso de propriedades especiais dos operadores Bellman.

Especificamente, o fato de os operadores Bellman serem contrações fornece resultados úteis que, para qualquer políticaπ e qualquer vetor inicial v,

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

11)limk(T)kv=v

Onde vπ é o valor da política π e v é o valor de uma política ideal π. A prova é devida ao teorema do mapeamento de contração .

Philip Raeisghasem
fonte