Skip to content
Kembali ke hasil pencarian

Q-Learning

Diperkenalkan oleh
Christopher Watkins & Peter Dayan
Tahun
1992
Jenis
Model-free reinforcement-learning control algorithm
Keluarga
Reinforcement learning

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Q-learning, yang diperkenalkan oleh Christopher Watkins dan Peter Dayan pada tahun 1992, adalah algoritma pembelajaran penguatan (reinforcement learning) yang bebas model (model-free) yang mempelajari nilai dari setiap tindakan dalam setiap keadaan — fungsi Q — murni dari pengalaman, tanpa model lingkungan.

Algoritma ini bersifat di luar kebijakan (off-policy): ia mempelajari nilai tindakan optimal sambil mengikuti kebijakan perilaku eksploratif, dan dalam kondisi standar terbukti konvergen ke kebijakan optimal.

Intuisi di balik metode

Agen yang belajar melalui coba-coba perlu mengetahui, untuk setiap situasi, seberapa baik setiap tindakan yang mungkin dilakukan dalam jangka panjang. Q-learning mempertahankan hal tersebut: sebuah tabel (atau fungsi) nilai Q yang memperkirakan total imbalan masa depan dari mengambil suatu tindakan dalam suatu keadaan dan berperilaku optimal setelahnya. Setiap kali agen bertindak, mengamati imbalan, dan mendarat di keadaan baru, ia menggeser nilai Q ke arah apa yang baru saja dialaminya ditambah yang terbaik yang diyakininya dapat dilakukannya selanjutnya. Yang terpenting, ia memperbarui ke arah tindakan terbaik selanjutnya terlepas dari apa yang sebenarnya dilakukannya selanjutnya — sehingga ia dapat menjelajah dengan bebas sambil tetap mempelajari strategi optimal.

Sejarah

Christopher Watkins memperkenalkan Q-learning dalam tesisnya tahun 1989, dan Watkins serta Dayan (1992) memberikan bukti konvergensi, menjadikannya landasan pembelajaran penguatan. Algoritma ini menggeneralisasi pembelajaran perbedaan temporal untuk kontrol dan mendasari tonggak sejarah selanjutnya — terutama Deep Q-Networks (Mnih et al., 2015), yang menggabungkan Q-learning dengan jaringan dalam (deep networks) untuk memainkan permainan Atari dari piksel. Algoritma ini dibahas secara kanonik dalam buku teks Sutton dan Barto dan tetap menjadi titik awal default untuk RL berbasis nilai.

Kapan digunakan

Gunakan Q-learning untuk masalah pengambilan keputusan sekuensial yang dibingkai sebagai proses keputusan Markov di mana Anda dapat mengambil sampel transisi dan imbalan tetapi tidak memiliki model dinamika (atau model yang tidak dapat diandalkan) — kontrol, permainan, perutean, penjadwalan, dan sistem adaptif. Q-learning tabular cocok untuk ruang keadaan-tindakan kecil dan diskrit dan konvergen ke optimum dengan eksplorasi yang cukup dan ukuran langkah yang menurun. Untuk ruang besar atau kontinu, tabel diganti dengan aproksimator fungsi (Deep Q-Networks). Algoritma ini mengasumsikan properti Markov dan lingkungan yang stasioner, bisa jadi tidak efisien dalam sampel, dan operator maksimum menimbulkan bias optimis (maksimisasi) yang diatasi oleh varian seperti Double Q-learning. Ketika kebijakan stokastik atau tindakan kontinu diperlukan, metode gradien kebijakan adalah alternatifnya.

Batasan dan pertimbangan

  • Bentuk tabular tidak dapat diskalakan ke ruang keadaan/tindakan besar atau kontinu.
  • Tidak efisien dalam sampel; mungkin memerlukan banyak episode untuk konvergen.
  • Bias maksimisasi (overestimasi) dari operator maksimum; dimitigasi oleh Double Q-learning.
  • Mengasumsikan proses keputusan Markov (stasioner); kesulitan di bawah observabilitas parsial atau drift.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Bebas model: tidak memerlukan model transisi/imbalan, hanya pengalaman yang disampel.
  • Di luar kebijakan: mempelajari kebijakan optimal sambil menjelajah dengan kebijakan lain.
  • Terbukti konvergen ke nilai tindakan optimal dalam kondisi standar.
  • Sederhana, fundamental, dan menjadi dasar bagi Deep Q-Networks dan banyak perluasan.

