DEPARTEMEN
TEKNIK INFORMATIKA
REINFORCEMENT
LEARNING
Kecerdasan Komputasional
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Artificial Intelligence
Machine Learning
Semi-
Supervised Unsupervised Reinforcement
Supervised
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Konsep Reinforcement Learning
• Konsep pembelajaran yang melibatkan interaksi Agent dengan lingkungan
(environment) untuk mencapai tujuan (goal)
• Agent: mempunyai tugas untuk mencapai tujuan (goal)
• Environment: memberikan umpan balik terhadap aksi yang dilakukan Agen
• State (s) merupakan kondisi atau situasi saat ini berdasarkan persepsi Agen
• Goal: memilih aksi yang memaksimalkan reward
• Reward (r) merupakan sebuah nilai untuk mengukur keberhasilan aksi dari
Agen
• Action (a) merupakan aksi yang akan dipilih Agen untuk mencapai tujuan
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Contoh Reinforcement Learning
• Cart-Pole Balancing
• Goal - Menyeimbangkan tiang diatas gerobak agar tetap berdiri
• State - Sudut tiang, kecepatan sudut, posisi gerobak, kecepatan
horisontal
• Actions - Gaya horisontal ke gerobak
• Reward – setiap step bernilai 1 jika tiang berdiri tegak
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Contoh Reinforcement Learning
• Bin Packing
• Goal - Mengambil barang dalam kotak dan meletakkan ke kontainer
• State - Piksel-piksel pada gambar yang tertangkap kamera
• Actions – Aksi-aksi yang dilakukan robot, misalnya mengambil atau
meletakkan barang
• Reward – Bernilai positif jika berhasil menempatkan barang dan bernilai
negatif jika sebaliknya
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Konsep Reinforcement Learning
OBSERVATIONS
State: 𝑠𝑠𝑡𝑡
Reward: 𝑟𝑟𝑡𝑡
State changes : 𝑠𝑠𝑡𝑡+1
Action: 𝑎𝑎𝑡𝑡 ENVIRONMENT
AGENT
ACTIONS
• st : state pada waktu t
• at : aksi pada waktu t
• rt : reward pada waktu t
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Konsep Reinforcement Learning
OBSERVATIONS
State: 𝑠𝑠𝑡𝑡
Reward: 𝑟𝑟𝑡𝑡
State changes : 𝑠𝑠𝑡𝑡+1
Action: 𝑎𝑎𝑡𝑡 ENVIRONMENT
AGENT
ACTIONS
Total Reward Discounted Total Reward
𝑅𝑅𝑡𝑡 = ∑∞
𝑖𝑖=𝑡𝑡 𝑟𝑟𝑖𝑖 = 𝑟𝑟𝑡𝑡 + 𝑟𝑟𝑡𝑡+1 + … + 𝑟𝑟𝑡𝑡+𝑛𝑛 + … 𝑅𝑅𝑡𝑡 = ∑∞ 𝑖𝑖 𝑡𝑡
𝑖𝑖=𝑡𝑡 𝛾𝛾 𝑟𝑟𝑖𝑖 = 𝛾𝛾 𝑟𝑟𝑡𝑡 +𝛾𝛾
𝑡𝑡+1 𝑟𝑟
𝑡𝑡+1 + … + 𝛾𝛾
𝑡𝑡+𝑛𝑛 𝑟𝑟
𝑡𝑡+𝑛𝑛 + …
𝛾𝛾: discount factors, 0 < 𝛾𝛾 < 1
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Definisi Q-function
Total Reward, 𝑅𝑅𝑡𝑡 , total semua reward dengan diskon dari waktu t
𝑅𝑅𝑡𝑡 = 𝑟𝑟𝑡𝑡 + 𝛾𝛾 1 𝑟𝑟𝑡𝑡+1 + 𝛾𝛾 2 𝑟𝑟𝑡𝑡+2 + …
𝛾𝛾: discount factors, 0 < 𝛾𝛾 < 1
Q-function menangkap expected total feature reward Agen pada
state s, yang melakukan aksi a tertentu
𝑄𝑄 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 = Ε 𝑅𝑅𝑡𝑡 |𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Bagaimana cara Agen memilih aksi dari Q-function?
𝑄𝑄 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 = Ε 𝑅𝑅𝑡𝑡 |𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡
Agen memerlukan suatu policy 𝝅𝝅 𝒔𝒔 untuk
Q-function memilih aksi terbaik pada state s
Strategi: memilih aksi yang memaksimalkan future reward
𝜋𝜋 ∗ 𝑠𝑠 = argmax 𝑄𝑄 𝑠𝑠, 𝑎𝑎
𝑎𝑎
𝜋𝜋 ∗ optimal policy 𝝅𝝅
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Pendekatan Reinforcement Learning
• Policy-based RL
• Memilih secara langsung optimal policy 𝜋𝜋 ∗
• Memilih policy yang mencapai maximum future reward
• Value-based RL
• Mengestimasi optimal value function 𝑄𝑄∗ (s,a)
• Maximum value yang tercapai oleh policy
• Model-based RL
• Membangun transition model pada sebuah environment
• Perencanaan berbasis model
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Desain Algoritma Reinforcement Learning
Fit Model
Generate
Samples Improve the
policy
(Run Policy)
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Policy-based Reinforcement Learning
Fit Model
(Estimate 𝑉𝑉 𝑠𝑠 or 𝑄𝑄 𝑠𝑠, 𝑎𝑎
Value)
Generate
Samples Improve the 𝜋𝜋 ∗ 𝑠𝑠 = argmax 𝑄𝑄 𝑠𝑠, 𝑎𝑎
policy 𝑎𝑎
(Run Policy)
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Value-based Reinforcement Learning
𝑅𝑅𝑡𝑡 = � 𝛾𝛾 𝑡𝑡 𝑟𝑟(𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 )
Fit Model
𝑡𝑡
Generate
Samples Improve the 𝑄𝑄𝑡𝑡+1 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 = 𝑄𝑄𝑡𝑡 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 + 𝛼𝛼𝛻𝛻𝑄𝑄 Ε 𝑅𝑅𝑡𝑡 |𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡
policy
(Run Policy)
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Model-based Reinforcement Learning
Fit Model 𝑝𝑝 𝑠𝑠𝑡𝑡+1 |𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡
a. Menggunakan model (no policy)
Generate • Monte Carlo tree search
Samples Improve the b. Backpropagate gradients policy
policy c. Menggunakan model untuk
(Run Policy)
pembelajaran value function
• Dynamic programming
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Q-Learning
Menggunakan policy untuk mengestimasi Q yang memaksimalkan future
reward:
• Aproksimasi Q* (persamaan Bellman optimality)
• Update setiap pasangan (s, a)
Learning rate Discount factor
𝑄𝑄𝑡𝑡+1 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 = 𝑄𝑄𝑡𝑡 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 +∝ 𝑅𝑅𝑡𝑡+1 + 𝛾𝛾 max 𝑄𝑄𝑡𝑡 𝑠𝑠𝑡𝑡+1 , 𝑎𝑎 − 𝑄𝑄𝑡𝑡 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡
𝑎𝑎
New state Old state Reward
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Q-Learning: Value Iteration
Learning rate Discount factor
𝑄𝑄𝑡𝑡+1 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 = 𝑄𝑄𝑡𝑡 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡 +∝ 𝑅𝑅𝑡𝑡+1 + 𝛾𝛾 max 𝑄𝑄𝑡𝑡 𝑠𝑠𝑡𝑡+1 , 𝑎𝑎 − 𝑄𝑄𝑡𝑡 𝑠𝑠𝑡𝑡 , 𝑎𝑎𝑡𝑡
𝑎𝑎
New state Old state Reward
Q-Table
Sumber: Lex Fridman, Deep Reinforcement Learning, MIT Course 2018 : Introduction to Deep Learning
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Contoh Penerapan Q-Learning
• Cart-Pole Balancing import gym Tanpa Q-Learning
• Goal - Menyeimbangkan tiang env = [Link]('CartPole-v0')
diatas gerobak agar tetap berdiri for i_episode in range(20):
• State - Sudut tiang, kecepatan observation = [Link]()
sudut, posisi gerobak, kecepatan for t in range(100):
horisontal
[Link]()
• Actions - Gaya horisontal ke
print(observation)
gerobak
action = env.action_space.sample() Dengan Q-Learning
• Reward - setiap step bernilai 1 jika
tiang berdiri tegak observation, reward, done, info =
[Link](action)
if done:
print("Episode finished after {}
timesteps".format(t+1))
break
[Link]()
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
Kelemahan Q-Learning
Value Iteration tidak praktis:
• State atau action yang terbatas
• Tidak dapat mengeneralisir state yang belum
diketahui
Contoh Breakout game
State: screen pixels
• Ukuran gambar: 𝟖𝟖𝟒𝟒×𝟖𝟖𝟒𝟒(resized) 𝟐𝟐𝟓𝟓𝟔𝟔𝟖𝟖𝟒𝟒×𝟖𝟖𝟒𝟒×𝟒𝟒 rows
• Consecutive 4 images pada Q-table!
• Grayscale with 256 gray level
Solusi pendekatan Deep Q Learning!
[Link]/informatika INSTITUT TEKNOLOGI SEPULUH NOPEMBER, Surabaya - Indonesia
- TERIMA KASIH -