Aprendizagem por reforço

Jacques RobinCIn-UFPE

O que é aprendizagem por reforço?

Uma classe de problemasclasse de problemas de aprendizagem (pela qual existe uma grande diversidade de técnicastécnicas)

Aprendizagem:por um agente com objetivo(s) situado em um ambienteda utilidade dos estadosutilidade dos estados do ambiente com respeito a esse(s) objetivo(s)

ouou de uma política de açãopolítica de ação maximizando o grau de satisfação desse(s) objetivo(s)

indiretamenteindiretamente via recepção de reforçoreforço (ou dica) positivo ou negativo

quando se encontra em alguns estadosou como resultado da execução de uma ação ou uma serie de ações

Exemplo de tarefa de aprendizagem por reforço

Agente explorador da caverna do wumpus Explora N instâncias aleatoriamente geradas da

caverna Recebe reforços:

+1 quando sai vivo da caverna sem o ouro+5 quando sai vivo da caverna com o ouro-5 quando morre caindo em um buraco ou devorado pelo wumpus

Aprende:função f: Percepções Ações, para um agente puramente reativo

ou, função g: EstadosDaCaverna Utilidades, para um agente reativo com estado interno, modelo perceptivo e modelo efetivo do ambiente

Aprendizagem por reforço xAprendizagem supervisionada

Aprendizagem por reforçoAprendizagem por reforço retorno na forma de dica, as

vezes para um conjunto de escolhasex, na situação 26, a ação 27 é nota 0.8

ex, a partir da situação 26, a serie de ação 27, 3, 12, 79, e 99 é nota 0.3

permite treinamentotanto prévio a utilização quanto durantedurante a utilização

aprende mapeamento global percepção(t) ação(t)

para satisfazer simultaneamente váriosvários objetivos

Aprendizagem supervisionadaAprendizagem supervisionada retorno na forma da escolha correta,

separadamente por cada escolha: ex, na situação 26, ação 67 era a melhor

requer treinamento antesantes da utilização

aprende mapeamentos componentes:classificação (percepção(t),modelo(t-1)) modelo(t)

previsão (modelo(t),ação(t)) modelo(t+1))

otimização (modelo(t+1),objetivo(t)) max(utilidade(t+1))

para satisfazer um únicoúnico objetivo

Conceitos chaves daaprendizagem por reforço

Política de ação Função de reforço Função de valor

(ou utilidade) Modelo do ambiente

Policy

Reward

ValueModel of

environment

Política de ação

Mapeia estado percebido do ambiente pelo agente para a ação a executar nesse estado que maximiza satisfação dos seus objetivos

: percepção(estado(ambiente)) ação(estado(ambiente))

estado percebido pode ser última percepção recebida ou modelo construído a partir das percepções anteriores

pode ser determinista ou estocástica

Função de reforço

Mapeia estados do ambiente ou transição do ambiente de um estado para um outro para um número indicando a satisfação imediata dos objetivos do agente nesse estado ou no estado resultando da transição

r: estado(ambiente) real, ou r: (estado1(ambiente), estado2(ambiente)) real r codifica os objetivos do agente de maneira

imediata local r pode ser determinista ou estocástica

Função de valor

Mapeia estado do ambiente para um número indicando o a satisfação futura atingível dos objetivos do agente a partir desse estado

v: estado(ambiente) real v codifica os objetivos do agente de maneira global

e a prazo v(e) definida como função aditiva dos reforços nos

estados alcançáveis a partir de e:v(ek) = i[k,+[ pi.r(ei)

v(ek) = i[k,j] r(ei)

v(ek) = limji[k,j] r(ei)

Modelo do ambiente

Modelo perceptivo, mapeia percepções para representação interna do estado do ambientemp: (percepção(t), modelo(estado(ambiente(t-1)))) modelo(estado(ambiente(t)))

Modelo efetivo, mapeia ação a efetuar para representação interna do estado do ambiente resultando dessa açãome: (ação(t), modelo(estado(ambiente(t)))) modelo(estado(ambiente(t+1)))

Cada um desses modelos pode ser: representado em extensão por uma tabela, ou representado em intenção por algum formalismo de representação do conhecimento como operadores de próximo estado, regras, lógica, operadores de planejamento

manualmente codificado, ou aprendido com aprendizagem supervisionado

Exemplo introdutório: jogo da velha

} x joga

} x joga

} o joga

} x joga

} o joga

