Algoritmo Q-Learning

Fabrı́cio Barth

Insper Instituto de Ensino e Pesquisa

Fevereiro de 2025

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 1 / 21
 Polı́tica de Controle

A polı́tica de controle desejada é aquela que maximiza os reforços

(reward) acumulados ao longo do tempo pelo agente.
Em tese, é a polı́tica que faz o agente percorrer o melhor caminho.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 2 / 21
 Reward acumulado (1/4)

O valor de um estado final leva-se em consideração apenas o reforço:

V (sn ) = rn .

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 3 / 21
 Reward acumulado (2/4)

O V (s2 ) será a soma de r2 com o V (s3 ).

Considerando o fator de desconto γ, temos: V (s2 ) = r2 + γ 3 V (s3 ).
O fator de desconto: 0 ≤ γ < 1

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 4 / 21
 Reward acumulado (3/4)

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 5 / 21
 Reward acumulado (4/4)

Desta forma, temos:

V (s0 ) = r0 + γV (s1 )
V (s0 ) = r0 + γr1 + γ 2 V (s2 )
V (s0 ) = r0 + γr1 + γ 2 r2 + γ 3 V (s3 )
V (s0 ) = r0 + γr1 + γ 2 r2 + γ 3 r3

Ou melhor:

V (s0 ) = r0 + γr1 + γ 2 r2 + γ 3 r3 · · · + γ n rn

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 6 / 21
 Fator de desconto γ

O fator de desconto (γ) é um hiperparâmetro que consiste em um

número entre 0 e 1 que define a importância das recompensas futuras
em relação a atual (0 ≤ γ < 1).
Valores mais próximos ao 0 dão mais importância a recompensas
imediatas enquanto os mais próximos de 1 tentarão manter a
importância de recompensas futuras.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 7 / 21
 Algoritmo Q-Learning

O algoritmo Q-Learning é um algoritmo do tipo value-based que

estimam a expectativa de retorno de uma ação a sendo executada em
um estado s de acordo com uma polı́tica π: Q π (s, a).
Para que agente possa identificar uma polı́tica de controle ótima este
agente precisa criar um mapeamento entre estados (S) e ações (A).
Desta forma o agente consegue identificar qual é a ação a com maior
retorno em um determinado estado s.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 8 / 21
 Algoritmo Q-Learning

Este mapeamento é representado por uma função Q(S, A) onde S são

todos os estados possı́veis (s1 , s2 , · · · ) e onde A são todas as ações
possı́veis (a1 , a2 , · · · )

Q-table a1 a2 a3 a4
s1
s2
···
sn

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 9 / 21
 Algoritmo Q-Learning

Como é que o agente pode saber quais são as melhores ações em cada
estado?

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 10 / 21
 Algoritmo Q-Learning

Como é que o agente pode saber quais são as melhores ações em cada
estado?

A ideia é fazer com que o agente aprenda a função de mapeamento

Q(S, A). Ou seja, que seja capaz de identificar qual é a melhor ação
para cada estado através das suas experiências.
Testando infinitas vezes o ambiente. Ou seja, testando muitas vezes
as combinações entre estados (S) e ações (A).

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 10 / 21
 Algoritmo Q-Learning

function Q-Learning(env, γ, α, episódios)

inicializar os valores de Q(s, a) arbitrariamente
for todos os episódios do
inicializar s a partir de env
repeat
escolher uma ação a para um estado s
executar a ação a
observar a recompensa r e o novo estado s ′
Q(s, a) ← atualizando a partir das experiências
s ← s′
until s ser um estado final
end for
return Q(s, a)
Poderı́amos simplesmente: Q(s, a) ← r . Será que funciona?

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 11 / 21
 Algoritmo Q-Learning

function Q-Learning(env, γ, α, episódios)

inicializar os valores de Q(s, a) arbitrariamente
for todos os episódios do
inicializar s a partir de env
repeat
escolher uma ação a para um estado s
executar a ação a
observar a recompensa r e o novo estado s ′
Q(s, a) ← Q(s, a) + α[r + γ maxA′ Q(s ′ , A′ ) − Q(s, a)]
s ← s′
until s ser um estado final
end for
return Q(s, a)
O valor de Q(s, a) não é simplesmente o valor imediato do r . Ele deve levar em
consideração toda a trajetória (Equação de Bellman).

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 12 / 21
 Algoritmo Q-Learning: hiperparâmetro α

α é a taxa de aprendizado (0 < α ≤ 1), quanto maior, mais valor dá

ao novo aprendizado.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 13 / 21
 Que ação escolher?

function Q-Learning(env, α, γ, episódios)

inicializar os valores de Q(s, a) arbitrariamente
for todos os episódios do
inicializar s a partir de env
repeat
escolher uma ação a para um estado s
executar a ação a
observar a recompensa r e o novo estado s ′
Q(s, a) ← Q(s, a) + α[r + γ maxA′ Q(s ′ , A′ ) − Q(s, a)]
s ← s′
until s ser um estado final
end for
return Q(s, a)

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 14 / 21
 Exploration vs Exploitation

