Page1 DAS-5341: Aprendizagem por Reforço Prof. Eduardo Camponogara

Page1

DAS-5341: Aprendizagem por Reforço

Prof. Eduardo Camponogara

Page2

AgendaIntrodução a Aprendizagem por Reforço

(AR)• Aprendizagem supervisionada• Aprendizagem não-supervisionada• Elementos básicos de AR• Função ganho e função valor• Exemplo

Page3

Introdução• Aprender por meio de nossas interações

com o ambiente– Uma criança não tem um professor, mas

possui habilidades cognitivas

– Através das interações, a criança descobre as relações de causa e efeito

– Aprendendo por meio de interações é uma idéia fundamental de quase todas as teorias de aprendizagem e inteligência

Page4

Introdução – Aplicação em Robótica

Obstáculo

Robô

DomínioProblema Dinâmico

(PD)• Aprender a navegar dentro do domínio• Coletar lixo (ganho +)• Trombar em obstáculos (ganho -)

• Controle de força

Page5

O Que Veremos?• Nas próximas aulas discutiremos uma

abordagem computacional para aprendizagem através de interações

• Exploraremos projetos de máquinas que são eficazes na solução de problemas de aprendizagem com interesse econômico e científico

• Avaliaremos a qualidade desses projetos por meio de análises matemáticas e experimentos computacionais

• A abordagem a ser explorada é chamada “Reinforcement Learning”

Page6

Aprendizagem por Reforço• Aprendizagem por reforço consiste em

aprender o que fazer—como mapear situações em ações—de maneira a maximizar um sinal de ganho

• Ao aprendiz não é dito que ação tomar, o qual deve aprender quais ações produzem maior ganho por meio de interações

• Nas situações mais desafiadores, o ganho não é imediato, mas futuro

Page7

Aprendizagem por Reforço• Características de RL (Reinforcement

Learning)– Ganho retardado– Busca por meio de tentativa e erro

• RL não é caracterizado por métodos de aprendizagem, mas por meio de um problema de aprendizagem

• O LP (Learning Problem) será especificado como um problema de controle ótimo sobre um processo de decisão Markoviano

Page8

The Learning Problem• A formulação inclui três aspectos básicos

de um agente que interage com o ambiente:– Percepção– Ação– Objetivo

• O agente percebe, pelo menos parcialmente, o estado do ambiente, suas ações afetam o estado e ele possui um objetivo relacionado ao ambiente

Page9

The Learning Problem

Agente

Ambiente

Ação at

Ganho rt+1

Estado st Problema

Encontre política de controle, at = (st) que maximize ganho total

Características

• Aprendizagem por tentativa e erro• Não necessita de modelos• Adaptação automática a ambientes desconhecidos ou dinâmicos

Page10

Aprendizagem por Reforco – Aplicações em Controle de

Tráfego

Agente(st, rt) = (filas, atrasos)

at = sinais

(PD)

Atividades

• Modelagem (PD)

• Estudo e implementação de métodos RL• Análise Experimental

Page11

Controle de Tráfego J2

J1

J3

J4

J5 J6

I1

I2

Page12

Resultados Computacionais

Page13

Resultados Computacionais

Page14

Aprendizagem Supervisionada x Aprendizagem por Reforço

• RL difere de aprendizagem supervisionada– Em aprendizagem supervisionada, o aprendiz

aprende por meio de exemplos recebidos de um supervisor sábio (oráculo)

– Em um território inexplorado, um agente tem que ser capaz de aprender a partir de sua própria experiência

– Uma das dificuldades em RL é o trade-off entre a escolha de explorar outras possibilidades ou tomar a ação que traz maior retorno imediato

Page15

Aprendizagem Supervisionada x Aprendizagem por Reforço

Aprendizagem Supervisionada

Situação Ação(x1

1, …, xn1) a1

(x12, …, xn

2) a2 … …

(x1m, …, xn

m) am

Problema: encontre função f(x) = a que:

a) aproxime os exemplos da tabela e

b) dado um estado x, indique a ação a que corresponda a uma interpolação dos exemplos de treinamento

Aprendizagem por Reforço

Não há tabela de dados. Esta deve ser construída implicitamente a partir da experiência adquirida por meio da interação com o ambiente

Problema: encontre f(x) = a, que maximize o ganho ao longo do tempo

Page16

Trade-off

• Para obter maior ganho, o agente prefere as ações que no passado produziram bons resultados

• Todavia, para descobrir tais ações, o agente tem que experimentar ações que ainda não selecionou

Page17

Trade-off: Exploration x Exploitation

• Dilema: tanto exploration quanto exploitation não podem ser seguidas exclusivamente sem que o agente falhe em sua tarefa.