X XXO O

X

XO

X

O

XO

X

O

X

XO

X

O

X O

XO

X

O

X O

X

...

...... ...

... ... ... ... ...

x x

x

x o

x

o

xo

x

x

xx

o

o

Exemplo introdutório: jogo da velha

1. Inicializar tabela de valores com tabela de reforços

2. Fazer agente jogar muitos jogos contra adversário imperfeito Escolhendo:

a grande maioria das vezes ação que leva a estado de maior valor as vezes aleatoriamente ação que leva a estado com valor menor

Atualiza tabela depois de cada ação levando do estado s para o estado s´ com a formula: V(s) := V(s) + p(V(s´) – V(s)) na qual p é o tamanho de passo de aprendizagem

Estado V(s) – Probabilidade estimada de ganhar

.5 ?

.5 ?. . .

. . .

. . .. . .

1 vitória

0 derrota

. . .. . .

0 empate

x

xxx

oo

oo

ox

x

oo

o ox

xx

xo

Exemplo introdutório: jogo da velha

Exemplo de técnica de aprendizagem por reforço dita de diferencia temporal

Se p decresce a cada iteração, convergência para a tabela de valor representando política de ação ótima contra um adversário usando uma política de ação fixa

Se p não decresce até 0, bom desempenho mesmo contra adversário que muda lentamente sua política de ação

Ilustra como aprendizagem por reforço permite um agente:tomar em conta conseqüências de longo prazo da suas ações sem busca explícita no espaço dos estados ou das seqüências de ações

adaptar-se a um adversário ou a um ambiente dinâmico sem um modelo explícito do mesmo

Exemplos de aplicações práticas da aprendizagem por reforço

Jogos com agente treinado jogando contra ele mesmo, ou várias encarnações ligeiramente diferentes dele

Navegação e manipulação robótica Filtragem de e-mail sem aquisição manual nem de

regras de filtragem, nem de corpus de exemplos positivos e negativos

Tipologia dos problemas de aprendizagem por reforço

Passivo Reforço em qualquer estado Com modelo prévio do

ambiente Aprendizagem da função

valor Ambiente accessível Ambiente determinista Ambiente episódico

Ativo Reforço em poucos estados Sem modelo prévio do

ambiente Aprendizagem da função

ação-valor Ambiente inacessível Ambiente não determinista Ambiente não episódico

No caso mais complexo,a aprendizagem por reforço é praticamente equivalente a IA como um todo

Aprendizagem por reforço passivo x ativopassivo x ativo

PassivoPassivo Ambiente passa de um estado

para o outro sem intervenção do agente

A cada transição, agente apenas:percebe o estado e recebe reforço

atualiza sua representação do valor desse estado

Equivalente a situação na qual:Agente faz mudar o ambiente pela execução de uma política de ação predefinida

Agente não tenta descobrir uma boa política de ação

mas apenas avaliar política predefinida

AtivoAtivo Agente tenta descobrir uma boa

política de ação A cada transição, agente:

percebe o estado e recebe reforço

atualiza sua representação do valor desse estado

escolhe uma ação a executar que muda o estado do ambiente

Dilema aproveitamento-exploração

Na aprendizagem por reforço ativa o agente enfrenta dilema aproveitamento-exploração:Quando gulosamente aproveitar da estimação atual da função valor e escolher ação que a maximiza?

Quando curiosamente explorar outra ação que pode levar a melhorar estimação atual da função valor?

Particularmente relevante quando aprendizagem ocorre durante utilização, sem fase de treinamento prévio

Taxa de exploração = proporção de escolhas curiosasGeralmente se começa com uma taxa de exploração alta que vai decrescendo com tempo

Mesmo princípio do que o simulated annealing

Aprendizagem por reforço com reforçoem todos xtodos x em poucospoucos estados

Reforço em Reforço em todos todos os estadosos estados Agente recebe reforço em todos

os estados Pode facilmente atribuir esse

reforço esse estado o a última ação que executou

Simplifica a atualização da estimativa do valor desse estado ou ação

Reforço em Reforço em poucos poucos estadosestados Agente recebe reforço apenas

em poucos estados Enfrenta o problema da

distribuição desse reforço entre as várias ações que executou desde o último reforço

Dificulta atualização da estimativa do valor dos estados ou das ações

Dilema da atribuição do mérito

