Q-learning Belum Dapat Diskalakan

• RL telah meraih capaian besar di Go, Chess, dan post-training LLM, tetapi sebagian besar bergantung pada RL on-policy yang membutuhkan rollout baru, sehingga kondisinya berbeda dari RL off-policy yang dapat menggunakan ulang data lama secara bebas
• Q-learning, contoh utama RL off-policy, memiliki efisiensi sampel yang tinggi, tetapi belum cukup dapat diskalakan untuk tugas jangka panjang yang membutuhkan lebih dari 100 tahap pengambilan keputusan bermakna
• Bottleneck-nya adalah target bootstrap yang bias dalam pembelajaran TD terakumulasi seiring horizon makin panjang; ini merupakan batasan yang berbeda dari prediksi token berikutnya, model difusi, dan pembelajaran kontrasif
• Dalam eksperimen OGBench, flow BC, IQL, CRL, dan SAC+BC tidak berhasil menyelesaikan semua tugas jangka panjang bahkan dengan dataset 1B yang 1000 kali lebih besar daripada dataset RL offline biasa, dan kinerjanya stagnan di bawah level optimal
• Horizon reduction seperti n-step returns dan RL hierarkis meningkatkan skalabilitas dan kinerja akhir, tetapi teknik saat ini hanya meringankan masalah dalam faktor konstan dan belum cukup untuk menyelesaikan tugas jangka panjang yang kompleks secara arbitrer

---

Posisi Skalabilitas RL Saat Ini

• Prediksi token berikutnya, denoising diffusion, dan pembelajaran kontrasif menunjukkan bahwa mereka adalah fungsi objektif yang dapat diskalakan pada data berskala besar dan model dengan miliaran parameter
• RL juga telah mencapai performa superhuman di Go dan Chess, dan pada LLM mampu menyelesaikan tugas penalaran kompleks seperti matematika dan coding
• Namun sebagian besar contoh sukses nyata saat ini berbasis algoritme RL on-policy
  • Contoh utamanya adalah REINFORCE, PPO, GRPO, dan sejenisnya
  • Rollout yang baru di-sampling dari policy saat ini selalu diperlukan
  • Data lama tidak dapat digunakan ulang
  • Metode keluarga PPO dapat menggunakan ulang data secara terbatas, tetapi menurut klasifikasi seperti dalam dokumentasi OpenAI, tetap dianggap sebagai RL on-policy
• Di lingkungan seperti board game atau LLM, tempat rollout murah dan dapat dibuat dalam jumlah besar, batasan ini mungkin bukan masalah besar
• Dalam robotika, membuat sampel di dunia nyata pada skala yang digunakan untuk post-training model bahasa dengan RL memerlukan waktu berbulan-bulan atau lebih, dan selama training manusia harus berada di sisi robot 24 jam untuk meresetnya

RL Off-policy dan Q-learning

• RL off-policy pada prinsipnya dapat menggunakan data apa pun, kapan pun dan bagaimana pun data itu dikumpulkan
• Data yang sama dapat digunakan ulang berkali-kali, sehingga umumnya memiliki efisiensi sampel yang lebih baik
• Ada juga contoh di lingkungan nyata yang melatih robot anjing agar bisa berjalan dalam 20 menit dari nol
  • Kasus terkait: walk in the park
• Q-learning adalah algoritme RL off-policy yang paling banyak digunakan
• Sebagian besar algoritme RL off-policy model-free yang praktis berbasis variasi dari loss TD
• Agar RL dapat diterapkan ke lebih banyak masalah dunia nyata, pertanyaan kuncinya adalah “apakah Q-learning, yaitu TD learning, dapat diskalakan?”
• Jika bisa, tugas nyata yang lebih beragam dan kompleks seperti robotika serta agen penggunaan komputer dapat diselesaikan secara efisien

Makna “Dapat Diskalakan”: Bukan Lebar, Melainkan Kedalaman

• Skalabilitas di sini berarti kemampuan untuk menyelesaikan masalah dengan horizon yang lebih sulit dan lebih panjang ketika data dengan coverage memadai, komputasi, dan waktu ditambahkan
• Ini berbeda dari kemampuan satu model untuk menyelesaikan lebih banyak jumlah tugas
  • Bertambahnya jumlah tugas tidak selalu berarti menyelesaikan tugas yang lebih sulit
  • Beberapa studi scaling yang ada menunjukkan kemungkinan pada sumbu “lebar” ini
