25-Aprendizagem_por_reforco

Prévia do material em texto

APRENDIZADO	
  POR	
  REFORÇO	
  
	
  
	
  
	
  
Roteiro	
  
¨  Introdução	
  
¨  Aprendizado	
  Passivo	
  	
  
¤  Ambiente	
  Conhecido	
  
¤  Ambiente	
  Desconhecido	
  
¨  Aprendizado	
  AAvo	
  	
  
¤  Ambiente	
  Desconhecido	
  
¨  Exploração	
  
¨  Aprendendo	
  uma	
  Função	
  Valor-­‐Ação	
  
¨  Generalização	
  no	
  Aprendizado	
  com	
  Reforço	
  
Introdução	
  
¨  Xadrez	
  
¤  Aprendizado	
  supervisionado	
  
¤  As	
  próximas	
  jogadas	
  têm	
  um	
  valor	
  
¤  Mas:	
  
n  E	
  se	
  não	
  houvesse	
  um	
  feedback?	
  
¤  Feedback	
  
n  Só	
  no	
  final	
  do	
  jogo	
  (ganhou,	
  perdeu,	
  empatou)	
  
n  ESTADO	
  TERMINAL	
  
Introdução	
  
¨  Recompensa	
  ou	
  Reforço	
  (negaAva	
  ou	
  posiAva)	
  
¤  Tarefa	
  do	
  aprendizado	
  com	
  reforço	
  
n  Usar	
  recompensa	
  para	
  treinar	
  um	
  agente	
  
Agente 
Ambiente 
ação recompensa 
estado 
rt+1 
st+1 
st rt at 
Introdução	
  
¨  Como	
  variam	
  as	
  tarefas	
  de	
  treinamento?	
  
¤  Quanto	
  aos	
  estados	
  
n  Acessíveis	
  
n  Percepção	
  –	
  estado	
  
n  Inacessíveis	
  	
  
n  Estados	
  inacessíveis	
  
¤  Quanto	
  ao	
  estado	
  inicial	
  
n  O	
  	
  ambiente	
  e	
  seus	
  efeitos	
  são	
  conhecidos	
  
n  Terá	
  que	
  aprender	
  um	
  modelo	
  do	
  ambiente	
  
¤  Quanto	
  às	
  recompensas	
  
n  Somente	
  no	
  estado	
  terminal	
  
n  Em	
  qualquer	
  estado	
  
Introdução	
  
¨  Como	
  variam	
  as	
  tarefas	
  de	
  treinamento?	
  
¤  Quanto	
  à	
  políAca	
  (o	
  que	
  o	
  agente	
  deve	
  fazer	
  para	
  cada	
  estado)	
  
n  UAlidade	
  real	
  
n  Pontos	
  em	
  uma	
  parAda	
  de	
  tênis	
  de	
  mesa	
  
n  Apostas	
  
n  Dicas	
  
n  legal!!	
  
n  bom,	
  hein?!	
  
n  uhuuuu!!	
  
n  idiota!!!	
  
¤  Quanto	
  à	
  interação	
  com	
  o	
  ambiente	
  
n  Passivos	
  
n  Só	
  assistem	
  o	
  mundo,	
  tentando	
  aprender	
  a	
  uAlidade	
  em	
  vários	
  estados	
  
n  AAvos	
  
n  Agem	
  usando	
  a	
  informação	
  aprendida	
  ou	
  o	
  gerador	
  de	
  problemas	
  
Experiências	
  
¨  Podemos	
  supor	
  que	
  há	
  uma	
  sequência	
  de	
  experiências:	
  
	
  estado,	
  ação,	
  recompensa,	
  estado,	
  ação,	
  recompensa,	
  ...	
  
¨  A	
  qualquer	
  momento	
  o	
  agente	
  deve	
  decidir	
  se	
  deseja:	
  
	
  para	
  obter	
  mais	
  conhecimentos.	
  
o	
  conhecimento	
  que	
  ele	
  já	
  
descobriu.	
  
Por	
  que	
  a	
  aprendizagem	
  por	
  reforço	
  é	
  diacil?	
  
¨  As	
  ações	
  responsáveis	
  pela	
  recompensa	
  podem	
  ter	
  ocorrido	
  
um	
  longo	
  tempo	
  antes	
  da	
  recompensa	
  ser	
  recebida.	
  
¨  O	
  efeito	
  a	
  longo	
  prazo	
  de	
  uma	
  ação	
  do	
  robô	
  depende	
  do	
  que	
  
