Multi‑agent deep reinforcement learning: Sebuah Survei

1. Pendahuluan

Yo, sobat! Apa kabar dunia multi-agent? Di sini kita ngomongin tentang entitas yang disebar—alias agen—yang make keputusan sendiri dan interaksi di lingkungan yang sama. Masing-masing agen punya goal sendiri yang butuh skill banyak untuk bikin perilaku yang pintar. Tergantung tugasnya, agen bisa kolaborasi atau jadi kompetitif buat ngalahin lawan. Kalo mau nge-program perilaku yang pintar dari awal itu susah banget. Jadi, agen harus bisa adaptasi dan belajar overtime. Framework yang paling sering dipake buat belajar di lingkungan interaktif ini adalah reinforcement learning (RL), yang fokusnya adalah belajar dari coba-coba.

Dunia RL lagi booming banget sekarang. Berkat deep learning, banyak penelitian yang sukses di bidang kontrol kompleks, kayak di robotik dan bermain game. Meski banyak sukses, kebanyakan penelitian fokus ke setting single-agent, padahal banyak aplikasi di dunia nyata yang melibatkan banyak pengambil keputusan sekaligus. Area aplikasinya bisa dari koordinasi sistem terdistribusi, kendaraan otonom, sampai trading di pasar keuangan. Oleh karena itu, komunitas multi-agent reinforcement learning (MARL) jadi lebih aktif dan banyak literatur baru yang muncul.

Di paper ini, kita ngasih review lengkap tentang perkembangan terbaru di area multi-agent deep reinforcement learning (MADRL). Tujuannya adalah untuk memberikan gambaran yang lebih luas dan komprehensif tentang investigasi terkini di bidang MADRL.

1.1 Pekerjaan Terkait

Di sini kita bahas tentang penelitian yang sudah ada sebelumnya. Ada banyak tantangan dan isu yang perlu dipecahkan, mulai dari masalah skalabilitas, kompleksitas komputasi, sampai ke perlu adanya koordinasi yang konsisten antar agen.

1.2 Kontribusi dan Struktur Survei

Paper ini ditujukan buat kamu yang pengen tau lebih dalam tentang MADRL. Isinya bakal ngasih tau tentang tantangan-tantangan khusus yang ada di dunia multi-agent deep RL dan solusi terkini untuk ngatasin itu. Selain itu, kita juga bahas tentang arah penelitian masa depan yang mungkin jadi tren.

2. Background

2.1 Single‑agent reinforcement learning

Di bagian ini, kita ngobrolin dasar-dasar dari RL (Reinforcement Learning), bro. Jadi, RL itu fokusnya di belajar sebuah kebijakan kontrol yang bisa mengoptimasi performa numerik lewat pengambilan keputusan. Jadi, agen ini interaksi sama lingkungannya, cobain sesuatu, terus dapet feedback yang bisa dia pake buat improve. Nah, Markov Decision Process (MDP) itu jadi framework-nya.

2.2 Multi‑agent reinforcement learning

Kalo udah masuk ke multi-agent, kita pake Markov Games sebagai framework. Di sini, lebih dari satu agen bisa interaksi di lingkungan yang sama dan mungkin juga satu sama lain. Mereka semua punya tujuan sendiri-sendiri, tapi di akhir hari, mereka semua mau maximize reward mereka dalam jangka panjang.

Kasus Spesial

Ada juga yang namanya strategic-form game, yang basically cuma satu ronde doang. Semua agen ambil tindakan secara simultan, terus dapet reward. Ini cukup populer di komunitas MARL.

Value Function

Di sini, nilai dari sebuah state gak cuma bergantung ke policy dari satu agen, tapi juga dari agen lainnya. Jadi, kalo semua agen belajar secara simultan, best response yang ditemukan bisa jadi gak unik.

Nash Equilibrium

Nah, ini konsep dari teori game yang basically bilang kalo satu agen gak bisa improve performanya kalo policy dari agen lain tetap.

Pareto-optimality

Ini versi lain dari Nash Equilibrium tapi lebih ke arah yang lebih optimal buat semua agen.

Tipe Task dan Informasi

Di literature MARL, kita bisa ngategorikan berdasarkan tipe task dan informasi yang tersedia buat agen. Ada yang fully cooperative, fully competitive, atau mixed setting.

2.3 Pengantar Formal ke Tantangan Multi-Agen

Non-stationarity