• Sumbu yang lebih penting dan sulit adalah kedalaman
  • Karena menuntut kemampuan pengambilan keputusan yang lebih maju
• Q-learning dalam bentuk saat ini tidak sangat dapat diskalakan pada sumbu kedalaman
• Untuk menskalakan Q-learning dan RL off-policy ke masalah jangka panjang yang kompleks, diperlukan terobosan algoritmik

Q-learning yang Absen dari Kisah Sukses RL Berskala Besar

• Banyak keberhasilan RL nyata berbasis pendekatan selain Q-learning berbasis TD
• AlphaGo, AlphaZero, dan MuZero menggunakan RL berbasis model serta Monte Carlo tree search, dan tidak menggunakan TD learning dalam board game
  • Referensi: makalah MuZero halaman 15
• OpenAI Five mencapai performa superhuman di Dota 2 dengan PPO
  • Referensi: catatan kaki 6 pada makalah OpenAI Five
• RL untuk LLM saat ini didominasi keluarga policy gradient on-policy seperti PPO dan GRPO
• Tidak ada contoh nyata yang ditunjukkan mengenai keberhasilan RL off-policy, khususnya 1-step TD learning, pada skala yang mirip AlphaGo atau LLM
• Penilaian ini bukan untuk menyangkal RL off-policy, melainkan lebih dekat pada kesadaran masalah bahwa riset algoritme RL masih perlu lebih banyak dilakukan

Mengapa Q-learning Goyah pada Tugas Jangka Panjang

• Loss TD dalam Q-learning melatih nilai Q saat ini agar sesuai dengan target berupa reward ditambah nilai Q maksimum dari state berikutnya
• Target ini adalah target bootstrap yang bias yang belum tentu sama dengan nilai Q optimal sebenarnya
• Alasan utama Q-learning sulit diskalakan adalah bias pada target prediksi terakumulasi sepanjang horizon
• Akumulasi bias ini menjadi batasan mendasar TD learning
  • Fungsi objektif seperti prediksi token berikutnya, denoising diffusion, dan pembelajaran kontrasif tidak memiliki bias target prediksi seperti ini
  • BYOL dan DINO, meskipun memiliki bias, tidak mengakumulasikannya sepanjang horizon
• Saat masalah makin kompleks dan horizon makin panjang, bias target bootstrap menumpuk lebih parah
• Masalah ini sulit diringankan hanya dengan lebih banyak data dan model yang lebih besar
• Faktanya, salah satu alasan utama discount factor yang lebih besar seperti (\gamma > 0.999) jarang digunakan juga berkaitan dengan hal ini
• Metode policy gradient relatif lebih sedikit mengalami masalah ini
  • Teknik estimasi nilai on-policy seperti GAE relatif lebih mudah menangani horizon panjang meskipun harus menerima varians lebih tinggi
  • Tidak terikat pada rekursi 1-step yang ketat

Eksperimen Skalabilitas Berbasis OGBench

• Makalah terbaru Horizon Reduction Makes RL Scalable memverifikasi hipotesis di atas melalui berbagai studi scaling yang terkontrol
• Tujuannya adalah memastikan apakah metode RL off-policy saat ini dapat menyelesaikan tugas yang sangat sulit hanya dengan memperbesar data dan komputasi
• Eksperimen menggunakan tugas-tugas kompleks dari OGBench yang sebelumnya belum terselesaikan
• Persyaratan tugasnya adalah sebagai berikut
  • Agen harus mempelajari perilaku goal-reaching yang kompleks dari demo play-style acak yang tidak terstruktur
  • Saat pengujian, agen harus melakukan manipulasi presisi, pemecahan puzzle kombinatorial, dan navigasi jangka panjang
  • Tugas berlangsung selama 1.000 environment steps
• Eksperimen dirancang untuk mengurangi variabel perancu
  • Mengumpulkan data nyaris tak terbatas sampai overfitting secara praktis mustahil
  • Berfokus pada RL offline untuk menghilangkan masalah eksplorasi
  • Memastikan dataset memiliki coverage yang memadai dan semua tugas dapat diselesaikan dari dataset yang diberikan
  • Memberikan ground-truth state observation secara langsung untuk mengurangi beban pembelajaran representasi
• Jika Q-learning tidak dapat diskalakan bahkan dalam lingkungan terkontrol ini, peluangnya lebih rendah di lingkungan nyata yang memiliki data terbatas dan noisy observation

Hasil Algoritme RL Offline Standar