vai	
  fazer	
  no	
  futuro.	
  
¨  O	
  dilema	
  de	
  explorar-­‐exploração	
  (fazer	
  uso):	
  a	
  cada	
  passo	
  o	
  
robô	
  deverá	
  ser	
  ganancioso	
  ou	
  curioso?	
  
Abordagens	
  ao	
  aprendizado	
  por	
  reforço	
  
¨  Existem	
  2	
  projetos	
  básicos:	
  
¤  O	
  agente	
  aprende	
  uma	
  função	
  uAlidade	
  para	
  os	
  estados	
  
n  Escolhe	
  ações	
  que	
  tentam	
  maximizar	
  a	
  função	
  uAlidade	
  
n  EU	
  CONHEÇO	
  AS	
  REGRAS	
  DO	
  JOGO	
  
¤  O	
  agente	
  aprende	
  uma	
  função	
  valor-­‐ação	
  
n  UAlidade	
  média	
  para	
  uma	
  dada	
  ação	
  
n  Q-­‐learning	
  
n  EU	
  NÃO	
  CONHEÇO	
  AS	
  REGRAS.	
  	
  
n  VOU	
  TER	
  QUE	
  APRENDER	
  JOGANDO.	
  
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
¨  Modelo	
  Maij P(j|I,a)	
  =	
  
probabilidade	
  de	
  que	
  executando	
  a	
  
leva	
  a	
  j	
  
¨  Cada	
  estado	
  tem	
  uma	
   	
  
R(i):	
  
•  =	
  -­‐0.04	
  (custo	
  pequeno)	
  para	
  
estados	
  não	
  teminais	
  
•  =	
  ±1	
  para	
  os	
  estados	
  terminais	
  
≡
1 2 3
1
2
3 + 1
4
START
0.8
0.10.1
Exemplo	
  de	
  sequência	
  de	
  treinamento	
  
época 
reward-to-go de um estado é: 
 A soma das recompensas de um estado até que seja 
 alcançado o estado terminal 
 
utilidade esperada (média) de um estado é: 
 O reward-to-go médio daquele estado 
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
função AGENTE-RL-PASSIVO(e) retorna uma ação 
 estático: 
 U, uma tabela de estimativas de utilidade 
 N, uma tabela de freqüências para os estados 
 M, uma tabela de probabilidades de transição de um estado para outro 
 
 adiciona(e, percepções) 
 incrementa(N[ESTADO[e]]) 
 U ← ATUALIZA(U, e, percepções, M, N) 
 se TERMINAL[e] então 
 percepções ← [] 
 retorna a ação Observe 
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
¨  Atualização	
  ingênua	
  (naïve)	
  
¤  Vem	
  da	
  “Teoria	
  de	
  Controle	
  AdaptaAvo”	
  
¤  Abordagem	
  LMS	
  (least	
  mean	
  squared)	
  
¤  A	
  probabilidade	
  real	
  de	
  um	
  estado	
  está	
  restrita	
  à	
  probabilidade	
  média	
  
ponderada	
  das	
  uAlidades	
  de	
  seus	
  sucessores	
  mais	
  a	
  própria	
  recompensa.	
  
função ATUALIZA-LMS(U, e, percepções, M, N) retorna uma U atualizada 
 
se TERMINAL[e]então 
 reward_to_go ← 0 
 para cada ei em percepções (a partir do final) faça 
 reward_to_go ← reward_to_go + RECOMPENSA[ei] 
 U[ESTADO[ei]] ← MÉDIA(U[ESTADO[ei]],reward_to_go,N[ESTADO[ei]]) 
 fimfaça 
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
¨  Programação	
  Dinâmica	
  AdaptaAva	
  (ADP)	
  
¤  Inviável	
  para	
  grandes	
  espaço-­‐estado	
  
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
¨  Aprendizado	
  por	
  Diferença	
  Temporal	
  (TD)	
  
¤  A	
  chave	
  é	
  usar	
  as	
  transições	
  observadas	
  para	
  ajustar	
  os	
  valores	
  dos	
  
estados	
  observados	
  para	
  que	
  saAsfaçam	
  as	
  equações	
  de	
  restrição.	
  