– O agente deve explorar uma série de possibilidade e progressivamente favorecer aquelas que produzem melhores resultados

Page18

Ambiente Desconhecido• Uma outra característica

chave de RL é que este considera explicitamente o problema completo do agente:– o agente busca atingir um

objetivo enquanto interage com um ambiente desconhecido e incerto

• Planejamento tipicamente considera como conhecido o ambiente

Onde estou?

Page19

IA e Outras DisciplinasRL: • mais próxima da engenharia e outras disciplinas (como estatística e teoria do controle)• mais relacionada a grandezas numéricas, não apenas simbólicas

IA clássica está relacionada à lógica e símbolos

Hoje IA também engloba estatística, álgebra linear, equações diferenciais, etc.

Page20

IA e Outras Disciplinas• RL estende idéias da teoria de controle

ótimo e aproximações estocásticas para tratar de objetivos abrangentes e ambiciosos da Inteligência Artificial

Page21

Exemplos de Aprendizagem• Jogo de xadrez• Aprendizagem na natureza• Robótica

Page22

Exemplo: Xadrez• Um mestre de xadrez faz um

movimento– A escolha é informada pelo planejamento

(antecipação de possíveis respostas do adversário) e pelo julgamento imediato e intuitivo da qualidade do movimento

Page23

Exemplo: Aprendizagem na Natureza

• Uma gazela tem dificuldade de locomover-se logo após o nascimento. Horas depois está correndo a mais de 20 Km/h

Page24

Exemplo: Robótica• Um robô móvel tem que decidir:

a) se entra em uma sala em busca de mais lixo ou

b) se volta para a estação onde recarregará sua bateria.

• O robô toma sua decisão com base na experiência passada, em quão fácil foi encontrar estações de recarga no passado.

Page25

Similaridades Entre Exemplos Vistos

• Estes exemplos e muitos outros apresentam características comuns– Todos envolvem interação entre um

agente de tomada-de-decisão e o ambiente

– Um agente que procura atingir um ou mais objetivos

– Ambiente incerto

Page26

Similaridades Entre Exemplos Vistos

• Estes exemplos e muitos outros apresentam características comuns

– As ações do agente afetam o estado futuro do ambiente

– A ação correta deve levar em consideração consequências indiretas e retardadas, requerendo predição e planejamento

Page27

Outras Questões• Em todos os exemplos anteriores, os efeitos

das ações não podem ser perfeitamente antecipados; portanto, o agente deve monitorar o ambiente frequentemente e reagir apropriadamente

Plano a

Plano b

Plano c

Lucro

Prejuizo

Page28

Elementos Básicos de RL

• Além de agente e ambiente, pode-se identificar quatro subelementos fundamentais em RL:

– Política (de controle ou de tomada-de-decisão)

– Função ganho (reward function)

– Função valor (value function)

– Modelo do ambiente (opcional)

Page29

Política de Controle

• Define o comportamento do agente num dado momento• Em poucas palavras, uma política é uma função que

mapeia estados em açõesAção = (estado)

• Em alguns casos, a política pode ser simplesmente uma tabela; em outros casos ela pode envolver computações complexas

• Em geral políticas podem ser estocásticasNo estado s, a probabilidade de se tomar a ação a é

dada por (s,a)

Page30

Função Ganho• A função ganho define a meta em um problema RL• Em poucas palavras, ela mapeia um estado (ou par estado-

ação) do ambiente para um número, denominado ganho

• O objetivo do agente é maximizar o ganho total que ele recebe a longo termo

• Ganhos podem ser estocásticos

Estado stAção at

st+1

Ganho rt+1 = r(st,at,st+1)

Page31

Função Valor• Enquanto a função ganho indica os movimentos

promissores imediatos, a função valor estado indica o ganho total que pode ser acumulado no futuro se iniciarmos no estado em consideração

• A função valor indica o ganho potencial de longo termo de um estado, levando em conta os estados que sucedem o estado em consideração

V(s) = E[rt+1 + rt+2 + rt+3 + … : st = s]

Page32

Função Valor• Ganhos são de certa forma primários,

enquanto que valores são secundários– Sem ganho, valores não poderiam existir

• O propósito de estimarmos valores é obter maiores ganhos

• É com valores que nos preocupamos quanto tomamos decisões

Page33

Função Valor• Ganhos são basicamente dados diretamente

pelo ambiente, mas valores devem ser estimados e re-estimados, a partir das observações que o agente faz durante toda a sua vida

• De fato, um componente de quase todos os algoritmos de aprendizagem por reforço são métodos eficientes de estimar valores

Page34

Função Valor• Os métodos de RL a serem visto são estruturados na

estimação da função valor• Estimar V(s), s S, a partir das interações com