Di dunia single-agent, si agen adalah satu-satunya yang punya efek ke keadaan lingkungan. Tapi di dunia multi-agen, semua agen update policy mereka secara barengan. Ini bikin lingkungan jadi kayak berubah-ubah (non-stationary) dari perspektif satu agen. Jadi, masalah yang muncul adalah “moving target problem”.

Nash Equilibrium & Shadowed Equilibrium

Meski Nash Equilibrium bisa jadi solusi, faktanya adalah agen bisa converge ke solusi yang sub-optimal atau malah stuck di tengah-tengah beberapa solusi. Ada juga yang namanya “shadowed equilibrium”, di mana satu kebijakan bisa kalah sama kebijakan lainnya.

Relative Over-generalization

Di fenomena ini, satu Nash equilibrium yang sub-optimal bisa lebih dipilih daripada solusi yang sebenernya lebih optimal. Ini terjadi karena policy dari masing-masing agen performa-nya relatif oke meskipun digabungkan dengan aksi acak dari agen lain.

Partially Observable Markov Games (POMG)

Kadang-kadang, agen nggak bisa ngeliat semua informasi tentang dunia di sekitarnya. Ini bikin mereka harus ngambil keputusan meskipun dalam keadaan nggak pasti. POMG adalah generalisasi dari MG dan MDP untuk kondisi seperti ini.

Credit Assignment Problem

Di game kooperatif, semua agen ditargetkan untuk maximize goal yang sama melalui reward yang sama. Tapi, mereka nggak bisa tau kontribusi mereka sendiri ke reward tersebut. Ini dikenal sebagai “credit assignment problem”.

Penutup

Beberapa masalah ini muncul di semua jenis task (kooperatif, kompetitif, dan campuran), sementara beberapa lainnya lebih sering muncul di setting kooperatif. Untuk mengatasi masalah ini, banyak penelitian yang masih fokus ke dunia-dunia sederhana, karena ini masih jadi lahan subur untuk penelitian lebih lanjut.

3 Analisis Skema Pelatihan

Tantangan Pelatihan Multi-Agen

Pelatihan multi-agen itu komputasinya gak gampang. Karena semakin banyak agen, semakin kompleks juga ruang keadaan dan aksi. Oleh karena itu, pelatihan bisa dibagi menjadi dua paradigma: terpusat (centralized) dan terdistribusi (distributed).

Skema Pelatihan

• Centralized Training: Semua agen saling tukar informasi saat pelatihan. Tapi, info ini biasanya dihilangkan saat fase pengujian.
• Distributed Training: Setiap agen belajar sendiri-sendiri tanpa pake informasi dari agen lain.

Skema Eksekusi

• Centralized Execution: Semua aksi diatur oleh unit terpusat.
• Decentralized Execution: Setiap agen menentukan aksi sendiri berdasarkan kebijakannya.

3.1 Pelatihan Terdistribusi (Distributed Training)

Di skema pelatihan ini, agen-agen belajar secara independen tanpa ada pertukaran informasi. Ini punya kelemahan, yaitu dari sudut pandang satu agen, lingkungannya jadi non-stationary.

Beberapa penelitian awal di area ini fokus pada dunia yang sederhana dan menunjukkan bahwa agen yang belajar secara independen lebih lambat daripada yang bekerja sama. Penelitian lebih baru menunjukkan bahwa metode pelatihan terdistribusi ini kurang efisien, terutama jika jumlah agennya banyak.

Isu dan Solusi

Karena informasi yang terbatas, agen di setting terdistribusi menghadapi berbagai masalah, seperti non-stationarity, transisi atau reward yang stochastic, dan lain-lain. Beberapa penelitian baru mencoba menangani masalah ini. Misalnya:

• Concurrent Experience Replay Trajectories (CERT) untuk membuat sampling lebih stabil.
• Experience Replay dengan Leniency, yang menambahkan faktor optimisme dalam update fungsi nilai.
• Negative Update Intervals Double-DQN, yang mengidentifikasi dan menghapus data yang menyebabkan mis-coordination.

Ada juga pendekatan lain yang menggunakan metode evolusi untuk mengganti agen yang kurang perform dengan versi yang lebih baik.

3.2 Pelatihan Terpusat

Ikhtisar

Metode pelatihan terpusat memungkinkan agen-agen untuk memperbarui kebijakan mereka berdasarkan informasi bersama selama fase pelatihan. Namun, informasi ini biasanya diabaikan pada saat pengujian. Pelatihan terpusat bisa dibagi lebih lanjut menjadi dua skema eksekusi: eksekusi terpusat dan terdesentralisasi.

