Pengantar Q-Learning: Tutorial untuk Pemula

Reinforcement learning (RL) adalah bagian dari ekosistem machine learning di mana agen belajar dengan berinteraksi dengan lingkungan untuk memperoleh strategi optimal dalam mencapai tujuan. Ini cukup berbeda dari algoritma machine learning terawasi, yang mengharuskan kita memuat dan memproses data. Reinforcement learning tidak memerlukan data. Sebagai gantinya, ia belajar dari lingkungan dan sistem hadiah untuk membuat keputusan yang lebih baik.

Misalnya, dalam gim video Mario, jika karakter melakukan aksi acak (mis. bergerak ke kiri), berdasarkan aksi itu, ia mungkin menerima hadiah. Setelah mengambil aksi, agen (Mario) berada pada keadaan baru, dan proses ini berulang sampai karakter gim mencapai akhir tahap atau mati. 

Episode ini akan berulang berkali-kali hingga Mario belajar menavigasi lingkungan dengan memaksimalkan hadiah. 

Gambar oleh Penulis

Kita dapat memecah reinforcement learning menjadi lima langkah sederhana:

1. Agen berada pada keadaan nol dalam suatu lingkungan.
2. Agen akan mengambil sebuah aksi berdasarkan strategi tertentu.
3. Agen akan menerima hadiah atau hukuman berdasarkan aksi tersebut.
4. Dengan belajar dari langkah sebelumnya dan mengoptimalkan strategi. 
5. Proses akan berulang sampai strategi optimal ditemukan. 

Pelajari lebih lanjut dengan membaca tutorial kami, sebuah Pengantar Reinforcement Learning. Anda akan mengeksplorasi lebih jauh cara kerja reinforcement learning dengan contoh kode. 

Dalam tutorial ini, kita akan mempelajari Q-learning dan memahami mengapa kita memerlukan Deep Q-learning. Selain itu, kita akan belajar membuat dan melatih algoritma Q-learning dari awal menggunakan Numpy dan OpenAI Gym.

Catatan: Jika Anda baru dalam machine learning, kami menyarankan Anda mengikuti jalur karier Machine Learning Scientist with Python untuk lebih memahami Reinforcement learning dan Q-Learning. 

Apa itu Q-Learning?

Q-learning adalah algoritma tanpa model, berbasis nilai, dan off-policy yang akan menemukan rangkaian aksi terbaik berdasarkan keadaan saat ini dari agen. Huruf “Q” adalah singkatan dari quality (kualitas). Kualitas merepresentasikan seberapa berharga suatu aksi dalam memaksimalkan hadiah di masa depan.  

Algoritma berbasis model menggunakan fungsi transisi dan hadiah untuk memperkirakan kebijakan optimal dan membuat model. Sebaliknya, algoritma tanpa model mempelajari konsekuensi dari aksinya melalui pengalaman tanpa fungsi transisi dan hadiah. 

Metode berbasis nilai melatih fungsi nilai untuk mempelajari keadaan mana yang lebih berharga dan mengambil aksi. Di sisi lain, metode berbasis kebijakan melatih kebijakan secara langsung untuk mempelajari aksi mana yang harus diambil pada keadaan tertentu.

Pada off-policy, algoritma mengevaluasi dan memperbarui kebijakan yang berbeda dari kebijakan yang digunakan untuk mengambil aksi. Sebaliknya, algoritma on-policy mengevaluasi dan meningkatkan kebijakan yang sama yang digunakan untuk mengambil aksi.  

Terminologi Kunci dalam Q-learning

Sebelum kita membahas bagaimana Q-learning bekerja, kita perlu mempelajari beberapa terminologi berguna untuk memahami dasar-dasar Q-learning. 