o ambiente• Definir política (s,a) a partir de V(s)

• Métodos como algoritmo genético e simulated annealing são algumas vezes utilizados para resolver problemas de RL, mas estes fazem uma busca direta no espaço de políticas sem fazer qualquer referência à função valor

• Sugerir (s,a) e simular seu desempenho• Modificar sugestão

Page35

Modelo• O modelo do ambiente imita o comportamento do

ambiente

• Dados um estado e uma ação, o modelo antecipa o próximo estado e o ganho

• Estado corrente no instante t: st• Ação a ser tomada: at• Modelo antecipa o próximo estado: P(st+1=s | st, at)

• Modelos são usados para planejamento, o que entendemos como qualquer método de decidir um curso de ação ao considerarmos futuras situações antes de encontrá-las

Page36

Modelo: Equações• O modelo é representado por:

– espaço de estados S– Conjunto de ações que podem ser tomadas

em cada estado: A(s) para s S– Probabilidade das transições: P(st+1=s | st,

at)– Probabilidade dos ganhos: P(rt=r | st+1, st, at)

st=a

st+1=c

st+1=b

ra,c

ra,b

Page37

Modelo: Simulador• Desenvolve-se um simulador do ambiente

– Dados o estado corrente st e a ação at, o simulador responde com o próximo estado st+1 e o ganho rt+1

Agente

Simulador

Ação atGanho

rt+1

Estado st

Page38

Um Exemplo Ilustrativo – Jogo da Velha

• Cenário:

- Um jogador experiente jamais perde neste jogo

- Considere um adversário imperfeito, que às vezes toma decisões incorretas

X

X

X X

O O

O

Page39

Jogo da Velha• Como poderíamos construir um jogador

artificial que “identifica” as imperfeições do oponente e aprende a maximizar as chances de vitória?

Page40

Jogo da Velha• Como poderíamos construir um jogador

artificial que “identifica” as imperfeições do oponente e aprende a maximizar as chances de vitória?– Apesar de ser um jogo simples, uma solução

satisfatória não pode ser obtida através de técnicas clássicas

– A técnica MiniMax, por exemplo, baseada na teoria dos jogos, assume um comportamento particular do oponente

Page41

Jogo da Velha• Como poderíamos construir um jogador

artificial que “identifica” as imperfeições do oponente e aprende a maximizar as chances de vitória?

– Métodos de otimização para problemas de decisão sequencial (programação dinâmica) são capazes de calcular uma solução ótima, mas exigem uma especificação completa do oponente, incluindo distribuições de probabilidades.

Page42

Jogo da Velha• O comportamento do adversário pode não ser

conhecido a priori, mas podemos identificá-lo a partir das interações

– Podemos jogar com o oponente e identificar o modelo, até um certo nível de confiança

– Aplica-se então técnicas de programação dinâmica para calcular a política de decisão ótima

– RL não é muito diferente dos passos acima

Page43

RL para Jogo da Velha• Passos para aplicar RL ao jogo da velha

– Criamos uma tabela de números, V(s), com uma entrada para cada estado s do jogo

– V(s) é a estimativa mais recente de vencermos o jogo a partir do estado s

– V(s) é o valor do estado s

– A tabela V representa a função valor

Page44

RL para Jogo da Velha• Um estado s1 é considerado melhor do que um

estado s2, se V(s1) > V(s2)

• Uma linha com três X’s tem probabilidade 1 de vitória—nós já ganhamos o jogo

• Uma linha com três O’s tem probabilidade 0 de vitória—o jogo já está perdido

• Para os demais estados, chutamos probabilidade ½ de vitória

Page45

RL para Jogo da Velha• Jogamos contra o oponente

– Na maioria das vezes selecionamos o movimento que nos leva ao estado com maior valor, ou seja, o estado com maior probabilidade de vitória (exploitation)

– Ocasionalmente, entretanto, selecionamos randomicamente dentre os demais movimentos possíveis (exploration)

Page46

RL para Jogo da Velha• Enquanto jogamos, atualizamos a tabela

V– Tentamos obter estimativas mais acuradas

das probabilidades de vencer

• Para que isso seja feito, atualizamos o valor do estado após cada movimento guloso (exploitation)– O valor corrente é ajustado para se tornar

mais próximo do último valor

Page47

RL para Jogo da Velha

S

S’’

Movimentodo Oponente

Page48

RL para Jogo da Velha

• V(s) V(s) + [V(s’) – V(s)]– é um número positivo pequeno, chamado

de passo, o qual influencia a aprendizagem

– A regra de atualização acima é chamada de método de aprendizagem por diferença temporal (temporal-difference learning method)

Page49

Fim• Obrigado pela presença!