Jenis Pelatihan Terpusat

1. Pelatihan Terpusat Eksekusi Terpusat (CTCE):
   • Definisi: Dalam skema ini, sebuah eksekutor terpusat memodelkan kebijakan gabungan, yang memetakan kumpulan observasi dari semua agen menjadi sejumlah distribusi atas tindakan individu.
   • Kelebihan: Memungkinkan penggunaan metode pelatihan agen tunggal seperti aktor-kritik atau algoritma gradien kebijakan.
   • Kekurangan: Ruang tindakan dan keadaan tumbuh secara eksponensial dengan jumlah agen, yang bisa menjadi masalah skalabilitas. Ini juga bisa menghasilkan apa yang disebut “agen malas”, di mana satu agen belajar kebijakan yang baik sementara agen lain kurang termotivasi untuk melakukan hal yang sama.
2. Pelatihan Terpusat Eksekusi Terdesentralisasi (CTDE):
   • Definisi: Setiap agen memiliki kebijakan individu yang memetakan observasi lokal ke distribusi atas tindakan individu. Selama pelatihan, agen diberi informasi tambahan yang kemudian diabaikan saat pengujian.
   • Kelebihan: Merupakan pendekatan yang paling banyak digunakan dan telah berhasil dalam banyak aplikasi. Metode ini juga bisa mengatasi masalah non-stasioneritas.
   • Kekurangan: Agen harus berbagi informasi selama pelatihan, yang bisa menjadi masalah jika komunikasi antar agen terbatas atau mahal.

Penerapan dalam Agen Homogen dan Heterogen

• Agen Homogen: Parameter bisa dibagikan antar agen, memungkinkan pelatihan yang lebih efisien.
• Agen Heterogen: Berbagai teknik seperti aktor-kritik terpusat bisa digunakan untuk meningkatkan kinerja kebijakan agen individu.

Kesimpulan

Pelatihan terpusat menawarkan beberapa keuntungan dalam hal efisiensi dan efektivitas pelatihan, tetapi juga hadir dengan tantangan dan kekurangannya sendiri. Pilihan antara CTCE dan CTDE, serta antara agen homogen dan heterogen, akan tergantung pada kebutuhan dan keterbatasan spesifik dari masalah yang dihadapi.

4. Pola Perilaku Agen yang Muncul

Ikhtisar

Agen-agen dalam sistem multi-agen cenderung mengembangkan perilaku tertentu berdasarkan interaksi dinamis dan struktur pahala yang telah dirancang. Perilaku ini bisa bersifat kooperatif atau kompetitif, tergantung pada bagaimana sistem pahalanya dirancang.

4.1 Struktur Pahala

Pahala tim yang lebih tinggi dibandingkan dengan pahala individu cenderung mendorong agen untuk berkolaborasi. Sebaliknya, jika pahala untuk kinerja individu lebih tinggi, agen akan cenderung bersaing. Dalam kasus pahala yang jarang muncul, agen bisa dilengkapi dengan fungsi pahala intrinsik untuk memberikan sinyal umpan balik yang lebih sering.

4.2 Bahasa

Perkembangan bahasa dan kemampuan komunikasi agen menarik perhatian besar. Penelitian telah menunjukkan bahwa agen dapat mempelajari protokol komunikasi hanya melalui interaksi. Bahasa yang muncul dalam dialog antar agen juga telah dipelajari, termasuk di dalamnya negosiasi dan pertanyaan-jawaban.

4.3 Konteks Sosial

Beberapa studi juga telah mempertimbangkan perkembangan komunikasi dalam dilema sosial. Metrik untuk menilai kualitas protokol komunikasi yang dipelajari juga telah diajukan.

Kunci Temuan

• Kooperatif vs Kompetitif: Struktur pahala mempengaruhi apakah agen akan berkolaborasi atau bersaing.
• Pahala Intrinsik: Mereka bisa digunakan untuk mengatasi masalah pahala yang jarang muncul dalam lingkungan.
• Perkembangan Bahasa: Agen bisa mempelajari protokol komunikasi dan bahasa abstrak melalui interaksi.
• Komunikasi dalam Konteks Sosial: Penelitian telah mulai menggali bagaimana komunikasi berkembang dalam konteks sosial dan dilema sosial.

Implikasi