Na maioria dos casos, reforço é recebido apenas em alguns estados

Em jogos, agente pode receber reforço apenas no estado final (ganhou? perdeu? empatou?)

As vezes, agente executa uma política de ação ótima com apenas um único erro grave e recebe reforço negativo

Como identificar qual foi a ação que causou esse reforço? A mesma ação no mesmo estado pode ser ótima no contexto de

uma serie de ações, mas péssima no contexto de uma outra serie Dilema geralmente resolvido iterativamente pela execução de

muitas series de ações diferentesValor de uma ação em um estado estimada como média do seu valor em todas as series tentadas

Seu valor em uma serie tentada estimada como o reforço recebido pela serie divido pelo tamanho da serie

Computacionalmente caro Ressalta necessidade de exploração

Aprendizagem por reforço com x sem modelocom x sem modelo prévio do ambiente

ComCom modelo prévio do modelo prévio do ambienteambiente

Agente possui modelo do ambiente para prever transições de estado do ambiente causada pelas suas ações

Em ambiente não determinista tal modelo pode ser apenas estocástico

SemSem modelo prévio do modelo prévio do ambienteambiente

Agente ignora a priori:tanto o valor de cada estado do ambiente com respeito a seus objetivos

quanto as transições de estado do ambiente que suas ações podem causar

Dois tipos de técnicas:As que permitem ao agente aprender o valor de ação para a realização dos seus objetivos sem conhecer o estado do ambiente

As que permitem aprender ambas a função valor e a função de transição de estado

Aprendizagem por reforço de uma função valor xfunção valor x de uma função ação-função ação-

valorvalor

Função valorFunção valor associa valor diretamente a

estados dos ambiente valor de uma ação indiretamente

definida como valor do estado resultado da execução da ação

aplicável apenas para agente com modelo efetivo do ambiente (para prever o estado resultado da execução de cada ação)

Função ação-valorFunção ação-valor associa valor diretamente a

pares (estado(ambiente),ação) aplicável a agente:

sem modelo efetivo do ambientesem nenhum modelo de um ambiente acessível

com modelo apenas perceptivo de um ambiente inacessível

chamado de Aprendizagem Q

Aprendizagem por reforço de uma função valor xfunção valor x de uma função ação-função ação-

valorvalor

0

000

0 100

Reforços

0

00

0

0

0

0

0

100

100

0

0

0

Reforços

81

908172

90 100

Função Valor Função Ação-Valor

81

8172

90

81

72

90

81

100

100

81

90

0

Aprendizagem por reforço em ambiente episódico x não episódicoepisódico x não episódico

Ambiente episódicoAmbiente episódico O reforço recebido pelo agente

depende apenas do estado atual do ambiente

O estado sucessor depende apenas do estado atual e da ação a executar

Ambos são independentes dos estados precedentes pelo qual o ambiente passou

Escolher uma ação em tal ambiente chama-se de processo de decisão de Markov

Pode se reusar o vasto leque de técnicas de otimização iterativas probabilistas disponíveis para tais processos

Ambiente não episódicoAmbiente não episódico Agentes chegando no mesmo

estados do ambiente por caminhos diferentes podem:receber reforços diferentesfazer passar o ambiente para estados diferentes executando a mesma ação nesse mesmo estado

Técnicas baseadas em modelos de Markov não se aplicam

Aprendizagem por reforço em ambiente determinista x não deterministadeterminista x não determinista

Ambiente deterministaAmbiente determinista Agente recebe sempre mesma

percepção e mesmo reforço ao chegar em um determinado estado do ambiente

Agente executando a mesma ação no mesmo estado do ambiente sempre leva-o no mesmo estado sucessor

Função valor ou ação-valor podem ser determinista

Ambiente não deterministaAmbiente não determinista Agente pode receber

percepções e reforços diferentes quando chegar várias vezes no mesmo estado do ambiente

Execução da mesma ação no mesmo estado pode levar o agentes para estados sucessores diferentes

Sensores e atuadores ruidosos são umas das causas de tal não determinismo

Função valor ou ação-valor há de ser estocástica

Técnicas de Aprendizagem Por Reforço (APR)

APR passiva compassiva com modelo efetivo do ambiente:LMS: teoria do controle adaptativoADP: programação dinâmica adaptativa (pesquisa operacional)

TD: diferencia temporal

APR passiva sempassiva sem modelo efetivo do ambiente:LMS e TD