• States(s): posisi saat ini dari agen di lingkungan. 
• Action(a): langkah yang diambil agen pada keadaan tertentu. 
• Rewards: untuk setiap aksi, agen menerima hadiah dan penalti. 
• Episodes: akhir tahap, di mana agen tidak dapat mengambil aksi baru. Ini terjadi ketika agen telah mencapai tujuan atau gagal. 
• Q(S_t+1, a): nilai Q optimal yang diharapkan saat melakukan aksi pada keadaan tertentu. 
• Q(S_t, A_t): estimasi saat ini dari Q(S_t+1, a).
• Q-Table: tabel yang dipelihara agen berisi himpunan keadaan dan aksi.
• Temporal Differences (TD): digunakan untuk memperkirakan nilai yang diharapkan dari Q(S_t+1, a) dengan menggunakan keadaan dan aksi saat ini serta keadaan dan aksi sebelumnya. 

Bagaimana Q-Learning Bekerja?

Kita akan mempelajari secara rinci cara kerja Q-learning dengan menggunakan contoh danau beku. Dalam lingkungan ini, agen harus menyeberangi danau beku dari awal hingga tujuan, tanpa jatuh ke lubang. Strategi terbaik adalah mencapai tujuan dengan mengambil jalur terpendek. 

Gif oleh Penulis

Q-Table

Agen akan menggunakan Q-table untuk mengambil aksi terbaik berdasarkan hadiah yang diharapkan untuk setiap keadaan di lingkungan. Sederhananya, Q-table adalah struktur data berupa himpunan aksi dan keadaan, dan kita menggunakan algoritma Q-learning untuk memperbarui nilai-nilai dalam tabel. 

Q-Function

Q-function menggunakan persamaan Bellman dan menerima state(s) dan action(a) sebagai masukan. Persamaan ini menyederhanakan perhitungan nilai keadaan dan nilai keadaan-aksi. 

Gambar dari freecodecamp.org

Algoritma Q-learning

Gambar oleh Penulis

Inisialisasi Q-Table

Pertama, kita akan menginisialisasi Q-table. Kita akan membuat tabel dengan kolom berdasarkan jumlah aksi dan baris berdasarkan jumlah keadaan.

Pada contoh kita, karakter dapat bergerak ke atas, bawah, kiri, dan kanan. Kita memiliki empat aksi yang mungkin dan empat keadaan (mulai, diam, jalur salah, dan akhir). Anda juga bisa menganggap jalur salah sebagai jatuh ke lubang. Kita akan menginisialisasi Q-Table dengan nilai 0. 

Gambar oleh Penulis

Pilih Aksi

Langkah kedua cukup sederhana. Di awal, agen akan memilih mengambil aksi acak (bawah atau kanan), dan pada putaran kedua, ia akan menggunakan Q-Table yang telah diperbarui untuk memilih aksi. 

Lakukan Aksi

Memilih aksi dan melakukan aksi akan berulang berkali-kali hingga loop pelatihan berhenti. Aksi dan keadaan pertama dipilih menggunakan Q-Table. Dalam kasus kita, semua nilai Q-Table bernilai nol. 

Lalu, agen akan bergerak ke bawah dan memperbarui Q-Table menggunakan persamaan Bellman. Pada setiap langkah, kita akan memperbarui nilai di Q-Table dan juga menggunakannya untuk menentukan langkah terbaik. 

Awalnya, agen berada dalam mode eksplorasi dan memilih aksi acak untuk menjelajahi lingkungan. Strategi Epsilon Greedy adalah metode sederhana untuk menyeimbangkan eksplorasi dan eksploitasi. Epsilon menyatakan probabilitas memilih untuk mengeksplorasi dan mengeksploitasi saat peluang eksplorasi lebih kecil. 

Pada awalnya, laju epsilon lebih tinggi, artinya agen dalam mode eksplorasi. Sembari menjelajah lingkungan, epsilon menurun, dan agen mulai mengeksploitasi lingkungan. Selama eksplorasi, pada setiap iterasi, agen menjadi lebih percaya diri dalam memperkirakan nilai Q

Gambar oleh Penulis

