IFT-4201 / IFT-7201
Apprentissage par Renforcement
Reinforcement Learning
Audrey Durand
Boltzmann/Softmax
Rappel : Le compromis exploration/exploitation
Espérance de récompense
Espérance de récompense
associée à l’action optimale k⋆ associée à l’action k Gap de sous-optimalité de l’action k
T T K T K
∑ [∑ ] ∑ [ ∑ ] ∑
R(T) = μ⋆ − rt = (μ⋆ − μk) [kt = k] = Δk [Nk(T)]
t=1 t=1 k=1 t=1 k=1
Récompense obtenue au temps t
Action choisie au temps t Nombre de sélections de l’action k
(donc après avoir joué l’action kt) jusqu’au temps T (inclusivement)
Simultanément :
• Découvrir les (Δk)k=1…K
Exploration
• Sélectionner k⋆aussi souvent que possible Exploitation
𝔼
𝔼
𝕀
𝔼
Rappel : Exploration uniforme
Constante d’exploration ε ∈ [0,1] assez petit (e.g. ε = 0.1)
ε-greedy
Estimation empirique de la moyenne
• Jouer chaque action une fois
des récompenses de l’action k après
t − 1 pas de temps (inclusivement)
• Pour t > K :
• Explorer avec probabilité ε : Sélectionner kt ∼ ({1,2,…, K})
• Exploiter avec probabilité 1 − ε : Sélectionner kt = arg maxk μk̂ (t − 1)
⇒ Probabilité d’explorer l’action k dépendante de μk̂ (t − 1)?
𝒰
Exploration en fonction du potentiel
Taux d’apprentissage (learning rate) η ≥0
Boltzmann / Softmax
• Jouer chaque action une fois
• Pour t > K :
ημk̂ (t−1)
e
Sélectionner l’action k avec probabilité ℙ[kt = k] = K
∑k=1 e ημk̂ (t−1)
Expérience 1
K = 2 actions, con guration μ = (0.5, 0.9)
ημk̂ (t−1) ημk
Xk,t ∼ ℬ(μk)
e e
ℙ[kt = k] = K
→ K
50 répétitions, T = 500 ∑k=1 e ημk̂ (t−1) ∑k=1 e ημk
η=1 η = 10 η = 20
fi
Expérience 2
• K = 2 actions
• 50 instances ⇒ μk ∼ (0,1) ∀k
• rt ∼ ℬ(μkt) • T = 500 pas de temps
η=1 η = 10 η = 20
𝒰
Expérience 2
Pseudo-regret cumulatif
• K = 2 actions
• 50 instances ⇒ μk ∼ (0,1) ∀k
• rt ∼ ℬ(μkt) • T = 500 pas de temps
η xe
𝒰
fi
Exploration en fonction du potentiel
Taux d’apprentissage ηt ≥ 0 croissant avec t
Boltzmann / Softmax
• Jouer chaque action une fois
• Pour t > K :
ηt μk̂ (t−1)
e
Sélectionner l’action k avec probabilité ℙ[kt = k] =
K
∑k=1 e ηt μk̂ (t−1)
( mink≠k⋆ Δk )
ln(t)
⇒ Garanties de pseudo-regret cumulatif quasi-optimal requièrent ηt ≥ O
[Cesa-Bianchi et al., 2017]
Toujours dans le contexte de l’expérience 2
ln(t)
ηt = c
mink≠k⋆ Δk
• K = 2 actions
• 50 instances ⇒ μk ∼ (0,1) ∀k
• rt ∼ ℬ(μkt) • T = 500 pas de temps
c = 0.01 c = 0.1 c=1
𝒰
Toujours dans le contexte de l’expérience 2
t
ηt = c
mink≠k⋆ Δk
• K = 2 actions
• 50 instances ⇒ μk ∼ (0,1) ∀k
• rt ∼ ℬ(μkt) • T = 500 pas de temps
c = 0.01 c = 0.1 c=1
𝒰
Toujours dans le contexte de l’expérience 2
Pseudo-regret cumulatif
• K = 2 actions
• 50 instances ⇒ μk ∼ (0,1) ∀k
• rt ∼ ℬ(μkt) • T = 500 pas de temps
ln(t) t
ηt = c ηt = c
η xe mink≠k⋆ Δk mink≠k⋆ Δk
𝒰
fi