Mengapa Satu Strategi Saja Tidak Cukup: Portofolio Kebijakan Adaptif untuk MDP yang Tangguh
Proses keputusan Markov (MDP) klasik mengasumsikan bahwa dinamika lingkungan diketahui secara pasti. Dalam praktiknya, hal ini hampir tidak pernah terjadi: kita hanya dapat menguraikan serangkaian skenario yang masuk akal. MDP yang tangguh (robust MDP) menyikapi hal ini secara radikal — mencari satu kebijakan yang akan bekerja cukup baik pada transisi terburuk yang mungkin terjadi. Namun, pendekatan ini memiliki harga tersembunyi: pendekatan ini disetel untuk kasus terburuk dan karena itu sering kali terlalu konservatif.
Hal ini terutama terlihat dalam situasi di mana ketidakpastian berkurang seiring waktu. Lingkungan terbentang di hadapan agen, dan sebagian dinamikanya menjadi dapat diamati dan teridentifikasi sebagian. Kebijakan optimal yang dihitung sebelum penyingkapan tidak memanfaatkan informasi baru ini. Pada dasarnya, kita terus bermain untuk kasus terburuk bahkan di tempat yang sudah kita ketahui bahwa hal itu tidak terjadi. Para peneliti dari Universitas Twente dan Antwerpen — Kasper Engelen, Sebastian Junges, Guillermo A. Pérez, dan Marnix Suilen — dalam karya mereka «Adaptive Policy Portfolios for Robust Markov Decision Processes» (arXiv:2608.17929, cs.AI/cs.LO) mengusulkan pendekatan yang lebih fleksibel.
Portofolio Adaptif: Satu Set Kebijakan, Bukan Satu Kebijakan
Alih-alih satu kebijakan yang tangguh, para penulis mempertimbangkan portofolio kebijakan — serangkaian kebijakan acak tanpa memori yang terbatas, yang disintesis sebelumnya, secara offline. Sebagai tambahan, digunakan pemilih online yang ringan, yang memilih kebijakan yang paling sesuai dari portofolio selama proses berlangsung. Ini mengingatkan pada ansambel model dalam pembelajaran mesin, tetapi dengan perumusan teoretis yang jelas.
Metrik kunci kualitas portofolio semacam itu menjadi penyesalan yang tangguh (robust regret). Untuk setiap lingkungan spesifik dari rangkaian skenario yang masuk akal, metrik ini mengukur seberapa besar kebijakan yang dipilih oleh pemilih online kalah dari kebijakan ideal yang akan kita bangun jika kita mengetahui lingkungan tersebut sebelumnya. Dengan kata lain, portofolio dianggap baik jika peserta terbaiknya cukup dekat dengan optimum untuk lingkungan apa pun. Pandangan ini menggeser penekanan dari jaminan kasus terburuk ke harga adaptasi.
Ide serupa sebelumnya dikembangkan oleh Ghavamzadeh et al. (2016), tetapi dengan fokus pada metode perkiraan dan relaksasi untuk peningkatan kebijakan yang aman. Karya baru ini secara signifikan memajukan fondasi teoretis bidang ini.
Kompleksitas Sertifikasi dan Sintesis
Portofolio bukan sekadar heuristik rekayasa. Para penulis memberikan analisis kompleksitas teoretis yang cermat terhadap masalah yang muncul saat bekerja dengan portofolio.
Masalah pertama adalah sertifikasi portofolio yang diberikan: dapatkah kita menjamin bahwa untuk semua lingkungan yang masuk akal akan ada kebijakan dengan penyesalan yang dapat diterima? Ternyata, masalah ini ∀R-lengkap bahkan untuk portofolio deterministik dalam RMDP asiklik (s,a)-persegi panjang. Ini berarti bahwa memeriksa kualitas bahkan sekumpulan kecil kebijakan adalah tugas komputasi yang berat, sebanding dalam kompleksitasnya dengan menyelesaikan sistem pertidaksamaan bilangan real.
Yang lebih sulit lagi adalah masalah sintesis portofolio berukuran terbatas (unary-bounded). Untuk politop rasional umum, masalah ini ternyata ∃∀R-lengkap — bahkan dengan faktor diskon tetap dan dinamika asiklik. Kompleksitas semacam itu menunjukkan bahwa algoritma kombinatorial sederhana tidak ada di sini: masalah ini menggabungkan pencarian diskrit dan kompleksitas aljabar. Yang perlu diperhatikan, bahkan kasus satu kebijakan pun tidak sepele dan «mahal» di kedua sumbu.
Bagaimana Mendekatkannya ke Praktik?
Hasil kompleksitas yang diperoleh mungkin tampak menakutkan, tetapi para penulis tidak berhenti pada kesimpulan negatif. Mereka mengusulkan konstruksi portofolio offline yang konkret yang memungkinkan spesialisasi saat runtime (runtime specialization). Idenya adalah menyiapkan serangkaian kebijakan terlebih dahulu, lalu selama interaksi dengan lingkungan, dengan cepat menyesuaikan pilihan dengan pengamatan saat ini. Pendekatan semacam itu memungkinkan penggabungan jaminan yang ketat dengan fleksibilitas praktis.
Kesimpulannya sederhana: dalam tugas-tugas di mana ketidakpastian sebagian terungkap seiring waktu, satu strategi yang ditetapkan pasti lebih lemah daripada serangkaian kebijakan adaptif. Portofolio kebijakan membayar dengan kompleksitas komputasi yang lebih tinggi, tetapi memberi hak untuk membuat kesalahan dan kemampuan untuk beralih seiring datangnya data. Ini adalah langkah penting dalam perjalanan dari metode yang murni konservatif menuju sistem pengambilan keputusan yang cerdas dalam kondisi ketidakpastian.