função ATUALIZA-TD(U, e, percepções, M, N) retorna a tabela de utilidades U 
 
 se TERMINAL[e] então 
 U[ESTADO[e]] ← MÉDIA(U[ESTADO[e]], RECOMPENSA[e],N[ESTADO[e]]) 
 senão se percepções contém mais de um elemento então 
 e’ ← o penúltimo elemento de percepções 
 i, j ← ESTADO[e’], ESTADO[e] 
 U [i] ← U [i] + α(N[i])(RECOMPENSA[e’] + U [j] – U [i]) 
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Conhecido	
  
Aprendizado	
  Passivo	
  em	
  um	
  Ambiente	
  
Desconhecido	
  
Aprendizado	
  AAvo	
  em	
  um	
  Ambiente	
  
Desconhecido	
  
¨  Pequenas	
  alterações	
  para	
  acomodar	
  as	
  ações	
  do	
  agente:	
  
¤  O	
  modelo	
  do	
  ambiente	
  deve	
  incorporar	
  as	
  probabilidades	
  das	
  transições	
  
para	
  outros	
  estados	
  a	
  parAr	
  de	
  uma	
  ação	
  parAcular.	
  Maij	
  é	
  a	
  
probabilidade	
  de	
  alcançar	
  o	
  estado	
  j	
  se	
  for	
  tomada	
  a	
  ação	
  a	
  no	
  estado	
  i	
  
¤  As	
  restrições	
  sobre	
  a	
  uAlidade	
  de	
  cadaestado	
  deve	
  considerar	
  o	
  fato	
  que	
  
o	
  agente	
  escolha	
  as	
  ações	
  
¤  O	
  agente	
  deve	
  escolher	
  uma	
  ação	
  a	
  cada	
  passo	
  e	
  precisará	
  de	
  um	
  
elemento	
  de	
  desempenho	
  para	
  fazer	
  isso.	
  Assume-­‐se	
  que	
  o	
  modelo	
  M	
  e	
  
as	
  uAlidades	
  U	
  são	
  comparAlhadas	
  pelo	
  elemento	
  de	
  desempenho	
  
Exploração	
  
¨  Uma	
  ação	
  tem	
  dois	
  Apos	
  de	
  resultado:	
  
¤  Ele	
  ganha	
  recompensas	
  na	
  sequência	
  atual	
  
¤  Ele	
  afeta	
  as	
  percepções	
  recebidas	
  e	
  portanto,	
  a	
  capacidade	
  do	
  agente	
  
aprender	
  -­‐-­‐	
  e	
  receber	
  recompensas	
  nas	
  futuras	
  sequências	
  
¨  Função	
  de	
  Exploração	
  
Aprendizado	
  AAvo	
  em	
  um	
  Ambiente	
  
Desconhecido	
  
função AGENTE-ADP-ATIVO(e) retorna uma ação 
 estático: 
 U, uma tabela de estimativas de utilidade 
 M, uma tabela de probabilidades de transição de um estado para outro para cada ação 
 R, uma tabela de recompensas para os estados 
 percepções, uma seqüência de percepções (inicialmente 
 vazia) 
 última-ação, a última ação executada 
 
 adiciona e às percepções 
 R[ESTADO[e]] ← RECOMPENSA[e] 
 M ← ATUALIZA-MODELO-ATIVO(M, percepções, última-ação) 
 U ← VALOR-INTERAÇÃO(U, M, R) 
 se for TERMINAL[e] então 
 percepções ← a seqüência vazia 
 última-ação ← ELEMENTO-DESEMPENHO(e) 
 retorna a última-ação 
Desempenho	
  de	
  um	
  Agente	
  Exploratório	
  ADP	
  
Aprendendo	
  uma	
  Função-­‐Valor	
  
função AGENTE-Q-LEARNING(e) retorna uma ação 
 estático: 
 Q, uma tabela de valores das ações 
 N, uma tabela de frequências de estado-ação 
 a, a última ação tomada 
 i, o estado anteriormente visitado 
 r, a recompensa recebida no estado i 
 
 j ← ESTADO[e] 
 se i não for nulo então 
 N[a, i] ←N[a, i] + 1 
 Q[a, i] ← Q[a, i] + α( r + max a’ Q[a’, j] – Q[a, i]) 
 se TERMINAL[e] então 
 i ←nulo 
 senão i ← j 
 r ← RECOMPENSA[e] 
 a ← arg max a’ f (Q[a’, j], N[a’, j] 
 retorna a 
Desempenho	
  de	
  um	
  Agente	
  Q-­‐Learning	
  TD