APR ativa comativa com modelo efetivo do ambiente:ADP ativa e TD ativaModelo previamente conhecido ou iterativamente aprendido junto a função valor

APR ativa semativa sem modelo efetivo do ambiente: Aprendizagem Q

APR passiva com modelopassiva com modelodo ambiente não deterministanão determinista

Agente guarda para cada estado: probabilidades de transição para os outros estadosnúmero de vezes que foi alcançadoestimativa atual de v

Várias técnicas em função da formula de atualização de v

3 -0.0380 0.0886 0.2152 +1

2 -0.1646 -0.4430 -1

1 -0.2911 -0.4177 -0.5443 -0.7722

1 2 3 4

3 +1

2 -1

1 Start

1 2 3 4

Teoria do controle adaptativa

LMS: v(sk) = ij r(sij) / n

onde sij são os estados depois de sk nos n percursos já explorados passando por sk

reduz aprendizagem por reforço a aprendizagem supervisionada com reforços a vir já observados sendo o retorno

valor estimado de um estado função apenas de reforços função apenas de reforços ignorando valor estimado de outros estadosignorando valor estimado de outros estados

por isso converge muito lentamentecomo não usa modelo do ambiente é utilizável para APR semsem modelo

Programação dinâmica adaptativae diferença temporal

ADP: v(si) = r(si) + jp(trans(si,sj)).v(sj) onde p(trans(si,sj)) é a probabilidade do ambiente passar do estado si para o estado sj

valor estimado de um estado função do reforço no estado, dos função do reforço no estado, dos valores estimados em estados vizinhos e do modelo do ambientevalores estimados em estados vizinhos e do modelo do ambiente

por isso converge mais rapidamente que LMSporém computacionalmente caro por tomar em consideração, para cada percurso, todos os vizinhos de todos os estados do percurso

intratável para ambientes com muitos estados, ex, jogo do backgammon envolveria resolver sistema de 1050 equações com 1050 variáveis

TD: v(si,ek) = v(si,ek-1) + (r(sj) + v(sj,ek-1) - v(si,ek-1))valor estimado do estado função do reforço no estado e do valor função do reforço no estado e do valor estimado deestimado de apenas um vizinhoapenas um vizinho, o precedente no percurso atual

rapidez de convergência melhor que LMS mas menor que ADP porém mais computacionalmente escalável do que ADP

APR passiva sem modelo efetivo sem modelo efetivodo ambiente não determinista

LMS e TD de fato não usam modelo efetivo do ambiente e então se aplicam a esse caso sem modificação

ADP precisa ser modificado da seguinte maneira:modelo adquirido simultaneamente com função valor via percursos no ambiente

cada transição observada é registrada pelo agenteesse registros são generalizados por uma técnica de aprendizagem supervisionada incremental como: redes neurais redes bayesianas programação em lógica incremental

ADP ativaativa

Mudanças chaves de passivo para ativo:Adição de política de compromisso aproveitamento-exploraçãoParametrização do modelo efetivo pelas ações a executar

Atualização: v(si) = r(sj) + maxa e(jp(trans(si,a,sj)).v(sj) , n(a,sj)), ondep(trans(si,a,sj)) é a probabilidade do estado sj ser o resultado da execução da ação a no estado si

n(a,sj) é o número de vezes a ação a foi escolhida no estado sj

e(v,n) é a função de exploraçãofunção de exploraçãoe(v,n) = r+ se n Le(v,n) = v se n Lr+ é uma estimativa otimista do maior reforço disponível no ambienteL é um limiar fixo

Modelo p(trans(si,a,sj)) aprendido semelhantemente a p(trans(si,sj)), exceto pelo registro da ação executada que causou a transição observada

TD ativaativa

Coeficiente no fórmula de atualização toma em consideração compromisso aproveitamento-exploração: = 1 / 1 + n(a,s)onde n(s,a) é o número de vezes a ação a foi escolhida no estado s

Função de exploração e acrescentada para escolher a ação a executar

Modelo efetivo do ambiente: passa a ser necessário para escolher ação a executar a cada passo

pode ser aprendido iterativamente usando mesmas técnicas do que no ADP ativo

Aprendizagem Q

Aprende valor de uma determinada açãoação em um determinado estado no lugar do valor desse estado em si