A polı́tica que o agente utiliza para escolher uma ação a para um

estado s não interfere no aprendizado da Q-table.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 15 / 21
 Exploration vs Exploitation

A polı́tica que o agente utiliza para escolher uma ação a para um

estado s não interfere no aprendizado da Q-table.
No entanto, para que o algoritmo Q-learning possa convergir para um
determinado problema é necessário que o algoritmo visite pares de
ação-estado muitas (infinitas) vezes.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 15 / 21
 Exploration vs Exploitation

A polı́tica que o agente utiliza para escolher uma ação a para um

estado s não interfere no aprendizado da Q-table.
No entanto, para que o algoritmo Q-learning possa convergir para um
determinado problema é necessário que o algoritmo visite pares de
ação-estado muitas (infinitas) vezes.
Por isso, que a escolha de determinada ação em um estado poderia
ser feita de forma aleatória.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 15 / 21
 Exploration vs Exploitation

A polı́tica que o agente utiliza para escolher uma ação a para um

estado s não interfere no aprendizado da Q-table.
No entanto, para que o algoritmo Q-learning possa convergir para um
determinado problema é necessário que o algoritmo visite pares de
ação-estado muitas (infinitas) vezes.
Por isso, que a escolha de determinada ação em um estado poderia
ser feita de forma aleatória.
Porém, normalmente se utiliza uma polı́tica que inicialmente escolhe
aleatoriamente as ações, e, à medida que vai aprendendo, passa a
utilizar cada vez mais as decisões determinadas pela polı́tica derivada
de Q.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 15 / 21
 Exploration vs Exploitation

A polı́tica que o agente utiliza para escolher uma ação a para um

estado s não interfere no aprendizado da Q-table.
No entanto, para que o algoritmo Q-learning possa convergir para um
determinado problema é necessário que o algoritmo visite pares de
ação-estado muitas (infinitas) vezes.
Por isso, que a escolha de determinada ação em um estado poderia
ser feita de forma aleatória.
Porém, normalmente se utiliza uma polı́tica que inicialmente escolhe
aleatoriamente as ações, e, à medida que vai aprendendo, passa a
utilizar cada vez mais as decisões determinadas pela polı́tica derivada
de Q.
Esta estratégia inicia explorando (tentar uma ação mesmo que ela
não tenha o maior valor de Q) e termina escolhendo a ação que tem
o maior valor de Q (exploitation).

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 15 / 21
 Exemplo de função para escolha de ações

A escolha de uma ação para um estado é dada pela função:

function escolha(s, ϵ): a

rv = random (0 < rv ≤ 1)
if rv < ϵ then
return uma ação α aleatória em A
end if
return maxa Q(s, a)

O fator de exploração ϵ (0 ≤ ϵ ≤ 1) inicia com um valor alto (0.7, por

exemplo) e, conforme a simulação avança, diminiu: ϵ ← ϵ × ϵdec , onde
ϵdec = 0.99

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 16 / 21
 Epsilon

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 17 / 21
 Algoritmo Q-Learning

function Q-Learning(env, α, γ, ϵ, ϵmin , ϵdec , episódios)

inicializar os valores de Q(s, a) arbitrariamente
for todos os episódios do
inicializar s a partir de env
repeat
a ← escolha(s, ϵ)
s ′ , r ← executar a ação a no env
Q(s, a) ← Q(s, a) + α[r + γ maxA′ Q(s ′ , A′ ) − Q(s, a)]
s ← s′
until s ser um estado final
if ϵ > ϵmin then ϵ ← ϵ × ϵdec
end for
return Q

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 18 / 21
 Atividade de implementação

Implementando o algoritmo Q-Learning

O objetivo desta atividade é implementar uma versão do algoritmo
Q-Learning

Atividades
Siga o roteiro descrito em
[Link] q learning/ Link

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 19 / 21
 Atividade de implementação

Hiperparâmetros e seleção das ações

O objetivo desta atividade é compreender o funcionamento e impacto dos
hiperparâmetros de α, γ e dos conceitos de exploration e exploitation.

Atividades
Siga o roteiro descrito em
[Link] x hyperparameters/ Link

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 20 / 21
 Material de consulta

Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement

Learning: An Introduction. A Bradford Book, Cambridge, MA, USA.
Capı́tulo 6.5
Watkins, C.J.C.H., Dayan, P. Q-Learning. Machine Learning 8,
279–292 (1992). Link
Aurélien Géron. Hands-On Machine Learning with Scikit-Learn,
Keras, and TensorFlow, 2nd Edition, 2019.

Fabrı́cio Barth (Insper Instituto de Ensino e Pesquisa) Algoritmo Q-Learning Fevereiro de 2025 21 / 21