Pada contoh danau beku, agen tidak mengetahui lingkungan, sehingga ia mengambil aksi acak (bergerak ke bawah) untuk memulai. Seperti yang terlihat pada gambar di atas, Q-Table diperbarui menggunakan persamaan Bellman.

Mengukur Hadiah

Setelah mengambil aksi, kita akan mengukur hasil dan hadiahnya. 

• Hadiah untuk mencapai tujuan adalah +1
• Hadiah untuk mengambil jalur yang salah (jatuh ke lubang) adalah 0
• Hadiah untuk diam atau bergerak di danau beku juga 0. 

Perbarui Q-Table

Kita akan memperbarui fungsi Q(S_t, A_t) menggunakan persamaan. Ia menggunakan estimasi nilai Q episode sebelumnya, laju pembelajaran, dan galat Temporal Differences. Galat Temporal Differences dihitung menggunakan hadiah langsung, diskonto maksimum hadiah masa depan yang diharapkan, dan estimasi nilai Q sebelumnya. 

Proses ini diulangi berkali-kali hingga Q-Table diperbarui dan fungsi nilai Q dimaksimalkan. 

Gambar oleh Penulis | Visual Persamaan dari Thomas Simonini

Pada awalnya, agen menjelajahi lingkungan untuk memperbarui Q-table. Dan ketika Q-Table siap, agen akan mulai mengeksploitasi dan mengambil keputusan yang lebih baik. 

Gambar oleh Penulis

Dalam kasus danau beku, agen akan belajar mengambil jalur terpendek untuk mencapai tujuan dan menghindari melompat ke lubang. 

Tutorial Python Q-Learning 

Pada bagian ini, kita akan membangun model Q-learning dari awal menggunakan lingkungan Gym, Pygame, dan Numpy. Tutorial Python ini adalah versi modifikasi dari Notebook oleh Thomas Simonini. Ini mencakup inisialisasi lingkungan dan Q-Table, mendefinisikan kebijakan greedy, menetapkan hiperparameter, membuat dan menjalankan loop pelatihan dan evaluasi, serta memvisualisasikan hasil.   

Jika Anda menghadapi masalah saat membuat dan menjalankan loop pelatihan, Anda dapat memeriksa sumber kode beserta keluarannya.   

Menyiapkan Lingkungan

Menyiapkan Tampilan Virtual

Pertama kita akan memasang semua dependensi untuk menghasilkan video ulang (Gif). Kita memerlukan layar virtual (pyvirtualdisplay) untuk merender lingkungan dan merekam frame. 

Catatan: dengan menggunakan %%capture kita menekan keluaran sel Jupyter. 

%%capture
!pip install pyglet==1.5.1
!apt install python-opengl
!apt install ffmpeg
!apt install xvfb
!pip3 install pyvirtualdisplay

# Virtual display
from pyvirtualdisplay import Display

virtual_display = Display(visible=0, size=(1400, 900))
virtual_display.start()

Instal dependensi

Berikutnya kita akan memasang dependensi yang akan membantu kita membuat, menjalankan, dan mengevaluasi loop pelatihan. 

• gym: Digunakan untuk menginisialisasi lingkungan FrozenLake-v1.
• pygame: Digunakan untuk UI FrozenLake-v1.
• numPy: Digunakan untuk membuat dan menangani Q-table.

%%capture
!pip install gym==0.24
!pip install pygame
!pip install numpy

!pip install imageio imageio_ffmpeg

Impor paket

Sekarang kita akan mengimpor pustaka yang diperlukan. 

• Imageio digunakan untuk membuat animasi. 
• tqdm digunakan untuk bilah progres. 

import numpy as np
import gym
import random
import imageio
from tqdm.notebook import trange

Lingkungan Gym Frozen Lake 

Kita akan membuat lingkungan 4x4 non-slippery menggunakan pustaka gym Frozen Lake. 