• Algoritme RL offline standar yang banyak digunakan tidak dapat menyelesaikan semua tugas
• Algoritme yang diuji adalah flow BC, IQL, CRL, SAC+BC
• Eksperimen juga dilakukan pada dataset berukuran 1B
  • Ini (1000 \times) lebih besar daripada dataset RL offline biasa
• Hal yang lebih penting adalah kinerjanya sering mencapai plateau di titik yang jauh di bawah performa optimal
• Berbagai ablation dan eksperimen kontrol seperti model yang lebih besar, training lebih lama, dan hyperparameter berbeda juga tidak efektif
• Satu-satunya metode yang menjadi pengecualian dan efektif adalah horizon reduction

Perbaikan yang Dibawa Horizon Reduction

• Hipotesis sebelumnya adalah bahwa horizon dan akumulasi bias yang menyertainya merupakan hambatan utama bagi scaling RL off-policy
• Untuk memverifikasinya, dicoba beberapa teknik horizon reduction yang mengurangi jumlah TD backup yang bias
  • Contohnya n-step returns, RL hierarkis, dan sebagainya
• Hasilnya positif
  • Teknik sederhana seperti n-step returns pun secara signifikan meningkatkan skalabilitas dan performa akhir
  • Bukan sekadar trik untuk mempercepat training, tetapi juga meningkatkan asymptotic performance
  • Metode hierarkis penuh bekerja lebih baik
• Satu-satunya teknik yang bekerja secara konsisten di seluruh eksperimen adalah horizon reduction
• Sekadar memperbesar data dan komputasi tidak cukup untuk mengatasi kutukan horizon
• Diperlukan algoritme yang lebih baik yang menargetkan masalah ini secara langsung

Arah Riset Menuju Fungsi Objektif RL Off-policy yang Dapat Diskalakan

• Horizon reduction membuka skalabilitas Q-learning, tetapi teknik saat ini tidak menyelesaikan masalah secara fundamental
• Metode saat ini seperti n-step returns dan RL hierarkis kebanyakan meringankan masalah hanya dalam faktor konstan
• Algoritme RL off-policy yang dapat diskalakan hingga masalah jangka panjang yang kompleks secara arbitrer masih belum memadai
• Kemungkinan arah riset dapat diringkas menjadi tiga
  • Mencari struktur hierarkis rekursif yang sederhana dan dapat diskalakan melampaui hierarki 2 level untuk menangani horizon dengan panjang arbitrer
  • Karena pembelajaran model adalah supervised learning dan RL on-policy juga dapat diskalakan, pendekatan RL berbasis model yang terlebih dahulu mempelajari model lalu menjalankan RL on-policy di dalam model tersebut
  • Cara yang sepenuhnya menghindari TD learning
    • Sebagai contoh, quasimetric RL berbasis LP formulation dari RL
    • Metode berbasis MC seperti contrastive RL juga dapat diuji apakah memiliki kemungkinan scaling yang lebih baik dibanding pendekatan berbasis TD
• Setup eksperimen di atas dapat menjadi titik awal untuk menguji ide-ide ini
  • Tugas dan dataset robotika yang kompleks sudah dirancang
  • Telah diverifikasi bahwa tugas dapat diselesaikan dari data yang diberikan
  • Dengan menambahkan lebih banyak kubus dan sejenisnya, tugas dapat dibuat semakin sulit secara arbitrer untuk melakukan stress test skalabilitas algoritme secara terkontrol
  • Kode dirilis: horizon-reduction

[GN⁺]

Komentar Hacker News