Permite dispensar modelodispensar modelo efetivo do ambiente inteiramente, mesmo no caso ativo não precisa ser fornecido como conhecimento prévio nem aprendido junto a função ação-valor

Relação entre função valor e função ação-valor: v(e) = maxa q(a,e)

Fórmula de atualização: q(am,si,ek) = q(am,si,ek-1) + (r(si) + maxan q(an,sj,ek-1) - q(am,si,ek-1)) / (1 + n(am,si))

onde: n(am,si) é o número de vezes a ação am foi escolhida no estado si

adaptação ao caso de aprendizagem de uma função ação-valor da fórmula de atualização de TD

ADP não pode ser usado para aprender valores q pós re-introduziria necessidade de um modelo efetivo do ambiente

Converge menos rapidamente que ADP

Representação intencional do ambiente

Métodos apresentados até agora não são escaláveis para domínios com muitos estados e com muitas ações

Solução: mudar de uma representação em extensãoem extensão dos estados do ambiente, dos efeitos das ações e do valor dos estados ou ações para uma representação em intençãoem intenção

integrar aprendizagem por reforço com representação do conhecimento e/ou aprendizagem supervisionado incremental

Cada elemento de um problema de APR pode ser abstraído por um vetor de atributos, ex, v(ei) = w1f1(ei) + ... + wnfn(ei)Essa soma ponderada pode ser substituída ao v(ei) nas equações de atualização

os pesos aprendidos usando aprendizagem supervisionado incremental

os fj(ek) aprendidos resolvendo as novas equações abstratas

Aprendizagem por reforço x resolução de problema por meio de

busca

Métodos de busca iterativas como gradiente crescente e simulated annealing podem ser usadas para resolver problemas de APR

Buscam o espaço das políticas de ação diretamente, sem recorrer ao conceito intermediário de função valor ou função ação-valor

Viável apenas com ambiente muito pequenos Não permitem aprendizagem durante utilização,

mas apenas durante treinamento prévio

Aprendizagem por reforço xraciocínio baseado em conhecimento

Raciocínio baseado em conhecimento pode ser usado por um agente aprendendo por

reforço junto a uma representação em intenção do

problema para:

interpretar percepções para identificar reforço e estado do ambiente

prever efeitos das ações calcular utilidade

Aprendizagem por reforço x planejamento

APR pode ser combinado com planejamento hierárquico

A decomposição de um operador O na penúltima camada mais baixa do planejador é: nem enlatada nem construída usando planejamento mas construída por uma agente de APR

Quando o agente APR: executa uma serie de ações a partir de uns dos estados satisfazendo a precondição P(O) se o resultado é de fazer passar o ambiente por uns dos estados satisfazendo o efeito E(O) ele recebe um reforço +

senão, ele recebe um reforço -

Aprendizagem por reforço x aprendizagem conexionista e

evolucionista

Redes neurais e algoritmos genéticos podem ser usados para resolver problemas de APR

Aprendem políticas de ação diretamente, sem recorrer ao conceito intermediário de função valor ou função ação-valor

Os pesos de uma rede neural podem ser ajustados em função da recepção de reforços positivos ou negativos

A função de fitness de um algoritmo genético pode ser definida em termos dos reforços positivos ou negativos

Tópicos avançados emaprendizagem por reforço

Aprendizagem por reforço hierárquico: Idéia semelhante ao planejamento hierárquico Tarefa do agente decomposta em camadas O comportamento aprendido por reforço a uma camada mais baixa serve para execução de ação a camada acima

Aprendizagem por reforço relacional Modelo intencional do ambiente Baseado em programas lógicos ou árvores de decisão com variáveis lógicas

Fornecido como conhecimento prévio, e/ou aprendido junto a função valor ou ação-valor via programação em lógica indutiva

Aprendizagem por reforço multi-agentes

Leituras

Capítulo 22 do AIMA de Russell & Norvig www.cs.berkeley.edu/~russell/aima.html

Capítulo 13 de Machine Learning do Mitchell www.cs.cmu.edu/~tom/mlbook.html

Reinforcement Learning, livro de Sutton & Barbo http://www-anw.cs.umass.edu/~rich/book/the-book.html

Reiforcement Learning: A Surveyde Kaelbling, L.P. & Littman, M.L. www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/ kaelbling96a-html/rl-survey.html

ifile: An Application of Machine Learning to E-Mail Filtering, http://citeseer.nj.nec.com/11099.html