• Ada dua versi grid, “4x4” dan “8x8”.
• Jika is_slippery=True, agen mungkin tidak bergerak ke arah yang diinginkan karena sifat licin danau beku. 

Setelah menginisialisasi lingkungan, kita akan melakukan analisis lingkungan. 

env = gym.make("FrozenLake-v1",map_name="4x4",is_slippery=False)

print("Observation Space", env.observation_space)
print("Sample observation", env.observation_space.sample()) # display a random observation

Ada 16 ruang unik di lingkungan yang ditampilkan pada posisi acak. 

Observation Space Discrete(16)
Sample observation 15

Mari cari tahu jumlah aksi dan tampilkan aksi acak. 

Ruang aksi:

• 0: bergerak ke kiri
• 1: bergerak ke bawah
• 2: bergerak ke kanan
• 3: bergerak ke atas

Fungsi hadiah:

• Mencapai tujuan: +1
• Jatuh ke lubang: 0
• Tetap di danau beku: 0

print("Action Space Shape", env.action_space.n)
print("Action Space Sample", env.action_space.sample())

Action Space Shape 4
Action Space Sample 1

Buat dan Inisialisasi Q-table

Q-Table memiliki kolom sebagai aksi, dan baris sebagai keadaan. Kita dapat menggunakan OpenAI Gym untuk mengetahui ruang aksi dan ruang keadaan. Kita kemudian akan menggunakan informasi ini untuk membuat Q-Table. 

state_space = env.observation_space.n
print("There are ", state_space, " possible states")

action_space = env.action_space.n
print("There are ", action_space, " possible actions")

There are  16  possible states
There are  4  possible actions

Untuk menginisialisasi Q-Table, kita akan membuat array Numpy dari state_space dan actions space. Kita akan membuat array 16 X 4. 

def initialize_q_table(state_space, action_space):
  Qtable = np.zeros((state_space, action_space))
  return Qtable

Qtable_frozenlake = initialize_q_table(state_space, action_space)

Kebijakan epsilon-greedy

Pada bagian sebelumnya, kita telah mempelajari strategi epsilon greedy yang menangani trade-off eksplorasi dan eksploitasi. Dengan probabilitas 1 - ɛ, kita melakukan eksploitasi, dan dengan probabilitas ɛ, kita melakukan eksplorasi. 

Pada epsilon_greedy_policy kita akan:

1. Menghasilkan bilangan acak antara 0 hingga 1.
2. Jika bilangan acak lebih besar dari epsilon, kita akan melakukan eksploitasi. Artinya agen akan mengambil aksi dengan nilai tertinggi pada keadaan tertentu.
3. Jika tidak, kita akan melakukan eksplorasi (Mengambil aksi acak). 

def epsilon_greedy_policy(Qtable, state, epsilon):
  random_int = random.uniform(0,1)
  if random_int > epsilon:
    action = np.argmax(Qtable[state])
  else:
    action = env.action_space.sample()
  return action

Definisikan kebijakan greedy

Seperti yang kini kita tahu, Q-learning adalah algoritma off-policy yang berarti kebijakan untuk mengambil aksi dan kebijakan untuk memperbarui fungsi berbeda. 

Pada contoh ini, kebijakan Epsilon Greedy adalah kebijakan bertindak, dan kebijakan Greedy adalah kebijakan pembaruan. 

Kebijakan Greedy juga akan menjadi kebijakan final ketika agen telah dilatih. Ini digunakan untuk memilih nilai keadaan dan aksi tertinggi dari Q-Table.

def greedy_policy(Qtable, state):
  action = np.argmax(Qtable[state])
  return action

Hiperparameter model

Hiperparameter ini digunakan dalam loop pelatihan, dan penyetelan yang baik akan memberi Anda hasil yang lebih baik. 

Agen perlu mengeksplorasi cukup banyak ruang keadaan untuk mempelajari pendekatan nilai yang baik; kita perlu memiliki peluruhan epsilon yang progresif. Jika tingkat peluruhan tinggi, agen bisa terjebak karena belum mengeksplorasi cukup banyak ruang keadaan.

