- Baru-baru ini, skalabilitas reinforcement learning (RL) mendapat perhatian, seperti pada model bahasa besar (LLM)
- Dalam praktiknya, AlphaGo, LLM, dan lain-lain memang menunjukkan performa kuat, tetapi algoritme RL on-policy yang terutama digunakan
- Q-learning, algoritme perwakilan dari RL off-policy, memiliki skalabilitas yang rendah pada masalah dengan horizon panjang karena masalah bias yang terakumulasi
- Hasil eksperimen menunjukkan bahwa meski data dan komputasi ditingkatkan secara besar-besaran, algoritme standar keluarga Q-learning tetap memiliki batas performa pada tugas jangka panjang yang kompleks
- Karena yang ada baru solusi lokal seperti metode hierarchy untuk meredakan masalah horizon, dibutuhkan tujuan off-policy RL baru yang secara fundamental dapat diskalakan
Apakah RL bisa diskalakan?
- Baru-baru ini, prediksi token berikutnya pada model bahasa, diffusion model, dan metode contrastive learning adalah tujuan yang dapat diskalakan dengan baik ketika data dan komputasi ditambah
- RL juga menunjukkan hasil kuat pada game, matematika, coding, dan lain-lain, dan dalam banyak kasus algoritme RL on-policy (misalnya PPO, REINFORCE) digunakan
- On-policy RL selalu hanya bisa memakai roll-out baru, yaitu data yang dihasilkan langsung oleh kebijakan terbaru
- Cara ini bukan masalah besar dalam simulasi atau LLM, tetapi sangat tidak efisien di lingkungan nyata seperti robot
- Sebagai contoh, pada eksperimen robot, untuk memperoleh data yang cukup bisa memerlukan waktu berbulan-bulan, dan membutuhkan intervensi manual manusia
Munculnya off-policy RL
- Off-policy RL sangat unggul dalam sample efficiency karena dapat mendaur ulang seluruh data sebelumnya
- Q-learning banyak digunakan sebagai contoh utama, dan menunjukkan hasil seperti walking robot anjing secara real-time
- Q-learning menggunakan minimisasi temporal difference (TD) loss, dan hampir semua RL off-policy mengikuti prinsip ini
- Untuk menerapkan RL pada masalah dunia nyata, pada akhirnya pertanyaan kuncinya adalah: apakah Q-learning juga bisa diskalakan?
Batas skalabilitas Q-learning
- Penulis berargumen bahwa Q-learning saat ini tidak dapat diskalakan dengan baik ketika muncul masalah horizon panjang (lebih dari 100 langkah keputusan)
- Di sini, “skalabilitas” berarti apakah masalah tetap dapat diselesaikan hanya dengan menambah data dan sumber daya komputasi meski kedalaman/kesulitan masalah (‘depth’) meningkat
- Seperti dibuktikan secara empiris di berbagai makalah, ini bukan sekadar menambah jumlah masalah yang dapat diproses (‘width’)
- Klaim penulis: keluarga Q-learning lemah skalabilitasnya pada sumbu kedalaman (difficulty), sehingga inovasi algoritmik bersifat esensial
- Ada dua dasar utama: satu adalah tidak adanya contoh sukses empiris, dan yang lain adalah eksperimen sistematis yang baru dilakukan
Bukti empiris
- AlphaGo, AlphaZero, dan MuZero semuanya adalah RL on-policy berbasis model dan bukan keluarga TD-learning
- OpenAI Five juga merupakan metode on-policy seperti PPO
- RL untuk LLM pun sebagian besar didominasi varian on-policy dari keluarga policy gradient
- Hampir tidak ada contoh sukses nyata berskala besar dari Q-learning atau RL off-policy serupa pada tingkat AlphaGo atau LLM
- Penulis menyatakan bahwa dari penelusuran berbagai makalah dan kasus praktik, ia tidak mengetahui contoh sukses besar berbasis Q-learning
Penyebab keterbatasan Q-learning: horizon dan bias terakumulasi
- Pada Q-learning, target TD yang dibootstrap (membuat nilai prediksi dari estimasi) selalu bias; bias ini terakumulasi sepanjang time-horizon
- Sebaliknya, tujuan lain yang sangat skalabel seperti prediksi token, diffusion, dan contrastive learning tidak memiliki bias terakumulasi pada target prediksi
- Semakin panjang horizon (panjang pengambilan keputusan), semakin terbatas skalabilitas performa Q-learning karena error yang menumpuk
- Untuk meredakannya, banyak kasus menetapkan discount factor lebih kecil
- Metode estimasi nilai on-policy seperti policy gradient relatif kurang terdampak masalah horizon berkat teknik seperti GAE
Verifikasi batas skalabilitas melalui eksperimen
- Dalam makalah terbaru, untuk tugas ultra-long horizon dirancang task sulit dengan ribuan step di OGBench dan lainnya
- Di lingkungan tersebut, faktor noise diminimalkan dengan data yang “hampir tak terbatas”, model yang kuat, dan pengurangan beban pada jaringan representasi
- Semua metode offline RL yang ada (BC, IQL, CRL, SAC+BC, dll.) gagal mempelajari task kompleks bahkan pada dataset yang sangat besar
- Dilakukan ablation test pada semua variabel seperti data dan ukuran model, waktu pelatihan, serta hyperparameter, tetapi tetap gagal menembus batas performa
- Namun, hanya teknik yang mengurangi horizon (panjang pengambilan keputusan) yang secara konsisten efektif untuk meningkatkan skalabilitas performa
Efek teknik pengurangan horizon
- Hanya pengurangan horizon seperti n-step return dan RL hierarkis yang menunjukkan efek menentukan pada scaling RL
- Pengurangan horizon bukan sekadar mempercepat pelatihan, tetapi juga secara drastis meningkatkan performa akhir itu sendiri
- Namun, pendekatan semacam ini bukan solusi fundamental atas masalah, melainkan hanya mengurangi horizon dengan faktor konstan
- Dibutuhkan pendekatan algoritmik baru yang dapat mengatasi kutukan horizon
Perlunya tujuan off-policy RL baru yang skalabel
- Dari penelitian sejauh ini telah terbukti bahwa sekadar memperbesar ukuran data/model tidak dapat secara fundamental mengatasi kutukan horizon
- Pada akhirnya dibutuhkan varian off-policy RL yang dapat diskalakan bahkan untuk masalah jangka panjang dengan panjang sebarang
- Jika tujuan ini tercapai, akan dimungkinkan menyelesaikan spektrum masalah dunia nyata yang lebih luas seperti robot, LLM, dan berbagai agen pengambilan keputusan
Ide dan usulan riset ke depan
- Melampaui hierarchy dua tahap, dimungkinkan mengusulkan struktur hierarkis baru yang sederhana dan skalabel untuk menangani horizon dengan panjang sebarang
- Model-based RL mungkin dapat bersifat scalable melalui penggabungan pemodelan berbasis supervised learning dan RL on-policy
- Menjelajahi keluarga baru seperti quasimetric RL dan contrastive RL yang sepenuhnya mengecualikan TD learning juga bisa berguna
- Lingkungan evaluasi dan kode yang dibuat telah dibuka, dan dapat dimanfaatkan sebagai benchmark uji skala untuk berbagai algoritme RL baru
Ucapan terima kasih
- Disampaikan terima kasih kepada berbagai peneliti yang memberikan kerja sama/umpan balik pada makalah dan post ini
- Dijelaskan bahwa isi ini didasarkan pada makalah [Horizon Reduction Makes RL Scalable] dan lainnya, serta merupakan opini pribadi penulis
1 komentar
Opini Hacker News
Saya rasa keterbatasan skalabilitas Q-Learning punya alasan yang lebih besar daripada yang disebut di blog. Jumlah state yang harus ditangani agen biasanya meningkat secara eksponensial seiring horizon bertambah. Akibatnya, kebutuhan data untuk melatih Q yang menangani state-state itu juga membesar secara eksponensial. Sebaliknya, pembelajaran on-policy hanya mempelajari state penting, sehingga meskipun ruang state bersifat eksponensial, data pelatihan relatif terfokus hanya pada titik yang benar-benar membutuhkan, sehingga masalahnya menjadi lebih sederhana
Saya setuju dengan analisis overapproximation bias pada Q-learning yang dibahas di tulisan tersebut. Operator Max pada Q-learning cenderung memperkuat noise sepanjang sumbu waktu. Ada juga contoh metode mitigasi bias yang berhasil meningkatkan performa agen RL, seperti di paper ini. Ada pula hasil riset yang menunjukkan bahwa fenomena ini lebih sering muncul pada state yang jarang dikunjungi jaringan. Kekuatan deep learning adalah performa tetap dimungkinkan jika ada struktur yang bisa dipelajari, meski jumlah state tumbuh eksponensial. Kuncinya adalah menetapkan target pelatihan yang tepat, dan tulisan itu berargumen bahwa Q-learning punya keterbatasan di bagian tersebut. Saya penasaran apakah sistem RL berbasis model seperti MuZero bisa menjadi solusi. MuZero meningkatkan efisiensi pelatihan dengan menganalisis ulang trajektori sebelumnya, dan Monte Carlo Tree Search (MCTS) adalah cara yang berprinsip untuk mengurangi horizon dengan membuka beberapa langkah ke depan. Masalah operator Max juga bisa muncul di dalam MCTS, tetapi semakin dalam pencariannya, semakin besar kemungkinan masalah ini terkompensasi
Saya rasa thread ini mungkin membantu. Dari sudut pandang orang yang benar-benar bukan ahli, ada tugas tertentu yang meskipun punya “kedalaman”, tetap bisa dianggap memiliki homogenitas, sehingga pembelajaran masih mungkin walaupun kualitas sampelnya agak buruk. Saya ingin menyebut tugas seperti ini sebagai “ergodic”. Tetapi saya juga yakin ada tugas yang memang tidak seperti itu
Saya penasaran apakah ini mirip dengan perbedaan antara integrasi Monte Carlo grid umum dan integrasi Monte Carlo importance sampling
Berbagi kesan tentang Majorana-1
Sayang sekali blog tersebut tidak membahas pendekatan offline seperti Decision Transformers dan Trajectory Transformers. Berkat mekanisme attention, pendekatan ini menghindari masalah credit assignment dan menunjukkan performa bagus pada tugas long-horizon (jangka panjang). Banyak peneliti RL menganggap pendekatan ini bukan “RL sejati”, karena ia tidak bisa melakukan credit assignment di luar context window. Karena itu, banyak yang menilai pendekatan ini sulit diterapkan pada tugas dengan horizon tak terbatas. Namun, jika context window-nya lebih dari 1 juta, saya jadi bertanya-tanya apakah itu benar-benar masih menjadi masalah besar. Lihat paper Decision Transformer dan paper Trajectory Transformer
Saya rasa ini merangkum inti RL dengan sangat baik. Sederhananya, ini seperti terus bergerak sambil mengejar tujuan, tetapi posisi tujuan itu sendiri terus berubah tergantung bagaimana saya bergerak. Dengan kata lain, dalam value-based RL tidak ada jawaban absolut (ground truth); ini permainan menyelaraskan kedua sisi hanya dengan estimasi kita sendiri. Namun saya tidak menganggapnya putus asa. Justru saya merasa RL akan segera menjadi praktis, karena selama ini salah satu hambatannya adalah kurangnya world model atau fungsi dinamika yang bisa diandalkan. Sekarang, kemajuan besar juga sedang terjadi di area itu
Paper/blog ini ditujukan untuk orang yang sudah punya pengetahuan RL. Jika ingin belajar RL lebih dalam, saya merekomendasikan kuliah pengantar dari David Silver (Deep Mind)
Keterbatasan mendasar pembelajaran off-policy adalah bahwa data eksplorasi awal yang kurang efektif tidak terlalu membantu untuk mempelajari kebijakan yang lebih maju. Contohnya dalam catur: blunder pemula, langkah yang tidak bermakna, atau perilaku yang gagal menyelesaikan puzzle. Data menjadi off-policy pada saat tindakan tersebut menyimpang dari kebijakan saat ini, yaitu dari apa yang benar-benar akan dipilih agen. Jadi pada akhirnya, inti masalah ini adalah generalisasi yang lebih baik dan peningkatan sample efficiency
Ketika manusia mempelajari tugas jangka panjang (horizon panjang), mereka menggunakan pengulangan latihan untuk membagi tugas keseluruhan menjadi sub-tugas dengan horizon pendek, lalu kemudian menggabungkan keterampilan-keterampilan bagian itu secara hierarkis
Manusia pada kenyataannya menggunakan pembelajaran on-policy dan off-policy sekaligus. Mereka belajar on-policy dengan mengeksplorasi langsung hasil dari tindakannya sendiri, dan juga belajar off-policy dengan mengamati demonstrasi dari ahli lain. Tetapi manusia berbeda dari RL karena mereka membedakan tindakan baik dan buruk lalu hanya menyaring yang “baik” untuk dipelajari. Sebaliknya, pada kebanyakan RL off-policy, tindakan buruk juga dipakai sebagai data, yang akhirnya memperlambat keseluruhan proses pelatihan
Saya suka isi blog ini, tetapi sayang penggunaan singkatan dan istilah teknis yang tidak dijelaskan membuatnya kurang berguna bagi pembaca yang lebih luas. Akan lebih baik jika istilah dan singkatannya dijelaskan agar lebih mudah diakses
Untuk tulisan seperti posting blog ini, isinya memang sangat kaya tetapi menuntut banyak pengetahuan awal sehingga aksesibilitasnya rendah; alat AI sangat membantu untuk penjelasan dan interpretasi yang lebih mudah. Baru-baru ini saya memakai Dia berbasis browser dan hasilnya efektif. Bahkan dengan menyalin-tempel ke model AI lain pun, keseluruhannya bisa diringkas dengan rapi sambil tetap memberi penjelasan atas hal-hal yang membuat penasaran
Terasa jelas bahwa tulisan seperti ini memang ditujukan untuk peneliti RL. Kesimpulannya seperti, “Tolong ada yang cari cara supaya Q-learning bisa dibuat scalable!”
Justru saya rasa itu yang membuat tulisan ini lebih rapi
Kelebihan teknik off-policy seperti Q-Learning adalah bahwa bahkan jika hanya memperoleh data yang hampir optimal (data yang kurang bagus), pada akhirnya ia tetap akan konvergen ke solusi optimal. Misalnya, bahkan jika kita hanya mengumpulkan data pertandingan catur tanpa strategi apa pun lalu memakainya sebagai input Q-Learning, pada akhirnya kebijakan optimal tetap bisa dipelajari (meskipun tentu lebih lambat dibanding jika datanya bagus)