Politika Gradyanı Metodlarına Başlama Rehberi -1
Reinforcement Learning Türkiye {yazar : Umut Can Altın}
Girişi çok uzatmadan hemen konuya geçelim, gelecek yeni yazılarımızda kafanıza takılan soruları tamamlıyor olacaksınız. Bir çoğumuzun da bildiği gibi Pekiştirmeli Öğrenme alanına girer girmez karşımıza value function(değer fonksiyonu) ibaresi çıkıyor. Kimi zaman Q(s,a) (aksiyon-değer fonksiyonu) , kimi zaman V(s) (değer fonksiyonu) olarak. Ve çoğumuz değer fonksiyonlarından yararlanılarak aksiyon alımı sağlayan politikalara aşinayız. Yaptığımız şey genel hatlarıyla aksiyon-değer fonksiyonunu öğrenmek ve bu fonksiyon tahminleri üzerinden bizim için en iyi olan hareketi aksiyonu seçmekti. Yani politikamız Q(s,a) tahminimiz olmadan var olamazdı. Bu yazımızda Politika Gradyanı metodlarına giriş yapıyor ve sizi bir adım ileri götürüyoruz. Yani bu yazıda, bir değer fonksiyonuna danışmadan eylemleri seçebilen, kendi parametrelerine sahip politikalar üzerine duracağız.
Kısaca politika parametresini, skaler performans ölçüsü J(θ)’nın politika parametresine göre gradyanını temel alarak öğrenme sağlayan yöntemleri düşünüyoruz. Bu yöntemler ile performansı maksimize etmeye çalışacağız yani gradyan düşüşü yerine aşağıda verilmiş olan yaklaşık gradyan yükselişi bizim işimize yarayacak.
Bu genel şemayı izleyen tüm yöntemlere(değer fonksiyonu olsun veya olmasın) politika gradyan yöntemleri diyoruz. Hem politika hem de değer fonksiyonu yaklaşımları öğrenen yöntemlere de aktör kritik yöntemler denilmekte. “aktör” öğrenilen politikaya bir referans, “eleştirmen(kritik)” ise öğrenilen değer fonksiyonuna bir referanstır.
Aksiyon uzayı kesikli ve çok büyük değilse, o zaman her durum-aksiyon çifti için sayısal tercihler oluşturmak doğal ve yaygın bir parametreleştirmedir. Her durumda en yüksek tercihlere sahip eylemlere, örneğin üstel softmax dağılımına göre, en yüksek seçilme olasılığı verilir:
Buradaki payda sayesinde her bir durumdaki eylem olasılıkları toplamı birdir. Aksiyon tercihlerinde bu tür bir politika parametrelemesine softmax diyebiliriz. Politikaları aksiyon tercihlerinde softmax kullanmanın bir avantajı, yaklaşık politikanın deterministik bir politikaya yaklaşabilmesidir, oysa aksiyon-değer fonksiyonuna(Q(s,a)) bakarak epsilon-greedy aksiyon seçimi ile her zaman rastgele bir eylem seçme olasılığı vardır.
Önemli fonksiyon yaklaşımı ile ilgili problemlerde, en iyi yaklaşık politika stokastik olabilir. Örneğin, eksik veya kusurlu bilgilere sahip kart oyunlarında en uygun oyun genellikle belirli olasılıklarla iki farklı şey yapmaktır. Aksiyon-değer tabanlı yöntemler ile stokastik optimal politikaları bulmanın bir yolu yoktur.
Bu kadar şey konuştuktan sonra kısaca çok basit bir şekilde şunu söylemek gerekir. Bazı problemlerde her durumda alınabilecek her hareketin değerini öğrenmektense sadece politikayı öğrenmek daha kolay olabilir. Ayrıca politika gradyanı yaklaşımında politikamız yavaş bir güncelleme yaşayacak bu sayede ani değişimler yerine aksiyon olasılıklarında küçük değişmeler yaşanacaktır.
DDeterministicPG gibi deterministik algoritmalardan gelenler için hatırlatalım bu yazıda politikamız stokastik. Yani her aksiyon için bir olasılık değeri çıktısı(toplamı 1 olmalı).
Politika Gradyanı Teoremi
Performans ölçüsünü bölümün başlangıç durumunun değeri olarak tanımladığımız epizodik durumu ele alıyoruz. Her bölümün belirli (rastgele olmayan) bir durum s0'da başladığını varsayarak, notasyonu anlamlı bir genelliği kaybetmeden basitleştirebiliriz:
Yani performans ölçümüzü belirli s_0 nun belirli bir politika altındaki değer fonksiyonu olarak düşünüyoruz.
Sorun, performansın hem aksiyon seçimlerine hem de bu seçimlerin yapıldığı durumların dağılımına bağlı olması ve her ikisinin de politika parametresinden etkilenmesidir. Politikanın durum dağılımı üzerindeki etkisi çevrenin bir fonksiyonudur ve genellikle bilinmemektedir. Gradyan, politika değişikliklerinin durum dağılımı üzerindeki bilinmeyen etkisine bağlı olduğunda, politika parametresine göre performans gradyanını nasıl tahmin edebiliriz? Bu soruna çözüm olarak politika gradyanı teoremi basit matematiksel eşitliklere dayanan bir kanıt göstermekte ve durum dağılımını gradyan alanından çıkarmaktadır. Kanıtı sırası ile inceleyelim:
Politika pi’nin değer fonksiyonu V(s), s durumunda alınabilecek aksiyonların olasılıkları*bu durum-aksiyon ikilisi için q değeri olarak tanımlanmış. Kısaca açalım ama Value- Policy iteration bölümüne göz atarsanız iyi olur. Yani her hareketin q değerini o hareketin gelme olasılığı ile çarpıp bunların toplamını almak zaten bize bu durumun değer fonksiyonunu sağlamıştır. Ardından denklemin iki tarafının gradyanı alınmış.
Şimdi eşitliğin sol tarafında gradyanı dağıtalım. Çok basit hatırlarsanız ilk terimin gradyanı çarpı ikinci terim, artı birinci terim çarpı ikinci terimin gradyanı:)
Açılımımızın sol tarafını şimdilik sabit bırakalım ve sağ tarafı tekrar açalım. sağ tarafta politika ve q değerinin gradyanı duruyor. Gradyanı bir kenara bırakıp q değerimizi açalım. Bir hareketin Q değeri, o hareket alındığı zaman karşımıza gelebilecek yeni durumların gelme olasılıkları ile bu durumda aldığımız ödül ve yine aynı politikaya bağlı kalarak yeni durumun değerinin toplamının çarpımlarının toplamına eşit. Evet biraz karışık oldu. Kısaca şöyle özetleyelim. Diyelim ki benim s durumunda a1 ve a2 hareket seçeneklerim var ve eğer a1 i seçersem %30 olasılıkla s1 ve r_1, %70 olasılıkla s2 ve r_2 durumu ve ödülü yeni durum ve ödül olarak karşıma çıkacak. Eğer a2 yi seçersem ise %70 olasılıkla s1 ve r_1, %30 olasılıkla s2 ve r_2 karşıma çıkacak. Varsayalım ki V(s1) = 0.5 ve V(s2)= 0.2. O zaman küçük bir matematiksel hesapla Q(s,a1)= 0.3*(r1+0.5) + 0.7(r2+0.2) olacaktır. Q(s,a2) ise 0.7*(r1+0.5) + 0.3(r2+0.2).
Şimdi gradyanı toplam toplamın içerisine değer fonksiyonuna aldık. Bunu yapabildik çünkü ortamın geçiş olasılıkları veya ödül theta ya bağlı değil ve biz gradyanımızı thetaya bağlı aldık. Aynı zamanda değişen olasılık gösterimleri aynı olduğu için bir sorun teşkil etmiyor.
Zaten eşitliğin sol tarafında V(s) gradyanı varken şimdi ssağ tarafta da V(s’) gradyanı kaldı. Bunu bir açalım. Şimdi bu denklem öyle bir hal aldı ki bu açıldıkça açılacak.
O zaman kısaca şöyle bir gösterim kullanarak işimizi çok kolaylaştırabiliriz. Pr, politika altında k adımlarında s durumundan x durumuna geçme olasılığıdır.
Buradaki sembol “orantılı” anlamına gelir. Buradaki µ dağılımı, pi altındaki politikadaki dağılımdır.
Bu sayede elde ettiğimiz yeni orantıda durum dağılımının gradyanını bilmemize gerek kalmamıştır.
Yukarıdaki ifade artık bir sabiti gösterdiği için orantı durumunda elemesini yapabiliriz.
ref : Sutton & Barto Book: Reinforcement Learning: An Introduction