• Ada 10.000 episode pelatihan dan 100 episode evaluasi.
• Learning rate adalah 0,7.
• Kita menggunakan "FrozenLake-v1" sebagai lingkungan dengan 99 langkah maksimum per episode.
• gamma (discount rate) adalah 0,95.
• eval_seed: seed evaluasi untuk lingkungan.
• Probabilitas eksplorasi epsilon pada awalnya 1,0, dan probabilitas minimum akan 0,05.
• Tingkat peluruhan eksponensial untuk probabilitas epsilon adalah 0,0005.

# Training parameters
n_training_episodes = 10000
learning_rate = 0.7        

# Evaluation parameters
n_eval_episodes = 100      

# Environment parameters
env_id = "FrozenLake-v1"   
max_steps = 99             
gamma = 0.95               
eval_seed = []             

# Exploration parameters
max_epsilon = 1.0           
min_epsilon = 0.05           
decay_rate = 0.0005           

Pelatihan Model 

Dalam loop pelatihan, kita akan:

1. Membuat loop untuk episode pelatihan.
2. Pertama-tama kita akan menurunkan epsilon. Karena kita memerlukan eksplorasi yang makin berkurang dan lebih banyak eksploitasi pada setiap episode. 
3. Reset lingkungan.
4. Membuat loop bersarang untuk langkah maksimum.
5. Memilih aksi menggunakan kebijakan epsilon greedy. 
6. Mengambil aksi (A_t) dan mengamati hadiah yang diharapkan (R_t+1) dan keadaan (S_t+1).
7. Mengambil aksi (a) dan mengamati keadaan hasil (s') dan hadiah (r).
8. Memperbarui fungsi Q menggunakan rumus. 
9. Jika done= True, akhiri episode dan hentikan loop.
10. Terakhir, ubah keadaan saat ini ke keadaan baru. 
11. Setelah menyelesaikan semua episode pelatihan, fungsi akan mengembalikan Q-Table yang diperbarui. 

def train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable):
  for episode in trange(n_training_episodes):
 
    epsilon = min_epsilon + (max_epsilon - min_epsilon)*np.exp(-decay_rate*episode)
    # Reset the environment
    state = env.reset()
    step = 0
    done = False

    # repeat
    for step in range(max_steps):
   
      action = epsilon_greedy_policy(Qtable, state, epsilon)

   
      new_state, reward, done, info = env.step(action)

   
      Qtable[state][action] = Qtable[state][action] + learning_rate * (reward + gamma * np.max(Qtable[new_state]) - Qtable[state][action])

      # If done, finish the episode
      if done:
        break
     
      # Our state is the new state
      state = new_state
  return Qtable

Diperlukan waktu 3 detik untuk menyelesaikan 10.000 episode pelatihan. 

Qtable_frozenlake = train(n_training_episodes, min_epsilon, max_epsilon, decay_rate, env, max_steps, Qtable_frozenlake)

Seperti yang dapat kita lihat, Q-Table terlatih memiliki nilai, dan agen kini akan menggunakan nilai-nilai ini untuk menavigasi lingkungan dan mencapai tujuan.  
Qtable_frozenlake
array([[0.73509189, 0.77378094, 0.77378094, 0.73509189],
      [0.73509189, 0.        , 0.81450625, 0.77378094],
      [0.77378094, 0.857375  , 0.77378094, 0.81450625],
      [0.81450625, 0.        , 0.77378094, 0.77378094],
      [0.77378094, 0.81450625, 0.        , 0.73509189],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.        , 0.81450625],
      [0.        , 0.        , 0.        , 0.        ],
      [0.81450625, 0.        , 0.857375  , 0.77378094],
      [0.81450625, 0.9025    , 0.9025    , 0.        ],
      [0.857375  , 0.95      , 0.        , 0.857375  ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.        , 0.        , 0.        ],
      [0.        , 0.9025    , 0.95      , 0.857375  ],
      [0.9025    , 0.95      , 1.        , 0.9025    ],
      [0.        , 0.        , 0.        , 0.        ]])