• Tulisan ini tampaknya melewatkan alasan yang lebih besar mengapa Q-learning sulit diskalakan
  Semakin panjang horizon, jumlah state yang mungkin biasanya bertambah secara eksponensial, dan untuk mempelajari Q yang bisa menangani state-state itu, data juga harus bertambah secara eksponensial
  Dalam pembelajaran on-policy, masalah ini lebih ringan, karena yang penting hanyalah state di sekitar policy saat ini, dan memang hanya state seperti itu yang disampel

  • Menurut saya analisis tulisan ini tentang bias overestimasi benar
    Intinya adalah operasi max pada Q-learning membuat noise menguat seiring berjalannya timestep, dan teknik mitigasi bias seperti https://arxiv.org/abs/1509.06461 berhasil meningkatkan performa agen reinforcement learning
    Menurut penelitian, fenomena ini lebih kuat muncul pada state yang jarang dikunjungi jaringan
    Jumlah state yang eksponensial hanya menjadi penentu bila tidak ada pola di antara state-state itu. Jika ada struktur yang bisa dipelajari, ini bisa bekerja dengan baik, dan itu bukan kelemahan deep learning, melainkan kekuatannya
    Kuncinya adalah menetapkan tujuan pembelajaran yang tepat, dan tulisan ini pada dasarnya berargumen bahwa Q-learning bukan tujuan tersebut
    Saya juga penasaran apakah reinforcement learning berbasis model seperti MuZero bisa menjadi solusi atas kekhawatiran penulis. MuZero dapat meningkatkan efisiensi pembelajaran dengan menganalisis ulang trajectory sebelumnya, dan Monte Carlo Tree Search (MCTS) adalah cara yang berprinsip untuk mengurangi horizon dengan mengembangkan model beberapa langkah ke depan
    Operasi max pada MCTS juga bisa menimbulkan masalah serupa, tetapi proses pencarian yang makin dalam dapat mengimbanginya
  • Mungkin thread ini bisa membantu: https://news.ycombinator.com/item?id=44280505
    Dari sudut pandang orang yang sama sekali bukan pakar, saya merasa beberapa tugas, meskipun “dalam”, bisa saja cukup “seragam” sehingga sampel yang buruk pun sudah memadai. Saya ingin menyebut tugas semacam itu sebagai tugas ergodik
    Tentu saja, pasti ada juga tugas yang tidak seperti itu
  • Apakah perbedaan ini pada dasarnya sama dengan perbedaan antara integrasi Monte Carlo grid umum dan integrasi Monte Carlo dengan importance sampling?

• Makalah ini memang berangkat dari asumsi bahwa pembacanya sudah cukup memahami reinforcement learning
  Jika ingin mendalami reinforcement learning dengan benar, kuliah pengantar dari David Silver (DeepMind) sangat bagus: https://youtu.be/2pWv7GOvuf0?si=CmFJHNnNqraL5i0s

• Saya sepenuhnya setuju, dan menurut saya ini ringkasan yang sangat bagus
  Singkatnya, ini adalah masalah mengejar target yang bergerak, dan target itu berubah tergantung bagaimana saya bergerak
  Dalam reinforcement learning berbasis nilai, tidak ada jawaban benar nyata yang bisa menjadi titik konvergensi. Seolah-olah kita meminimalkan selisih yang di kedua sisi persamaannya sama-sama berisi aproksimasi kita sendiri
  Meski begitu, saya tidak melihatnya sebagai sesuatu yang tanpa harapan. Menurut saya reinforcement learning sudah sangat dekat untuk bisa bekerja; yang selama ini kurang adalah world model/fungsi dinamika maju yang dapat diandalkan
  Dengan itu, kita bisa merencanakan tanpa bereksplorasi, dan sekarang model seperti itu sudah ada

• Manfaat pembelajaran off-policy secara fundamental dibatasi oleh fakta bahwa data tidak efisien dari eksplorasi awal tidak terlalu berguna untuk memperbaiki policy yang lebih matang di kemudian hari
  Ini jelas jika kita memikirkan blunder dalam catur, gerakan seperti kejang, atau kegagalan memecahkan puzzle
  Hal ini makin jelas setelah menyadari bahwa data menjadi off-policy hanya ketika data tersebut menggambarkan hal-hal yang tidak akan dilakukan oleh policy saat ini
  Menurut saya solusi untuk masalah ini sayangnya berkaitan dengan perlunya generalisasi dan efisiensi sampel yang lebih baik

  • Bukankah klaim ini membuktikan terlalu banyak hal?
    Bagaimana menjelaskan contoh yang dikutip, yaitu anjing yang belajar berjalan dalam 20 menit dengan pembelajaran off-policy? Atau apakah klaimnya lebih subtil?

• Agak mengherankan Decision Transformer atau Trajectory Transformer tidak dibahas
  Keduanya adalah pendekatan offline, dan berkat mekanisme attention, keduanya cenderung bekerja cukup baik pada tugas horizon panjang dengan menghindari masalah credit assignment
  Sebagian besar peneliti reinforcement learning tidak menganggap pendekatan seperti ini sebagai “reinforcement learning sungguhan”, karena tidak dapat mengalokasikan credit di luar context window sehingga tidak bisa mempelajari tugas dengan horizon tak hingga
  Namun jika context window mencapai lebih dari 1 juta token, mungkinkah ini dalam praktiknya menjadi masalah yang lebih kecil? Saya penasaran dengan pendapat lain
  DT: https://arxiv.org/abs/2106.01345
  TT: https://arxiv.org/abs/2106.02039

  • TFP mengutip Decision Transformer
    Sekadar memakai Transformer tidak berarti masalah credit assignment dapat dilewati
    Transformer adalah arsitektur untuk menyelesaikan masalah pemodelan sekuensial, dan masalah credit assignment dalam reinforcement learning juga merupakan salah satu contoh masalah seperti itu. Arsitektur semacam ini sudah banyak ada sebelumnya
    Sulitnya masalah credit assignment adalah pernyataan tentang kelangkaan data. Pilihan arsitektur saja tidak bisa “menghindari” hal itu