Pola perilaku yang muncul ini penting untuk dipahami karena mereka berdampak langsung pada bagaimana agen-agen dalam sistem multi-agen akan berinteraksi dan menyelesaikan tugas secara kolektif atau individu. Selain itu, pemahaman ini penting untuk desain sistem yang lebih efisien dan efektif.

• Penelitian dalam MARL juga melihat bagaimana agen berperilaku dalam konteks sosial.
• Sosial dilema sebagai skenario konflik antara keuntungan individu dan kolektif.
• Berbagai dimensi psikologis, seperti kepercayaan dan dampak emosi, juga diteliti.

5 Tantangan Saat Ini

5.1 Non-stasionaritas

• Karena banyak agen yang belajar secara bersamaan, lingkungan menjadi non-stasioner.
• Beberapa pendekatan untuk mengatasi ini termasuk penggunaan experience replay, unit terpusat, dan meta-learning.

5.2 Pembelajaran Komunikasi

• Kemampuan untuk mengembangkan bahasa dan komunikasi adalah salah satu tantangan utama.
• Tiga skenario komunikasi: broadcasting, targeted, dan networked.

5.3 Koordinasi

• Koordinasi sukses antar agen memerlukan konsensus.
• Cara untuk mencapai ini termasuk pembelajaran independen, membangun model dari agen lain, dan metode hierarkis.

5.4 Masalah Penugasan Kredit (Credit Assignment Problem)

Berbicara tentang bagaimana memberikan “kredit” atau imbalan kepada masing-masing agen dalam lingkungan multi-agen. Tiga pendekatan utama dibahas:

1. Dekomposisi: Fokus pada pembagian imbalan berdasarkan kontribusi agen.
2. Marginalisasi: Menggunakan fungsi tambahan untuk mengurangi efek dari tindakan individu agen.
3. Inverse Reinforcement Learning: Belajar dari perilaku ahli untuk memperbaiki masalah penugasan kredit.

5.5 Skalabilitas

Menjelaskan tantangan dalam melatih sejumlah besar agen dan bagaimana menangani mereka:

1. Penggunaan Kembali Pengetahuan (Knowledge Reuse): Teknik seperti pembagian parameter dan transfer learning.
2. Pengurangan Kompleksitas: Membagi masalah menjadi sub-masalah yang lebih kecil.
3. Ketahanan (Robustness): Membuat kebijakan yang tangguh terhadap gangguan, misalnya melalui pelatihan adversarial.

5.6 Observabilitas Parsial

Menjelaskan bagaimana agen beroperasi ketika mereka hanya dapat mengamati sebagian dari lingkungan:

1. Mekanisme Komunikasi: Agen dapat berkomunikasi untuk mengisi kekurangan informasi.
2. Mekanisme Memori: Menggunakan jaringan saraf berulang untuk membantu agen mengingat dan menggunakan informasi dari masa lalu.

6 Diskusi

Tren

1. Pembelajaran Kurikulum: Menggunakan kurikulum untuk memecah proses pembelajaran menjadi tahapan yang lebih mudah dikelola.
2. Deep Neural Networks dengan Unit Rekurensi: Digunakan untuk mengingat pengalaman dan sejarah transisi keadaan.
3. Komunikasi antar Agen: Fokus pada pengembangan keterampilan komunikasi di antara agen.
4. Paradigma CTDE (Centralized Training, Decentralized Execution): Memungkinkan berbagi informasi selama pelatihan untuk memitigasi beberapa masalah utama dalam MADRL.

Pekerjaan Masa Depan

• Pembelajaran Multi-Tujuan: Di mana setiap agen memiliki tujuan individu.
• Pembelajaran Multi-Tugas: Agen diharapkan untuk melakukan beberapa tugas yang terkait.
• MADRL yang Aman: Menjaga keamanan selama pembelajaran dan penerapan adalah prioritas tinggi.
• Metodologi Evolusi: Digunakan dalam konteks multi-agen RL.

Dua masalah utama yang diidentifikasi adalah “Kutukan Dimensi” dan eksplorasi yang memadai dalam ruang yang sangat besar dan kompleks.

7 Kesimpulan

MADRL adalah bidang yang muda dan berkembang pesat, dengan banyak masalah yang belum terpecahkan tetapi menjadi semakin dapat diatasi berkat metode deep learning. Artikel ini bertujuan untuk memberikan alat yang diperlukan untuk memahami tantangan kontemporer di MADRL.

Sumber

https://link.springer.com/article/10.1007/s10462-021-09996-w

---

---

---