Evaluasi
evaluate_agent berjalan selama n_eval_episodes episode dan mengembalikan mean dan deviasi standar dari hadiah. 

Dalam loop, pertama-tama kita akan memeriksa apakah ada evaluation seed. Jika tidak ada, maka kita akan me-reset lingkungan tanpa seed. 
Loop bersarang akan berjalan hingga max_steps.
Agen akan mengambil aksi yang memiliki hadiah masa depan yang diharapkan maksimum pada keadaan tertentu menggunakan Q-Table. 
Hitung hadiah.
Ubah keadaan.
Jika selesai (agen jatuh ke lubang atau tujuan telah dicapai), hentikan loop.
Tambahkan hasilnya.
Pada akhirnya, kita akan menggunakan hasil ini untuk menghitung mean dan deviasi standar. 

def evaluate_agent(env, max_steps, n_eval_episodes, Q, seed):

  episode_rewards = []
  for episode in range(n_eval_episodes):
    if seed:
      state = env.reset(seed=seed[episode])
    else:
      state = env.reset()
    step = 0
    done = False
    total_rewards_ep = 0
   
    for step in range(max_steps):
      # Take the action (index) that have the maximum reward
      action = np.argmax(Q[state][:])
      new_state, reward, done, info = env.step(action)
      total_rewards_ep += reward
       
      if done:
        break
      state = new_state
    episode_rewards.append(total_rewards_ep)
  mean_reward = np.mean(episode_rewards)
  std_reward = np.std(episode_rewards)

  return mean_reward, std_reward
Seperti yang Anda lihat, kita mendapatkan skor sempurna dengan deviasi standar nol. Ini berarti agen kita telah mencapai tujuan di seluruh 100 episode. 
# Evaluate our Agent
mean_reward, std_reward = evaluate_agent(env, max_steps, n_eval_episodes, Qtable_frozenlake, eval_seed)
print(f"Mean_reward={mean_reward:.2f} +/- {std_reward:.2f}")
Mean_reward=1.00 +/- 0.00
Memvisualisasikan hasil
Sejauh ini, kita bermain dengan angka, dan untuk memberikan demo, kita perlu membuat Gif animasi dari agen sejak awal hingga mencapai tujuan. 

Pertama, kita akan membuat keadaan dengan me-reset lingkungan menggunakan bilangan bulat acak 0-500. 
Render lingkungan menggunakan rdb_array untuk membuat array gambar. 
Lalu tambahkan img ke array images. 
Dalam loop, kita akan mengambil langkah menggunakan Q-Table dan merender gambar untuk setiap langkah. 
Pada akhirnya, kita akan menggunakan array ini dan imageio untuk membuat Gif dengan satu frame per detik. 

def record_video(env, Qtable, out_directory, fps=1):
  images = [] 
  done = False
  state = env.reset(seed=random.randint(0,500))
  img = env.render(mode='rgb_array')
  images.append(img)
  while not done:
    # Take the action (index) that have the maximum expected future reward given that state
    action = np.argmax(Qtable[state][:])
    state, reward, done, info = env.step(action) # We directly put next_state = state for recording logic
    img = env.render(mode='rgb_array')
    images.append(img)
  imageio.mimsave(out_directory, [np.array(img) for i, img in enumerate(images)], fps=fps)
Jika Anda berada di Jupyter notebook, Anda dapat menampilkan Gif menggunakan fungsi Image dari IPython.display. 
video_path="/content/replay.gif"
video_fps=1
record_video(env, Qtable_frozenlake, video_path, video_fps)

from IPython.display import Image
Image('./replay.gif')
Sekarang Anda dapat membagikan hasil ini dengan rekan kerja dan teman sekelas Anda atau mempostingnya di media sosial.