• Manusia sebenarnya melakukan keduanya
  Kita belajar secara on-policy saat mengeksplorasi konsekuensi dari tindakan sendiri, dan juga belajar secara off-policy seperti dari demonstrasi pakar
  Bedanya, manusia bisa membedakan tindakan yang baik dan buruk, lalu menyaring dan hanya belajar dari tindakan yang dinilai baik
  Dalam kebanyakan reinforcement learning off-policy, banyak tindakan buruk juga ikut masuk, dan ketika tindakan itu masuk ke set pembelajaran, proses belajar menjadi lebih lambat

  • “Bisa membedakan tindakan yang baik dan buruk” tidak selalu benar
    Karena itu beberapa demonstrasi pakar terasa menarik. Dari sudut pandang “praktik terbaik” level pemula, caranya terlihat sepenuhnya keliru, tetapi ternyata menghasilkan hasil yang lebih baik
    Tentu saja, kadang itu hanya berarti jika seseorang sudah sehebat itu, teknik atau kesalahan semacam itu pun masih bisa ditanggung

• Perlu dicatat bahwa tugas horizon panjang yang dipelajari manusia lewat latihan berulang biasanya dipecah menjadi tugas-tugas dengan horizon lebih pendek, lalu kemudian dipelajari dengan menyusunnya secara hierarkis

  • Ini mungkin pemikiran naif, tetapi menurut saya ini lebih terlihat sebagai masalah pendekatan daripada algoritme
    Model mungkin tidak mampu menangani tugas horizon panjang sejak awal, tetapi bisa terlebih dahulu mempelajari keterampilan horizon pendek, lalu menggunakan kumpulan keterampilan kecil itu untuk mempelajari horizon yang lebih panjang
    Sama seperti chunking yang kita semua lakukan
    Tidak ada orang yang belajar menerbangkan pesawat komersial lintas benua sebagai urutan gerakan mikro tangan dan lengan
    Sewaktu kecil, mengambil bola memang dipelajari dengan cara seperti itu, tetapi penerbangan atau olahraga tersusun dari hierarki keterampilan dan rencana yang sudah dipelajari

• Saya suka tulisannya, tetapi menurut saya penggunaan singkatan tanpa penjelasan mengurangi peluangnya untuk berguna bagi pembaca yang lebih luas
  Ini catatan kecil, tetapi akan baik jika singkatan dan istilah teknis dijelaskan

  • Untuk tulisan yang isinya sangat bagus tetapi kurang mudah diakses karena mengasumsikan pengetahuan awal yang luas, cukup berguna meminta alat AI menjelaskan dan menyederhanakannya
    Saya baru mencobanya dengan browser baru Dia dan hasilnya berjalan baik. Bisa juga disalin-tempel ke penyedia model favorit Anda
    Dengan begitu tulisan tetap ringkas, sementara kita bisa bertanya dan mengklarifikasi lewat alat AI
  • Melihat kesimpulannya adalah “tolong seseorang buat metode Q-learning yang bisa diskalakan”, jelas tulisan ini ditujukan kepada peneliti reinforcement learning lain

• Hal yang terasa ajaib dari teknik off-policy seperti Q-Learning adalah bahwa meskipun hanya melihat data pelatihan yang tidak optimal, ia tetap konvergen ke hasil optimal
  Misalnya, meskipun dataset permainan catur dari agen-agen yang bergerak sepenuhnya acak tanpa strategi apa pun dipakai sebagai input Q-Learning, prosesnya hanya lebih lambat dibandingkan jika ada input berkualitas tinggi, tetapi pada akhirnya tetap konvergen ke policy optimal

  • Jika itu benar, menurut saya itu mendekati definisi bahwa tugas tersebut ergodik
    Mungkin saya memakai istilahnya dengan sedikit menyimpang, tetapi saya rasa tugas yang tidak ergodik juga akan ada