Penerapan

  • Permainan dan tugas kontrol simulasi.
  • Navigasi robot dan kontrol adaptif.
  • Perutean dinamis, penjadwalan, dan alokasi sumber daya.
  • Kebijakan rekomendasi dan interaksi adaptif.
  • Metode berbasis nilai dasar sebelum Deep Q-Networks.

Cara kerjanya

Cara kerjanya

1

Q(s, a) memperkirakan jumlah imbalan masa depan yang didiskontokan yang diharapkan dari mengambil tindakan a dalam keadaan s dan kemudian bertindak secara optimal. Faktor diskonto γ memberi bobot lebih pada imbalan dekat daripada imbalan jauh. Mempelajari Q untuk semua pasangan keadaan-tindakan setara dengan menyelesaikan masalah kontrol.

Rumus
Q(s,a) \approx \mathbb{E}\!\left[\textstyle\sum_{k\ge0}\gamma^{k} r_{t+k+1}\mid s_t=s,a_t=a\right]
2

Setelah setiap transisi (keadaan s, tindakan a, imbalan r, keadaan berikutnya s'), Q-learning memperbarui Q(s, a) dengan langkah α menuju target perbedaan temporal r + γ·maksimum atas tindakan berikutnya dari Q(s', a'). 'Maksimum' adalah apa yang membuatnya di luar kebijakan dan mengarahkan pembelajaran pada nilai optimal, terlepas dari tindakan yang sebenarnya diambil selanjutnya.

Rumus
Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\big]
3

Untuk mengumpulkan pengalaman, agen bertindak dengan kebijakan eksplorasi, umumnya ε-greedy: biasanya memilih tindakan terbaik saat ini, tetapi dengan probabilitas ε memilih tindakan acak. Eksplorasi memastikan semua pasangan keadaan-tindakan dicoba, yang dipersyaratkan oleh jaminan konvergensi; ε biasanya menurun seiring waktu.

Rumus
a = \begin{cases}\arg\max_a Q(s,a) & \text{prob } 1-\epsilon\\ \text{random} & \text{prob } \epsilon\end{cases}
4

Setelah Q konvergen ke nilai tindakan optimal Q*, kebijakan optimalnya adalah dengan mengambil, di setiap keadaan, tindakan dengan nilai Q tertinggi. Dalam praktiknya, kebijakan serakah (greedy) terhadap Q saat ini diekstraksi di akhir (atau digunakan saat penerapan).

Rumus
\pi^*(s) = \arg\max_a Q^*(s,a)

Kesalahan umum

  • Eksplorasi yang tidak memadai (ε terlalu kecil/menurun terlalu cepat), membuat optimum tidak dipelajari.
  • Jadwal laju pembelajaran yang buruk, menyebabkan divergensi atau pembelajaran yang sangat lambat.
  • Menerapkan Q-learning tabular ke ruang besar alih-alih aproksimator fungsi.
  • Mengabaikan bias overestimasi pada masalah stokastik di mana Double Q-learning membantu.

Pertanyaan yang sering diajukan

Apa arti 'di luar kebijakan' (off-policy) dalam Q-learning?

Artinya Q-learning mempelajari nilai kebijakan optimal sementara agen mengikuti kebijakan perilaku (eksploratif) yang berbeda. Target pembaruan r + γ·maksimum Q(s', a') — tindakan terbaik selanjutnya — bukan tindakan yang sebenarnya diambil, sehingga eksplorasi tidak membiaskan optimum yang dipelajari.

Bagaimana Q-learning berhubungan dengan Deep Q-Networks (DQN)?

DQN menggantikan tabel Q dengan jaringan saraf dalam (deep neural network) yang memperkirakan Q(s, a), memungkinkan Q-learning dalam ruang keadaan besar atau kontinu (misalnya, piksel). DQN menambahkan trik stabilisasi — pengalaman pemutaran kembali (experience replay) dan jaringan target — tetapi aturan pembelajaran inti adalah pembaruan perbedaan temporal Q-learning.

Mengapa Q-learning mengestimasi nilai secara berlebihan (overestimate)?

Operator maksimum dalam pembaruan cenderung memilih estimasi yang terlalu optimis, membiaskan Q ke atas, terutama dengan imbalan yang berisik. Double Q-learning mengurangi hal ini dengan memisahkan pemilihan tindakan dari evaluasi nilai menggunakan dua estimator, menghasilkan kebijakan yang kurang bias dan seringkali lebih baik.

Metode terkait

Sumber

  1. Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3–4), 279–292.

    Buka referensi DOI
    Disalin.
  2. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.

    ISBN: 978-0-262-03924-6
    Disalin.