Pekiştirmeli Öğrenmeye Giriş

Pekiştirmeli öğrenmeyi tanımlayalım ve bir pekiştirmeli öğrenme sisteminin bileşenlerini detaylıca konuşalım.

Pekiştirmeli öğrenme, ardışık karar alma süreçlerinin optimizasyonuyla ilgilenen makine öğrenmesi dalıdır. Pekiştirmeli öğrenme birçok farklı yönetim, kontrol ve yapay zeka uygulamasına yaygın ve başarılı bir şekilde uygulanmıştır. Son zamanlarda robotları, otonom araçları ve pilotsuz uçakları kontrol etmede ve yönlendirmede vazgeçilmez hale gelmiştir. Ayrıca oyun oynamada da kayda değer başarılar elde etmiştir. Pekiştirmeli öğrenme sayesinde bilgisayar otomasyonlu video oyunları, tavla ve satranç oynama uygulamalarının en iyi insan oyuncuları yenebilmesi sağlamıştır.

Bu yazıda, temel metodolojileri ve uygulama alanlarını çalışarak pekiştirmeli öğrenmeye genel bir bakış sunacağız. Ayrıca, pekiştirmeli öğrenmenin klasik kontrol teorisiyle ilişkisini gözden geçireceğiz ve yüksek verimli veri ortamlarına uygulandığında bu eski yöntemlerin önemli dezavantajlarının nasıl üstesinden gelinebileceğini öğreneceğiz.

Basit Açıklama

“Öğrenme” terimi, algoritmanın açıkça programlanmadığını, ancak verilerden ilgili ilişkileri kendi kendine öğrendiğini ifade eder. Bilgisayarlar genellikle karar alma, tahmin, sınıflandırma veya desen tanıma görevlerini otomatikleştirmek için kullanılır. Makine öğrenmesi, bir bilgisayarın bu görevleri, genellikle gerçek veya simüle edilmiş verilerden edinilen deneyimlerden öğrenmesini sağlayan algoritmaların geliştirilmesini içerir. Öğrenme, temel algoritmaların verilere veya matematiksel modellere dayalı olarak bu görevlerin performansını optimize etme yeteneğini ifade eder.

Makine Öğrenmesi Dalları

Makine öğrenmesi üç ana dala ayrılabilir: gözetimli öğrenme, gözetimsiz öğrenme ve pekiştirmeli öğrenme.

Gözetimli Öğrenme: Gözetimli öğrenmede algoritmalar, etiketli verilerden öğrenir. Örneğin, el yazısı bir harfi tanımak için bir sistem eğitmek isterseniz, eğitim verileri olarak etiketli harf örneklerini sağlarsınız. Amaç, bir sınıflandırıcı veya bir regresyon modeli oluşturmaktır. Sınıflandırıcılar, girdi ile çıktı arasında bir eşleme yapar. Eğitim sürecinde kullanılan veri, test verileriyle doğrulanır. Gözetimli öğrenmenin kritik bir aşaması, özellik seçimi adı verilen bir adımdır. Bu adımda, problemle ilgili olmayan ya da gereksiz bilgiyi içeren özellikler ayıklanır. Örneğin, bir müşterinin kredi riskini tahmin etmek için doğum yeri gibi bir özelliğin faydasız olduğunu belirleyebiliriz.

Gözetimsiz Öğrenme: Gözetimsiz öğrenme, etiketlenmemiş verilerdeki desenleri ve ilişkileri keşfetmek için kullanılır. Genellikle kümeleme (clustering) gibi yöntemlerle, benzer özelliklere sahip veri grupları oluşturulur. Bu tür öğrenme, keşif analizi ve ileri düzey modellerin geliştirilmesi için bir temel sağlar. Örneğin, bir el yazısı karakter sınıflandırma uygulamasında, gözetimsiz öğrenme algoritması bir belge üzerindeki bireysel karakterleri ayıklayabilir ve bu karakterler daha sonra sınıflandırıcıya girdi verisi olarak kullanılabilir.

Pekiştirmeli Öğrenme: Pekiştirmeli öğrenme, ardışık karar verme süreçleri için geliştirilmiş bir öğrenme yöntemidir. Bu süreçte, bir ajan, çevresiyle etkileşim kurarak öğrenir. Amaç, bir ödül veya maliyet fonksiyonunu optimize eden bir karar dizisi geliştirmektir. Pekiştirmeli öğrenme, dinamik programlama gibi tekniklere dayanır ve genellikle otonom araç kontrolü, oyun oynama, robotik veya sağlık hizmetleri gibi uygulamalarda kullanılır. Örneğin, bir otonom araç navigasyonu uygulamasında, araç sürekli olarak kararlar alır (örneğin, hızlanma, fren yapma, dönüş yapma). Bu kararlar zaman içinde ödülleri (örneğin, güvenli sürüş) maksimize edecek şekilde optimize edilir. Pekiştirmeli öğrenme, derin sinir ağlarıyla birleştirildiğinde (derin pekiştirmeli öğrenme), AlphaZero gibi programların geliştirilmesinde kullanılabilir. AlphaZero, sadece birkaç saat içinde insan bilgisini aşan bir satranç oyunu stratejisi geliştirmiştir.

Dinamik Programlama

SDP (Stokastik Dinamik Programlama)

SDP, sıralı aşamalardan oluşur; her aşamada bir karar alınır ve bir maliyet veya ödül söz konusudur. Süreç, durumlar arasındaki geçişlerden oluşur ve eylem uzayından (A) seçilen bir eylemle karar alınır.

Durum ve Eylemler

• Durum uzayı X: Tüm olası durumların kümesidir.
• Eylem uzayı A: Her durum için mümkün olan eylemler kümesi Ax​’dir.
• Durum-eylem çifti: (xj,aj) ile gösterilir.

Maliyet ve Geçişler

Maliyet (veya ödül) fonksiyonu: R(x,a), her durum-eylem çiftine bir maliyet veya ödül atar.

Geçişler

• Stokastik Geçişler: Gelecek durum bir olasılık dağılımına bağlıdır (P(y∣x,a)).
• Deterministik Geçişler: Gelecek durum bir fonksiyonla belirlenir (x_j+1=q(xj,aj)).

SDP Türleri

Sonlu Ufuklu SDP: Sabit aşama sayısı K bulunur.

Sonsuz Ufuklu SDP: Süresiz devam eden bir süreçtir.

En Kısa Yol SDP: Aşama sayısı değişkendir; terminal duruma ulaşıldığında süreç sona erer.

İndirimli ve İndirimsiz Maliyet:

• İndirimli maliyet: Gelecekteki maliyetler bir indirim faktörü (β∈[0,1]) ile azaltılır.
• Sonsuz ufuklu problemler için genellikle β<1.
• İndirimsiz maliyet: β=1.

Optimizasyon Hedefi:

• Amaç: Maliyeti minimize etmek veya ödülü maksimize etmek.
• Maksimum ödül problemleri, maliyet fonksiyonu R(x,a)’nin −R(x,a) ile çarpılmasıyla minimum maliyet problemine dönüştürülebilir.

SDP Politikaları:

• Politika: Her aşamada eylemleri belirleyen bir yöntem.
• Durağan Politika: Tüm aşamalarda aynı karar kuralını uygular (ϕ(x)).
• Optimum Politika: Tüm başlangıç durumları için maliyeti minimize eden veya ödülü maksimize eden politika (ϕ∗).

Belleksiz SDP:

• Gelecekteki davranış ve maliyet yalnızca mevcut durum-eylem çiftine bağlıdır.
• SDP belleksizse, optimum politika da durağan ve belleksizdir.

Dinamik programlamanın temeli, süreçlerin sistematik olarak modellenmesi ve optimizasyon problemine uygun politikaların belirlenmesidir.

Markov Karar Süreçleri

Markov Karar Süreci (MDP): Sonsuz ufuklu, stokastik bir karar verme modelidir. Bir durum-eylem uzayı K, maliyet/ödül fonksiyonu R(x,a), olasılık geçiş çekirdeği P(y∣x,a), ve indirim faktörü β ile tanımlanır.

Özellik: Belleksizdir, yani kararlar sadece mevcut duruma bağlıdır (Markov özelliği).

Hedef: En iyi politikayı (eylem planını) bulmak ve toplam ödülü maksimize etmek veya toplam maliyeti minimize etmektir.

Politika Değerlendirme

Amaç:Verilen bir politika ϕ’nin değer fonksiyonunu Vϕ(x) hesaplamak.

Formül: Vϕ(x) = R(x, ϕ(x)) + β ∑[y] Vϕ(y) P(y | x, ϕ(x))

Bu denklem, belirli bir karar verme sürecinde değer fonksiyonu Vϕ(x)’i temsil eder:

• Vϕ(x): Durum x’te olup, ϕ politikasını takip ederken elde edilen değeri ifade eder.
• R(x, ϕ(x)): Durum x’teyken ve ϕ(x) politikasına göre eylem yaptığınızda elde edilen anlık ödül.
• β: Gelecekteki ödüllere verilen indirim faktörü. Genellikle 0 ile 1 arasında bir değeri vardır ve gelecekteki ödüllere ne kadar ağırlık verileceğini belirtir.
• ∑[y]: Olası tüm sonraki durumlar y üzerinde yapılan toplamdır.
• Vϕ(y): Sonraki durum y’nin, aynı ϕ politikası altında elde edilen değeridir.
• P(y | x, ϕ(x)): Durum x’ten, ϕ(x) politikasına göre y durumuna geçiş olasılığıdır.

Çözüm: Banach Sabit Nokta Teoremi’ne göre bu denklem tek bir çözümle sonuçlanır. Yinelemeli yöntemlerle bu çözüm bulunabilir.

Politika İyileştirme

Politikayı, her durum için en iyi eylemi seçerek geliştiririz.

Q-faktörü şu şekilde tanımlanır:

Qϕ(x, a) = R(x, a) + β ∑[y] Vϕ(y) P(y | x, a)

Bu denklem, x durumunda a eylemini yaparken elde edilen beklenen değeri (Q-değeri) temsil eder, yani ϕ politikasına göre:

• Qϕ(x,a): Durum x’te a eylemini gerçekleştirmenin beklenen değeri.
• R(x,a): Durum x’te a eylemi ile alınan anlık ödül.
• P(y∣x,a): Durum x’te a eylemi yapıldığında, y durumuna geçiş olasılığı.

Amacımız, her x durumu için Qϕ(x,a) değerlerini minimize eden a∗(x) eylemini seçmektir. Yani, optimal eylem a∗(x), hem anlık ödülleri hem de gelecekteki değerleri dikkate alarak en yüksek uzun vadeli getiri sağlayan eylemdir.

Buna göre, yeni politika şu şekilde tanımlanır:

ϕ’(x) = a^*(x)

Bu, güncellenmiş politikanın her x durumu için a∗(x) eylemini seçmek olduğunu gösterir.

Optimal Politika (ϕ∗): Optimal politika, en iyi toplam ödülü sağlayan stratejidir.

Bellman Denklemi

Optimal değer fonksiyonu şu şekilde tanımlanır:

𝑉∗(𝑥) = minₐ { 𝑅(𝑥, 𝑎) + 𝛽 ∑𝑦 𝑉∗(𝑦) 𝑃(𝑦|𝑥, 𝑎) }

V∗(x) = minₐ { R(x, a) + β ∑𝑦 V∗(y) P(y|x, a) }

Burada:

𝑉∗(𝑥): Durum 𝑥 için optimal değer fonksiyonu,

𝑅(𝑥, 𝑎): Durum 𝑥 ve eylem 𝑎 ile elde edilen anlık ödül,

𝛽: İndirim faktörü (0 < β < 1),

𝑃(𝑦|𝑥, 𝑎) : 𝑥 durumunda 𝑎 eylemini gerçekleştirdikten sonra 𝑦 durumuna geçme olasılığı.

Değer ve Politika Yinelemesi

Değer Yinelemesi

Optimal değer fonksiyonu 𝑉∗, sabit nokta yinelemeleriyle şu şekilde hesaplanır:

𝑉𝑛+1(𝑥) = minₐ { 𝑅(𝑥, 𝑎) + 𝛽 ∑𝑦 𝑉𝑛(𝑦) 𝑃(𝑦|𝑥, 𝑎) }

Vn+1(x) = minₐ { R(x, a) + β ∑𝑦 Vn(y) P(y|x, a) }

Burada 𝑛, yineleme sayısını ifade eder.

Politika Yinelemesi

Politika yinelemesinde, politika ve değer fonksiyonları sırayla güncellenir:

1. Mevcut politikayı değerlendir:
   Belirli bir politika için değer fonksiyonu hesaplanır.
2. Politikayı iyileştir:
   Değer fonksiyonuna dayanarak daha iyi bir politika seçilir.

Bu işlem, optimal politikayı bulana kadar tekrarlanır.

Zorluklar ve Pekiştirmeli Öğrenme

• Zorluklar: Çok büyük durum ve eylem uzayları. Geçiş olasılıkları ve ödüller bilinmeyebilir.
• Pekiştirmeli Öğrenme: MDP teorisine dayanır ancak dinamik programlamanın pratikteki sınırlamalarını (örneğin bellek ve model belirsizlikleri) aşabilir.

Öğrenme sürecinde keşif (exploration) ve sömürü (exploitation) olmak üzere iki temel davranış biçimi kullanılır. Keşif, deneme yanılma yoluyla yeni stratejiler öğrenmeyi hedeflerken, sömürü öğrenilen stratejileri uygulayarak ödülleri en üst düzeye çıkarmayı amaçlar. Pekiştirmeli öğrenme algoritmaları, bu iki davranışı dengelemek için farklı yaklaşımlar kullanır:

Politika Bağımlı (On-policy) Algoritmalar: Bu algoritmalar, hem optimal bir politika oluşturmayı hem de süreç boyunca optimal ödülleri elde etmeyi hedefler. Örneğin, simüle edilmiş oyun rakipleri geliştirmede bu yaklaşım kullanılır.

Politika Bağımsız (Off-policy) Algoritmalar: Bu algoritmalar, sadece optimal bir politika öğrenmeyi amaçlar ve öğrenme sürecinde optimal ödülleri elde etmeyi gerektirmez. Envanter yönetimi simülasyonları bu yaklaşıma örnek olarak verilebilir.

Pekiştirmeli Öğrenme Sistemlerinin Bileşenleri: Pekiştirmeli öğrenme sistemlerinde, politika değerlendirmesi önemli bir rol oynar. Bir politika değer fonksiyonu olan Vϕ, bir başlangıç durumundan bitiş durumuna kadar biriken toplam maliyeti temsil eder. Bu maliyet, rastgele bir değişkendir ve simülasyonlar tekrarlanarak ortalaması hesaplanır. Monte Carlo politika değerlendirmesi, ajanın bir politikayı uyguladığında çevreden gelen toplam ödülleri gözlemleyerek bir politika değer fonksiyonu tahmin etme yöntemidir. Bu yöntemin iki farklı yaklaşımı vardır: “ilk ziyaret” yöntemi ve “her ziyaret” yöntemi. İlk ziyaret yöntemi, bir durumun bir bölüm içinde ilk kez ziyaret edildiğinde hesaplanan maliyetleri kullanırken, her ziyaret yöntemi tüm maliyetleri kullanır.

Yinelemeli Güncelleme: Pekiştirmeli öğrenmede, tahminleri yinelemeli olarak güncellemek için bir formül kullanılır. Bu güncelleme kuralı şu şekilde ifade edilir:

[yeni tahmin] = [eski tahmin] + [adım boyutu] × ([hedef]−[eski tahmin])

Burada, hedef, güncellemenin yönlendirilmek istendiği niceliği temsil ederken, adım boyutu, güncellemenin büyüklüğünü kontrol eder. Genellikle adım boyutu, öğrenme oranı olarak da bilinir ve yavaşça sıfıra düşmesine izin verilir. Monte Carlo politika değerlendirme yönteminde hedef, bir bölüm tarafından varsayılan toplam maliyettir.

Önyükleme (Bootstrapping) ve Önyargı-Varyans Dengesi: Pekiştirmeli öğrenmede, bir hedef olarak r_{k+1} + βVϕ(x_{k+1}) kullanılabilir. Ancak Vϕ(x_{k+1}) bilinmediği için, onun yerine bir tahmini V^ϕ(x_{k+1}) kullanılır. Tahminin kendisinin hedefte kullanılması önyükleme (bootstrapping) olarak adlandırılır. Bu yöntem daha düşük varyansa sahip olabilir ancak önyargılıdır. Bir tahmin edicinin önyargısı, beklenen değerinin gerçek değerden ne kadar farklı olduğudur.

Ortalama kare hatası (MSE), bir tahmin edicinin tutarlılığını değerlendirmek için kullanılır. MSE, varyans ve önyargının karesinin toplamına eşittir. Bu nedenle, en iyi tahmin edici, en küçük varyansa veya en küçük önyargıya sahip olan değil, bu ikisi arasındaki en iyi dengeyi sağlayan tahmin edicidir.

TD(λ) Yöntemi: Zaman farkı (TD) öğrenmesi, pekiştirmeli öğrenmede önemli bir politika değerlendirme yöntemidir. TD(λ) yönteminde, λ parametresi gelecekteki maliyetlerin güncellemeleri ne kadar etkileyeceğini belirler. TD(0) yöntemi, bootstrapping yöntemine karşılık gelirken, TD(1) yöntemi Monte Carlo yöntemine karşılık gelir. λ’nın 0 ile 1 arasındaki değerleri ise hibrit bir yöntem tanımlar.

Deneyim Tekrarı ve Seyrek Ödüller: Deneyim tekrarı, daha önce elde edilen verilerin yeniden kullanılmasıdır. Bu yöntem, özellikle seyrek ödüller (bir bölümde nadiren alınan ödüller) durumunda öğrenmeyi iyileştirmek için kullanılır. Öncelikli deneyim tekrarı, pozitif ödüllere sahip dizilerin daha sık kullanılmasını sağlayarak öğrenmeyi hızlandırır. Geriye dönük deneyim tekrarı, başarısız bölümleri hedefe değiştirerek değerli öğrenme verilerine dönüştürür. İçsel ödüller de seyrek ödül sorununa bir çözüm olarak kullanılabilir.

Politika İyileştirme: Politika iyileştirme, toplam maliyeti en aza indirecek veya toplam ödülü en üst düzeye çıkaracak en iyi politikayı belirlemeyi amaçlar. Aktör-Eleştirmen yöntemi, politika değerlendirmesi yapan bir “Eleştirmen” ve politika iyileştirmesi yapan bir “Aktör”den oluşur.

Q Faktörleri ve Kontrol Problemi: Q-öğrenimi, hedefi Q-faktörü olan bir TD(0) algoritmasıdır. Q-faktörü Q(x, a), bir durum-eylem çifti için beklenen toplam ödülü temsil eder. Q-öğrenimi, politika bağımsız bir algoritmadır ve optimal kontrolü gözlemlemeden Q-faktörlerini tahmin eder. SARSA (State-Action-Reward-State-Action), Q-faktörlerini tahmin etmek için kullanılan politika bağımlı bir algoritmadır.

Keşif ve Sömürü Dengesi: Pekiştirmeli öğrenmede, keşif ve sömürü arasında bir denge kurmak önemlidir. Keşif, tüm durum-eylem uzayını ziyaret ederek optimal politikayı öğrenmeyi hedeflerken, sömürü ödülleri en üst düzeye çıkarmak için bilinen en iyi eylemleri kullanmayı amaçlar. ϵ-açgözlü algoritma, açgözlü politikayı (sömürü) 1-ϵ olasılıkla, keşif politikasını ise ϵ olasılıkla seçen bir yaklaşımdır.

Yapay Sinir Ağları ve Pekiştirmeli Öğrenme: Yapay sinir ağları (YSA), özellikle büyük durum uzaylarına sahip pekiştirmeli öğrenme problemlerinde kullanılır. YSA’lar, değer fonksiyonları ve Q-faktörleri gibi karmaşık yapıları yaklaşık olarak temsil etmek için kullanılabilir. Derin sinir ağları (DNN), özellik seçimi işlevini otomatikleştirerek, daha verimli öğrenmeyi sağlarlar.

Özetimiz bitti, yazı başlıyor…

Giriş: Pekiştirmeli Öğrenmeyi Anlamak

“Öğrenme” terimi, algoritmanın açıkça programlanmadığını, ancak verilerden ilgili ilişkilerin kendi kendine öğrendiğini ifade eder.

Bilgisayarlar genellikle karar alma, tahmin, sınıflandırma veya desen tanıma görevlerini otomatikleştirmek için kullanılır. Makine öğrenmesi, bir bilgisayarın bu görevleri, genellikle gerçek veya simüle edilmiş verilerden edinilen deneyimlerden öğrenmesini sağlayan algoritmaların geliştirilmesini içerir. Öğrenme, temel algoritmaların verilere veya bu görevlerin performansını optimize etmek için matematiksel modeller veya eniyilik (optimality) ilkeleri yerine verileri (veya önceki deneyimleri) kullanma becerisine dayanmasını ifade eder. Makine öğrenmesi birkaç dala ayrılabilir. Gözetimli öğrenme, belirli bir nicelik için bir regresyon modeli ve sınıflandırma yapmak gibi öncelikli olarak tahminlemeyle ilgilenir.

Gözetimli Öğrenme

Gözetimli öğrenmede, algoritmalar gerçek değerlerin bilindiği etiketli verilerden öğrenir. Gözetimli öğrenmenin amacı sınıflandırıcılar ve nicel öngörücüler geliştirmektir. Bunun temel bir örneği, el yazısı karakterlerin resimlerden sınıflandırılmasıdır. Amaç, f :X → Y eşlemesini oluşturmaktır; Burada X, el yazısı karakterlerin tüm makine tarafından okunabilen resimlerinin evrenidir (girdi), Y = {a, b, …} ise tanınacak tüm karakterlerin kümesidir (çıktı). Eğer x ∈ X, gerçekte, el yazısıyla yazılmış bir e harfinin resmiyse, olasılığının bire yaklaştığını f(x) = e ∈ Y görmeyi bekleriz.

Sınıflandırıcı f(x)’in, muhtemelen Y’deki karakterlerin bilinen geometrik özelliklerine dayanan programlanmış talimatlardan oluşması düşünülebilir. Örneğin, bilgisayarın bir daire ile bir doğru parçası arasında ayrım yapmasını sağlayacak talimatlar tasarlamak mümkün olmalıdır. Ancak, gözetimli öğrenme yaklaşımı oldukça farklıdır. Talimatları formüle etme girişimi yapılmaz. Bunun yerine, girdi-çıktı çiftlerinden oluşan (x1, y1), (x2, y2),…, (xn, yn) eğitim verileri kullanılır.

Eğitim verileri eğitim sürecinde kullanılırken, test verileri doğrulama amacıyla kullanılır.

Burada xi, sınıflandırıcının uygulanacağı X evreninden alınan bir örnektir ve onun çifti olan yi ise etiket veya gerçek sınıftır (bu insan yargısıyla elde edilebilir).

Gözetimli öğrenme yöntemi, eğitim verilerini kullanarak f(x) olarak adlandırılan bir sınıflandırıcı oluşturacaktır; bu sınıflandırıcı için f(xi)=y yüksek olasılıkla sağlanır. Tabii ki, genel yaklaşım, f(x) sınıflandırıcısının doğruluk oranını, eğitim verileriyle aynı yapıya sahip ancak f(x) tahmincisini eğitmek için kullanılmamış test verileri (x1′,y1′),(x2′,y2′),…,(xm′,ym′) ile değerlendirmeyi içerir.

Gözetimli öğrenmede potansiyel olarak kritik bir adım, en önemli değişkenleri tanımlayıp, problemle ilgili olmayanları eleyen özellik seçimi adımıdır. Özellikle, gözetimli öğrenme uygulamaları için girdi verileri yüksek boyutlu olduğunda, bilgilendirici olmayan ya da başka bir değişkende yer alan bilgiyi sadece tekrarlayan değişkenleri belirlemek ve elemek önemlidir. Çok boyutlu bir girdinin x=(x1,…,xp)∈X formunda olduğunu varsayalım; burada her bir bileşen xj,j=1,…,p ayrı bir bilgi parçası olarak yorumlanabilir.

Her bir bileşenin, yanıt değişkeni y ile ilişkili olması gerekmeyebilir. Örneğin, bir müşterinin kredi riskini, x1,…,xp​ gibi bir dizi mevcut değişkene dayalı olarak tahmin eden bir uygulama geliştirmek istediğimizi varsayalım. Bu durumda, örneğin, şunu bekleyebiliriz: x1 = mevcut kredi kartı bakiyesi olsun, bu uygulama için yararlı olur, ancak x2 = doğum_şehri durumunda özellik seçimi bu tür yargıları nicel bir temelde yapar.

Özellik çıkarımı, çok değişkenli girdi verilerinden x = (x1 , …, xp) ∈ X türetilmiş değerler oluşturur. Karakter tanıma veya diğer görüntü işleme uygulamalarında, türetilmiş değerler parlaklık ölçüleri, çarpıklık ölçüleri veya köşeler, düz çizgiler veya daireler gibi temel geometrik özelliklerin özetleri olabilir. Türetilmiş değerler daha sonra ham veri x yerine f’ye girdi olarak kullanılır.

Gözetimli öğrenme uygulamalarının verimliliği, girdilerin önce çeşitli özellik seçimi yöntemleri kullanılarak işlenmesiyle genellikle artar.

Gözetimsiz Öğrenme

Gözetimsiz öğrenme, verilerdeki ilişkileri bulmak için etiketlenmemiş verileri kullanır.

Makine öğrenmesinin ikinci bir dalı olan gözetimsiz öğrenme, genellikle desen tanıma ile ilgilidir. Eğer elimizde etiketler yi∈Y olmaksızın x1,…,xn∈X şeklindeyse, muhtemelen gözetimsiz öğrenme ile ilgili bir problemle karşı karşıyayızdır. Genellikle xi çok boyutludur ve daha önce bilinmeyen desenleri arıyoruzdur. Ancak, girdileri Y içinde bir çıktıya eşleyen bir sınıflandırıcı inşa etmeye çalışmıyoruz. Bu nedenle, gözetimsiz öğrenme genellikle keşif analizine yönelik olur ve gelecekteki makine öğrenmesi algoritmalarını bilgilendirmek için kullanılabilir. Önemli bir uygulama, verileri nispeten az sayıda gruba ayırmaya çalışan ve her bir grup içindeki gözlemlerin homojen, yani grup içindekilerin birbirine benzer, diğer gruplardakilerden ise farklı olduğu kümeleme (clustering) işlemidir.

Yukarıda bahsedilen karakter sınıflandırıcı f’yi düşünün; bunun girdi verisi, tek bir el yazısı karakterin makine tarafından okunabilir bir görüntüsüdür. Tabii ki, el yazısı karakterler bir zarf üzerindeki adres gibi bir grup içinde yer alır. Bu durumda, sınıflandırıcı, el yazısı bir dokümandan tekil karakterleri izole eden ve çıkaran ayrı bir gözetimsiz öğrenme algoritmasına bağlı olur. Genel olarak, gözetimsiz öğrenme algoritmaları özellik seçimi (feature selection) için faydalıdır. (James, Witten, Hastie & Tibshirani, 2013) gözetimli ve gözetimsiz öğrenme için mükemmel bir referanstır.

Pekiştirmeli Öğrenme

Ardışık karar verme süreci (SDP: Sequential Decision Process), zamana göre sıralanmış bir dizi kararın, zaman içinde biriken bir maliyeti veya ödülü etkilediği herhangi bir dinamik süreçtir. Amaç, tanımlanmış maliyeti veya ödülü optimize eden karar dizisini belirlemektir. Makine öğreniminin üçüncü bir dalı olan pekiştirmeli öğrenme (reinforcement learning), denetimli ve denetimsiz öğrenmenin bazı temel özelliklerini paylaşır, ancak özellikle ardışık karar verme problemine uygulanır ve bu nedenle denetimli veya denetimsiz öğrenmenin kullandığı verilerden farklı bir veri biçimine dayanır. Pekiştirmeli öğrenme teorisinin büyük bir kısmı, Richard Bellman tarafından 1957'de formüle edilen dinamik programlamaya dayanır. Bu pekiştirmeli öğrenmenin matematiksel temelinin büyük bir kısmını sağlasa da, dinamik programlamanın sınırlı bir hesaplama kapasitesi vardır. Pratikte bu, en azından tam formuyla, dinamik programlamanın, bugün sıklıkla mevcut olan yüksek verimli verilerden yararlanmak için yapılan uygulamalar için uygulanabilir bir çözüm olmadığı anlamına gelir.

Dinamik programlama, bir SDP için matematiksel bir modelin analizi temelinde optimal kararlar türetir. Pekiştirmeli öğrenmenin özellikle dikkat çekici erken bir uygulaması, TD-Gammon adı verilen bir SDP’nin geliştirilmesidir; bu program tavla oyununu rekabetçi bir düzeyde oynayabilmektedir (Tesauro, 1994). Daha yakın zamanda, pekiştirmeli öğrenme, DeepMind tarafından AlphaZero adlı bir satranç oynama programını oluşturmak için kullanılmıştır (The Telegraph, (6 Aralık 2017), “Tüm insan satranç bilgisi DeepMind’in AlphaZero’su tarafından dört saatte öğrenildi ve aşıldı”). Pekiştirmeli öğrenme, özellikle derin sinir ağı modelleriyle birleştirildiğinde (derin pekiştirmeli öğrenme), oyun oynama uygulamalarını geliştirmek için oldukça uygun hale gelir. Örneğin, oldukça etkili video oyunu oynama uygulamaları oluşturmak için kullanılmaktadır (Mnih, 2015a).

Daha genel olarak, dinamik programlama ve pekiştirmeli öğrenme, ardışık karar verme içeren yapay zeka uygulamaları için kullanılabilir. Bu, onları özellikle otonom araçların navigasyon kontrolü için uygun hale getirir. Otomobiller, dronlar, helikopterler ve diğer insansız hava araçları (UAV: Unmanned Aerial Vehicles) için bu tür uygulamaların geliştirilmesi, şu anda hızla büyüyen bir araştırma alanıdır. Pekiştirmeli öğrenme, robotikte yaygın olarak kullanılmakta ve sağlık hizmetlerine kadar genişlemektedir (bu da birçok yeni problemi beraberinde getirmiştir); bilgisayar destekli tanı, özellikle dikkat çekici bir uygulama haline gelmiştir. Bir SDP sürekli zamanda tanımlanabilse de, pekiştirmeli öğrenme, ayrık zamanlı süreçlerle ilgilenir. Zaman, k=1,2,… aşamalarına bölünür. Bir envanter kontrol modeli için bir aşama, bir gün veya bir hafta gibi sabit bir zaman aralığını temsil edebilir. Seçim, envanter kararlarının (stok yenileme veya fiyat düşürme) ne sıklıkla yapılacağına bağlı olacaktır. Benzer şekilde, bir otonom sürüş uygulaması sürekli zamanda çalışsa da, karar kurallarının uygulanması, iyi tanımlanmış karar anlarında (navigasyon kararları, fren uygulaması, rota düzeltmeleri, hız değişimi) gerçekleşir. Bir SDP, aynı zamanda satranç oyunu gibi bir oyun da olabilir; bu durumda aşama, tek bir hamleyi temsil eder. Ayrık zamanlı bir SDP, aşamaların bitiş noktalarını karar anları (kararların alınabileceği zaman noktaları) kullanarak tanımlayarak sürekli zamanlı bir süreci kontrol edebilir.

Örnek: Bir Alet Kabini SDP

Bir SDP örneği olarak, bir otoyoldaki geçiş ücreti sistemini düşünün. Maksimum on gişe kapasitesi olabilir, ancak tüm gişeler herhangi bir anda çalışmıyor olabilir. Mevcut veya tahmin edilen trafik seviyelerine göre gişeleri açmaya veya kapatmaya karar veren bir kontrol sistemi oluşturmak için pekiştirmeli öğrenmeyi kullanabiliriz. Bir araba sisteme girdiğinde veya çıktığında yeni bir aşama başlayabilir ve bu da yeni bir karar dönemi oluşturabilir. Bu şekilde, SDP resmi olarak ayrık zamanlı bir süreç olmasına rağmen kontrol esasen gerçek zamanlı olarak uygulanabilir.

Klasik Kontrol Teorisi

SDP’lerin optimum kontrolünü çıkarmak için zengin bir matematiksel teori vardır. Bunların çoğu, Richard Bellman tarafından 1957'lerde formüle edilen dinamik programlamaya dayanmaktadır. Öyle ki, nispeten basit bir fikir bu alana dikkate değer bir birlik derecesi sağlar ve operasyon araştırması, ekonomi, kontrol teorisi ve yapay zekadaki oldukça geniş bir uygulama yelpazesi esasen aynı yapıyı paylaşır. Örneğin, aşağıdaki kontrol problemini ele alalım.

Örnek: Envanter Modeli

Her iş haftasının (k = 1, 2, … endeksiyle etiketlediğimiz) başlangıcına hazırlık olarak, bir perakendeci bir ürünün mevcut stok yk’sini not eder, ardından kısa bir süre sonra gelen yeni stok wk’sini sipariş eder. Ürün için bir talep dk’si vardır, bu nedenle perakendeci şunları satar:

Bu nedenle bir karar sürecimiz bulunmaktadır. Karar, sipariş miktarı wk’dir. Wk’yi seçerken, aşağıdaki maliyetler ve ödüller dikkate alınmalıdır:

1. pssk geliri hesaplanır, burada ps birim fiyattır. Bu, sipariş kararlarından önce bilinmeyen talep dk’sına bağlıdır. Ancak, dk’yı karşılayacak yeterli stok sipariş etmemek gelir kaybına neden olur. Ayrıca, talebi düzenli olarak karşılayamamak, güvenilir bir tedarik tercih eden müşterilere gelecekteki satışlara da mal olabilir.
2. Sipariş miktarı haftalık olarak talebi önemli ölçüde aştığında önemli hale gelebilecek bir envanter depolama maliyeti vardır.
3. Her yeni sipariş için sabit bir nakliye maliyeti B vardır. Bu maliyet, sipariş verilmezse varsayılmaz (yani, wk = 0). Bu nedenle, karar verici, örneğin, iki haftada bir verilen siparişlerin haftalık siparişlere tercih edilebilir olma olasılığını öngörmeyi seçebilir.

Muhtemelen sipariş kararlarının perakendeci maliyetlerini ve ödüllerini etkilemesinin daha fazla yolu bulunmaktadır.

Envanter problemi, operasyon araştırmasının yönetim bilimine uygulanmasına klasik bir örnektir. İlkeler doğrultusunda, modeli matematiksel olarak tanımlayabiliriz. Parametreler arasında depolama maliyeti, nakliye maliyeti, perakende fiyatı gibi unsurlar yer alır. Ayrıca bir model ortamını, yani doğrudan kontrol edilemeyen, ancak modelin dinamik davranışını ve maliyetlerini etkileyen dışsal faktörleri de tanımlamamız gerekir. Talep dk​, bu tür bir faktöre örnek olarak gösterilebilir. Fiyat, kısa vadeli dalgalanmalara maruz kalan dışsal bir faktörse, onu da çevrenin bir parçası olarak görebiliriz. Model, net getiriyi de kesin bir şekilde tanımlamalıdır; bu, gelir ile maliyet arasındaki fark olarak ifade edilir. Bazı bileşenler muhtemelen tanımlaması kolay olacaktır; örneğin, satış geliri, depolama gideri veya nakliye gideri gibi. Ancak diğer maliyetleri nicel olarak belirlemek daha zor olabilir. Talebin sürekli karşılanamaması durumunun (ki bu, dk>yk+wk​ olduğunda meydana gelir) gelecekteki satışları azaltabileceği olasılığını değerlendirdik. Bunun nicel olarak tahmin edilmesi zor olabilir, ancak çok gerçek bir etkisi, gelecekte talep dk​’yi azaltmak olacaktır.

Uyarlanabilir Kontrol Sistemleri

Böyle uygulamalarda, model tanımlaması genellikle gereklidir. En basit stok kontrol modelinde bile talep miktarının tahmin edilmesi gerekir. Bu, neredeyse kesinlikle bir stokastik talep modeli içerecektir (çünkü talepler doğası gereği rastgelelik içerirler). Model tanımlaması, bu durumda talep dağılımı parametrelerinin tahmin edilmesini içerebilir.

Tabii ki, parametre tahmini matematiksel modelciler için genellikle rutin bir görevdir. Ancak, kontrol teorisinin doğası ilginç bir yeni sorunu ortaya çıkarır. Gerçek optimal kontrolün elde edilmesi genellikle tam model tanımlamasına bağlıdır. Model tam değilse, kontrol suboptimal olacak ve tahmin hatasına doğrudan atfedilebilecek bir maliyet oluşacaktır.

Bu nedenle, bir kontrol sisteminin, operasyon sırasında gözlemlenen verilerden yararlanması için güçlü bir teşvik vardır. Örneğin, stok kontrol modelimiz için bir talep modeli tahmin edebildiğimizi varsayalım. Tahmin edilen talep modelimiz tamamen doğru olsaydı optimal olacak karar kurallarını hesaplarız. Buna kesinlik-denklik modeli (certainty-equivalence model) denir. Daha sonra bu karar kuralını canlı operasyonlarımızda uygularız. Ancak, talep modelimizin tahminini geliştirmek için kullanılabilecek verileri biriktirmeye devam ettiğimiz için, giderek daha doğru hale gelen talep tahminlerimize dayanarak karar kurallarımızı sürekli olarak yeniden hesaplarız. İdeal olarak, böyle bir uyarlamalı kontrol sistemi optimal maliyetlere yaklaşır.

Buna ek olarak, çevre de değişebilir. Örneğin, bir reklam kampanyası talebi arttırabilir ve bu durumda statik bir kontrol sistemi artık optimal olmayacaktır. Uyarlamalı bir kontrol sistemi, bu tür değişikliklere yanıt olarak kontrol parametrelerinin tahminlerini de değiştirebilir.

Dinamik Programlamanın Temelleri

Bir SDP’yi (Stokastik Dinamik Programlama) zaman indeksli aşamalardan oluşan sıralı bir dizi olarak düşünebiliriz. Her aşama içinde, karar verici bir karar alır veya bir eylemde bulunur ve her aşama bir maliyet veya ödülle ilişkilendirilir. Sürecin kendisi, bir durum uzayına ait tekil durumlar arasındaki geçişlerden oluşur. Durum uzayı X, tüm olası durumların kümesidir.

SDP, yeni bir duruma geçtiğinde, eylem uzayı A’dan seçilen bir eylem şeklinde bir karar alınır. SDP, ayrık zaman noktaları veya epok’lar (epoch) j = 1, 2, … üzerinde tanımlanan dinamik bir süreçtir. Her epok j bir aşama ile ilişkilendirilir. Her bir aşama j, bir durum xj ve bir eylem aj içerir. Bu nedenle, bir durum-eylem çifti (xj, aj) olarak bahsederiz.

Kavramsal olarak, bir aşama içinde durum xj önce gözlemlenir. Daha sonra, durum bilgisiyle, iyi tanımlanmış bir olasılıklar kümesinden seçilen bir eylem aj şeklinde bir karar alınır. Ancak, bu tanımı detaylandırmak yaygın bir uygulamadır; çünkü herhangi bir durum x’den her eylem a ∈ A’nın mümkün olmayabileceği belirtilmelidir. Bu durumda, Ax, durum x’den yapılabilen tüm eylemleri temsil eder. Böylece, x, a çifti, eylem a’nın durum x’den izin verilen bir eylem olması durumunda geçerli bir durum-eylem çifti olur. Tüm geçerli durum-eylem çiftlerinin kümesi, durum-eylem uzayıdır.

Eylem aj, durum xj’den seçildiğinde, bir maliyet (veya ödül) R(xj, aj) hesaplanır; burada R(x, a), her kabul edilebilir durum-eylem çifti (x, a)’ya bir maliyet veya ödül atayan ve her kabul edilebilir durum-eylem çifti (x, a) ∈ K için tanımlanan maliyet (ödül) fonksiyonudur.

Durumlar arasındaki geçiş, SDP’nin xj durumundan x_{j + 1} durumuna nasıl hareket ettiğini belirleyen bir geçiş kuralı tarafından yönetilir. Bu kural, geçerli durum-eylem çiftine (xj, aj) bağlıdır. Rastgele durum işlemlerine stokastik geçişler denir. Bu durumlarda, sonraki bir durum xk + 1, geçerli durum-eylem çiftine (xk, ak) bağlı olan bir olasılık dağılımının sonucu olarak belirlenir. Daha kesin olarak, stokastik geçişler, her olası durum-eylem çifti x, a için tanımlanan bir olasılık çekirdeği P(y ∣ x, a )tarafından yönetilir. Geçerli durum-eylem çifti (xj , aj) verildiğinde, sonraki durum xj + 1'in y’ye eşit olma olasılığı P (y ∣ xj , aj)’dir. Muhtemelen, geçerli durum-eylem çifti (xk , ak) bilindiğinde sonraki bir durum xk + 1 benzersiz bir şekilde belirlenirse geçişler deterministiktir. Bu, (xj, aj) bilindiğinde, sonraki xj + 1 durumu için yalnızca bir olası değer olduğu anlamına gelir. Bu durumda, olasılık çekirdeği P (y ∣ xj, aj ) bir geçiş fonksiyonu q(x, a) ile değiştirilebilir ve bu da xj + 1 = q (xj, aj) geçiş kuralını verir.

Deterministik bir geçiş kuralı, her kabul edilebilir x, a ∈ K için bir q(x, a) ∈ X eşlemesiyle temsil edilebilir. Elbette, bu, olasılık çekirdeğini ayarlayarak da modellenebilir:

Bu, P{x_{j + 1} = q(xj , aj)} = 1 anlamına gelir ve bu da deterministik bir geçiş kuralını tanımlar.

“Model” terimi, bir SDP’nin bileşenlerine toplu olarak atıfta bulunmak için kullanılır.

Özellikle, bu, deterministik geçişler için durum uzayı X, eylem uzayı A, durum-eylem uzayı K, maliyet fonksiyonu R(x, a) ve geçiş fonksiyonu q(x, a) veya stokastik geçişler için olasılık çekirdeği P(y ∣ x, a) içerir.

Dinamik Programlama Modeli Tarafından Biriktirilen Maliyet

Şimdi sıralı karar problemlerinde sıklıkla kullanılan bazı terminolojileri tanımlayacağız. Yaşam süresi açısından, SDP’nin üç biçimi vardır.

Sonlu ufuklu bir SDP (Stochastic Dynamic Programming), sabit ve sonlu bir aşama sayısı K’ye sahiptir. Sonsuz ufuklu bir SDP ise süresiz olarak devam eder. En kısa yol SDP’sinde ise aşama sayısı sonludur ancak değişkendir. Bu tür SDP’lerde xΔ∈X olarak adlandırılan bir terminal durum bulunur. SDP bu duruma girdiğinde, burada süresiz olarak kalır ve artık hiçbir maliyet ya da ödül kazanmaz. Esasen süreç xΔ∈X durumuna ulaşıldığında sona erer.

Bir SDP, toplam birikmiş maliyetin/ödülün, aşama maliyetlerinin/ödüllerinin bir indirim faktörü (β∈[0,1]) ile iskonto edilmiş toplamı olması durumunda, iskonto edilmiş maliyet/ödül problemi olarak adlandırılır. İndirim faktörü, gelecekteki maliyetlerin/ödüllerin ne kadar iskontolandığını belirler.

Bu durumda toplam maliyet ya da ödül sonlu ufuklu bir problem için şu şekilde ifade edilir:

Sonsuz ufuklu en kısa yol problemi için şu şekilde ifade edilir:

Sonlu ufuk ve en kısa yol SDP’leri için genellikle β = 1 koyduğumuzu ve bu nedenle ifadeye dahil edilmesi gerekmediğini unutmayın. Bu durumda, toplam veya indirim yapılmamış maliyete atıfta bulunuruz. Bunun aksine, sonsuz ufuk SDP için genellikle β < 1'e sahibiz, böylece yukarıdaki denklemdeki R sonlu olacaktır.

İndirimin nasıl çalıştığını görmek için, tüm aşama maliyetlerinin negatif olmadığını ve üstten sonlu bir sabit M ≥ R(x, a) ≥ 0 ile sınırlandırıldığını varsayalım. β < 1 olduğunu varsayalım.

Daha sonra, herhangi bir eylem dizisi a1 , a2 , … için, şuna sahip olacağız:

Burada geometrik dizilerden yararlanıyoruz.

geometrik diziler

Bu nedenle, β < 1 olduğu sürece, toplam indirim yapılmış maliyet sonlu olacaktır. Bazen, hem indirim yapılmış hem de yapılmamış maliyetlerin tek bir modelle temsil edilebilmesi için β’yi ifadeye dahil etmenin uygun olacağını unutmayın.

Bir SDP’nin Kontrolü

Amaç, yukarıdaki denklemlerdeki R’yi maliyet olarak en aza indirmek veya ödül olarak en üst düzeye çıkarmaktır. Kural tutarlı bir şekilde uygulandığı sürece, dinamik programlamanın teorisinde ve metodolojisinde bu ayrım önemli değildir. Her iki durumda da genellikle R(x, a)’ya bir maliyet fonksiyonu olarak atıfta bulunacağız. Maksimum ödül problemi, maliyet fonksiyonu R (x, a)’yı −R(x, a) şeklinde -1 ile çarparak basitçe minimum maliyet problemine dönüştürülebilir. Kural olarak, bir optimizasyon problemi minimum maliyet veya maksimum ödül problemine atıfta bulunabilir.

SDP Politikası

Bir SDP (Stochastic Decision Process), her aşamada eylemleri seçmek için bir yöntem olan bir politika tarafından kontrol edilir. Toplam maliyetin veya ödülün optimize edilmesi, uygun politikanın seçilmesiyle ilgilidir.

Yaygın bir politika biçimi, her durum x∈X’i uygun bir eylem Ax​’e eşleyen bir politika fonksiyonundan yararlanır. Bir SDP, politika fonksiyonu ϕ(x) tarafından kontrol edildiğinde, her durum-eylem çifti (xj,aj)=(xj,ϕ(xj)) olur.

Bu tür bir politika, her aşamada aynı karar kuralını uygulayan herhangi bir politika olan durağan bir politikanın örneğidir. Optimum bir politika, ϕ∗ ile gösterdiğimiz politika fonksiyonu, başlangıç durumu x=x1​ için ya da ideal olarak tüm başlangıç durumları için, R’nin beklenen değerini optimize eder.

Dinamik programlama teorisinin büyük bir kısmının, bir SDP’nin belleksiz olduğu varsayımına dayandığını not ederiz, yani tüm sonraki davranışlar ve maliyetler yalnızca mevcut durum-eylem çiftine bağlıdır. Bu varsayım şu durumlarda sağlanır:

1. Durum xj​’den x_{j+1}​’e geçiş kuralı yalnızca mevcut aşama verilerine (xj, aj) bağlıdır.

2. Süreç tarafından xj​ durumundan itibaren biriken toplam kalan maliyet yalnızca mevcut aşama verilerine (xj, aj​) bağlıdır.

Kontrollü bir SDP’nin belleksiz kalması için politika da belleksiz olmalıdır. Bir politika fonksiyonu ϕ(x) ile tanımlanan durağan bir politika belleksiz olacaktır. Şunu belirtmek önemlidir ki, eğer SDP modeli belleksizse, o zaman optimum politika da durağan olacaktır. Bu, yalnızca j aşamasında bir durum x′ ’den bir eylem a’ ’nın optimum olduğu durumlarda, SDP x′ aşamasına geri döndüğünde gelecekte de a′ ’nin optimum eylem olmasını bekleyebileceğimiz anlamına gelir.

Markov Karar Süreçleri (MDP: Markov Decision Processes)

Özellikle önemli bir SDP türü, durum-eylem uzayı K, maliyet fonksiyonu R(x,a) ve olasılık çekirdeği P(y∣x,a) ile sonsuz ufuklu bir SDP olan Markov karar süreci (MDP)dir. İndirim faktörü β ile indirimli maliyet/ödül birikim yöntemini kullanır. Bu nedenle, bileşenler listesi (K, R, P, β) ile tanımlanabilir. Bu, basitçe, indirimli maliyet veya ödül ve stokastik geçişler kullanan bir sonsuz ufuklu dinamik programlama modelidir.

Yapısı gereği, bir MDP, hafızasız bir SDP’dir ve “Markoviyen” terimi genellikle hafızasız özelliği belirtmek için kullanılır. Eğer model bileşenleri (K, R, P) tanımlanabiliyorsa, optimal karar kuralını belirlemek için hiçbir veri veya simülasyon gerekmez. Ancak, bu ideal durum genellikle pratik değildir. Pekiştirmeli öğrenmenin matematiksel teorisinin büyük bir kısmının MDP gibi modellere dayandığını göreceğiz. Bununla birlikte, pekiştirmeli öğrenmenin bu modellerin uygulanmasındaki birçok pratik engelin üstesinden gelebileceği de doğrudur.

Politika Değerlendirmesi

Dinamik programlama teorisi büyük ölçüde optimal politikaların türetilmesiyle ilgilidir. Dinamik programlamayla ilişkili yöntem SDP’nin basit bir yinelemeli formülasyonuna dayanır. Durağan politika ϕ ve dinamik programlama modeli (K, R, P) verildiğini varsayalım.

Diğer tüm modeller özel durumlar olarak yorumlanabileceğinden, modelin stokastik ve indirim uygulanmış olduğunu varsayacağız.

Politika değeri fonksiyonu Vϕ(x), x ∈ X olacak ve başlangıç ​​durumu x1 = x olduğunda beklenen toplam maliyeti verecektir. Vϕ(x)’i ilk aşamayı ayrı ayrı ele alarak parçalayabiliriz. İlk olarak, argümanımız tüm durumlar için aynı olduğundan, SDP’nin ömrünü belirtmediğimizi unutmayın. Sonra, ilk aşamadan R’ye katkı R(x1, ϕ(x1)) olacaktır. İşlem daha sonra P(y ∣ x1, ϕ(x1)) dağılımına göre x2 = y durumuna geçer. Sonra, x2 koşuluyla, R’ye kalan beklenen katkı βVϕ(x2) olacaktır. Başlangıç ​​durumu x1 = x koşulunu sağlamak daha uygun olacaktır, böylece:

Vϕ(x) değer fonksiyonunun Vϕ(x) = R(x, ϕ(x)) + β∑(y) Vϕ(y)P(y ∣ x, ϕ(x)) ∈ X denklemini sağlaması gerektiği sonucuna varıyoruz. Ayrıca, başka hiçbir fonksiyonun bu denklemi sağlamadığını biliyorsak, Vϕ(x) tek çözümünü bularak belirlenebilir (eğer çözüm tek olmasaydı, bulduğumuz herhangi bir çözümün ilgilendiğimiz çözüm olup olmadığını bilemezdik). Şimdilik, fonksiyonel analizdeki önemli bir sonuç olan Banach Sabit Nokta Teoremi’nin dinamik programlama problemlerinin genel olarak sağladığı varsayımlar altında tek bir çözüme sahip olduğunu garanti ettiğini belirtmekle yetiniyoruz.

Belirli bir politikanın toplam ödülünü veya maliyetini belirleme sorununa politika değerlendirmesi denir. Sabit politika ϕ’ye sahip dinamik programlama modeli için bu, politika değer fonksiyonu Vϕ(x)’i değerlendirmeye eşdeğerdir. Sabit politika ϕ’ye sahip dinamik programlama modeli için bu, Vϕ(x)’i değerlendirmeye indirgenir.

Bir operatör bir fonksiyonu başka bir fonksiyona eşler.

Bu denklemin nasıl çözüleceğini açıklamak için bir operatör kavramını tanıtmamız gerekir. V’nin durum uzayı X üzerinde tanımlanmış uygun bir fonksiyon kümesi olduğunu varsayalım. V üzerindeki bir operatör daha sonra V′ ∈ V fonksiyonunu değiştirerek başka bir V′′ = TV′ ∈ V fonksiyonu üretir. Değerlendirme yöntemini kullanarak Tϕ olarak adlandırdığımız böyle bir operatörü inşa edebiliriz. Özellikle, V′ ∈ V ile başlayarak, V′′ = TV′ her x ∈ X için şu denklem kullanılarak değerlendirilir:

Bu, çok yararlı bir yeniden formülasyona izin verir:

Vϕ(x)= T^ϕV^ϕ(x).

Bu nedenle sorunu sabit nokta denkleminin sabit noktasını belirleme sorunu olarak görebiliriz. Sabit nokta denklemi, V = TV (burada V bir fonksiyondur) veya x = f(x) (burada x bir gerçek sayıdır) biçimindeki herhangi bir denklemdir.

Sabit nokta denkleminin herhangi bir çözümü V* sabit nokta V* = TV*’dir.

Bu nedenle önceki denklemi V = T^ϕV olarak yazabiliriz

Bazı V ∈ V için. Sabit nokta denkleminin çözümü o zaman politika operatörünün sabit noktasıdır ve politika değer fonksiyonu V^ϕ olarak adlandırılır. Daha önce, genel koşullar altında, denklemin çözümünün (aynı zamanda operatör T^ϕ’nin sabit noktası olan) var olduğunu ve benzersiz olduğunu savunduk. Bu sabit nokta politika değer fonksiyonu V^ϕ ‘dir.

Bu formülasyonun önemli bir avantajı, genel koşullar altında, sabit noktaların, xn + 1 = f xn sabit nokta yinelemelerini kullanarak x1, x2, … dizisini hesaplayan sabit nokta yineleme yöntemi kullanılarak değerlendirilebilmesidir. x1'in başlangıç ​​değeri belirtilmelidir. Eğer f, x* = f x* sabit noktasına sahipse, o zaman, iyi bilinen koşullar altında, sabit nokta yinelemelerinin dizisi x*’e yakınsar.

Fikir operatörlere kadar uzanır. Operatör T sabit nokta V * = TV*’ye sahipse, iyi bilinen koşullar altında, sabit nokta V_n+1 = TV n’yi yineler ve uygun bir başlangıç ​​fonksiyonu V1 verildiğinde V*’ye yakınsar. Bu, Banach Sabit Nokta Teoreminin bir başka sonucudur. Basitçe ifade etmek gerekirse, bize bir operatör T verildiğini ve sabit nokta yinelemelerini V_n+1 = TV_n, n ≥ 1 olarak değerlendirdiğimizi varsayalım, uygun bir başlangıç ​​fonksiyonu V1 verildiğinde. Dizi tek bir fonksiyon V *’ye yakınsarsa, bu sabit nokta V * = T V * olacaktır.

Politika İyileştirme

Diyelim ki bize bir politika ve politika değer fonksiyonu ϕ, Vϕ verildi. ϕ’yi iyileştirmenin basit bir yolu ne olabilir? İhtiyacımız olan ilk şey ϕ’yi değiştirmenin basit bir yoludur. Diyelim ki xk durumundan ak = ϕ(xk) eylemini seçmek yerine herhangi bir başka ak = a′ eylemini seçeriz. Daha sonra P(y ∣ xk, a′) dağılımına göre xk + 1 durumuna geçeriz ve aşama maliyeti R(xk, a′) biriktiririz. Daha sonra xk + 1 durumundan SDP’nin geri kalanı için ϕ’yi kullanmaya devam ederiz.

Bu yeni politikanın toplam maliyetini hesaplamak kolaydır:

Bu, pekiştirmeli öğrenmede Q faktörü (politika ϕ için) olarak bilinir ve herhangi bir durum-eylem çifti (x, a) ∈ K için tanımlanabilir:

Q-faktörlerine sahip olduğumuzda, politikayı geliştirebiliriz. x’i düzeltin, sonra Q^ϕ(x, a)’yı ∈ Ax üzerinde en aza indirin:

Ancak, Q^ϕ(x)’in en aza indirildiği eylemler arasında, a’nın politika ϕ’nin kendisi tarafından verilen eylem olduğunu, yani a = ϕ(x) olduğunu unutmayın. Bu seçim, politika ϕ’yi geri verir, böylece:

Eğer eşitsizlik kesin ise, o zaman ϕ politikasını iyileştirmiş oluruz.

Ancak, önce bir aşama için eylem a*(x)’i seçip sonra ϕ politikasını kullanan bu tür “karma politika” en azından elverişsiz görünüyor. Nasıl çalışacağını inceleyelim. Eğer x1 başlangıç ​​durumuysa, eylem a*(x1)’i seçeriz, sonra x2 durumuna geçeriz. Bu durumdan, ϕ politikasını sürdürürüz ve a2 = ϕ(x2) eylemini seçeriz. Ancak, tüm durum-eylem çiftleri x, a ∈ K için Q-faktörleri Q(x), a’ya sahipsek, a*(x2)’yi belirlemek ve bu eylemi ϕ(x2) yerine kullanmak için kullanabiliriz. O zaman, az önce kullandığımız argümanla, x2'den hesaplanan toplam maliyet, a2 = ϕ(x2) kullanmış olsaydık olacağından ya aynı ya da daha düşük olacaktır. Aynı argümanı tüm sonraki aşamalar için de kullanabiliriz. Bu, eğer tüm x ∈ X için yeni bir politika ϕ′(x) = a*(x) tanımlarsak, ϕ′’nin politika ϕ’yi şu anlamda iyileştirdiği anlamına gelir:

Optimal Politika

Başlangıç ​​durumu x olduğunda, en iyi toplam hesaplanan maliyet/ödülü veren en iyi değer fonksiyonu V *(x)’i her zaman tanımlayabiliriz:

ϕ* o zaman şunu sağlayan bir değerdir:

ϕ*’yi “iyileştirmeye” çalışırsak ne olur? Zorunlu olarak, yukarıdaki eşitsizlik bir eşitlik olurdu çünkü ϕ*’yi iyileştiremezsek, politikayı iyileştirmeye yönelik herhangi bir girişim şu eşitliği getirirdi:

Aksi takdirde ϕ* optimal olmazdı. Elbette, Q-faktörünün tanımı ve ϕ*’nin optimalliği gereği, Q^ϕ* x, ϕ* x = V^ϕ*(x) = V *(x) olmalıdır.

Sonra, bu özdeşliği kullanarak yukarıdaki denklemi şu şekilde yeniden yazabiliriz:

Bu, Bellman Denklemi olarak bilinir. Bu bir fonksiyonel denklemdir ve çözümü belleksiz SDP’ler için optimum değer fonksiyonu V *(x)’i verir. Politika değer fonksiyonu V^ϕ’nin tek çözümü olduğu denklem ile karşılaştırılmalıdır. O denkleme benzer bir denklem türüdür, önemli fark sabit bir politikanın a∈Ax eylemleri üzerinde en aza indirme ile değiştirilmesidir. Ancak, yine de politika değerlendirmesi için tanımlanan denkleme benzer şekilde V gibi bir fonksiyon uzayında T* operatörünü tanımlar. Bu durumda, herhangi bir V′ ∈ V için, V′′ = T*V′ her x ∈ X için şu denklem kullanılarak değerlendirilir:

Genel koşullar altında, V = T*V denkleminin tek bir çözümü vardır ve algoritma:

En uygun değer fonksiyonu V*’ye yakınsar. Bu, en uygun değer fonksiyonu V*’yi sabit nokta yinelemelerini V_n+1 = TV_n, burada T dinamik programlama operatörü ve V1 uygun şekilde seçilmiş bir başlangıç ​​fonksiyonu hesaplayarak değerlendiren değer yinelemesi olarak bilinir. V1, V2,… dizisi en uygun değer fonksiyonu olan sabit nokta V* = TV*’ye yakınsar.

Ayrıca, politika yinelemesi veya aktör-eleştirmen yöntemi ile optimal bir politika türetebiliriz. Politika yinelemesi, Bellman Denklemini çözmenin bir yöntemidir. Değer yinelemesi gibi, algoritma yinelemelidir, ancak iki adım arasında değişir ve değer fonksiyonları yerine ϕ1, ϕ2, … politika fonksiyonları dizisi üretir. İlk adım, geçerli politika ϕn ile başlar ve politika değer fonksiyonu Vϕn’yi, muhtemelen politika operatörü Tϕn’ye sabit nokta yineleme yöntemini uygulayarak değerlendirir. Daha sonra, politika ϕn iyileştirilir ve dizideki bir sonraki politika ϕn+1 elde edilir. Kesin iyileştirme mümkün olmadığında algoritma sonlanır, bu durumda dizideki son politika fonksiyonu optimal politika fonksiyonu ϕ* olur. Politika değerlendirme adımı “eleştirmen” olarak işlev görürken, politika iyileştirme adımı “aktör” olarak işlev görür.

Genel kurulum şu şekildedir: Başlangıç ​​politikası ϕ1 ile başlıyoruz. Ardından ϕ1, ϕ2, … politikalarından oluşan bir dizi yinelemeli olarak üretilir. Tek bir yineleme, geçerli politika ϕi verildiğinde aşağıdaki iki adımdan oluşur:

• Adım 1. Politika değerlendirmesi (eleştirmen) değerlendir: Örneğin, değer yinelemesini kullanarak Vϕi.
• Adım 2. Politika iyileştirme (aktör) ϕi’yi şu şekilde değerlendirerek iyileştirin:

Bu iki adımın tek bir yinelemesinin sonunda, Vϕi+1≤ Vϕi elde ederiz. Bu adımları yinelemeye devam ederiz ve Vϕi+1 = Vϕi gerçekleştiğinde sonlandırırız.

O zaman ϕi = ϕ* en iyi politikadır. En iyi politikanın kendisi benzersiz olmayabilir, Vϕ olsa bile. Bu nedenle, ϕi+1 = ϕi’yi bir durdurma kuralı olarak kullanamayız.

Politika İyileştirme Adımı Örneği

Aşağıda politika yinelemesinin politika iyileştirme (aktör) adımına bir örneği verilmiştir: Minimum indirim maliyetli bir MDP’nin durum uzayı X = 1, 2, 3, …, 50'ye sahip olduğunu varsayalım. Durum x = 3'ten iki eylem kullanılabilir. Eylem a = 1 seçilirse, sürecin her biri 1/2 olasılıkla x = 4 veya x = 5 durumuna geçer ve R(3, 1) = 53 aşama maliyeti gerçekleşir. Eylem a = 2 seçilirse, süreç bir olasılıkla x = 2 durumuna geçer ve R(3, 2) = 35 aşama maliyeti gerçekleşir. İndirim faktörü β = 0,9'dur. Ardından, politika yinelemesinin optimum politikayı değerlendirmek için kullanıldığını varsayalım. n’inci politika yinelemesine ait politika değer fonksiyonu ϕn için şu değerlere sahiptir: V′(2) = 23.5, V′(4) = 46 ve V′(5) = 14.7. Bir sonraki yineleme ϕn + 1, x = 3 durumundan hangi eylemi seçecektir?

Politika ϕn için ihtiyaç duyduğumuz Q faktörleri Q(x, a) = R(x, a) + βE[V ′(y)]’dir, burada beklenti, (x, a) durum eylem çifti için durum geçiş dağılımı üzerinden alınır. Ardından şunlara sahip oluruz:

Ek olarak:

Yani, Q(3, a), x = 3 durumundan ϕn + 1 (3) = 2 tarafından seçilen eylem olan a* = 2 ile en aza indirilir.

Pekiştirmeli Öğrenme ve Dinamik Programlama

Daha önce tartışılan envanter modelini takiben yeni bir SDP tanıtacağız ve bazı benzerlik ve farklılıkları ele alacağız.

Otomatik Poker İçin Bir Model

Farz edelim ki dikkatli bir değerlendirme sonucunda, uygun bir çevrimiçi poker sitesiyle entegre edildikten sonra oyunu otomatik olarak oynayacak bir program geliştirmeye karar verdik. Bu, her turda hangi kartların elden çıkarılacağına ve hangi bahislerin yapılacağına dair kararları içerir. Bu açıkça bir SDP’dir (Stokastik Dinamik Programlama) ve dinamik programlama ilkesinin toplam kazançlarla ilgili olarak optimal oyuna ulaşmak için kullanılabileceği konusunda bir umut vardır. Ancak, bu ideale ulaşmanın önünde birkaç engel bulunmaktadır.

İlk olarak, herhangi bir dinamik programlama için durum uzayı X çok büyük olacaktır. Bir oyuncu, 52 kartlık bir desteden beş kartlık bir el ile başlar. Bu türden (52 5)=2,598,960 farklı el vardır. Hatırlatmak gerekirse, (n k), yani n’den k’yı seçme, binom katsayısıdır ve n farklı nesneden k tanesini sırasız seçimlerinin sayısına eşittir. K adet tur olduğunu varsayalım. Her tur sırasında bazı kartlar elden çıkarılıp değiştirilebilir ve yeniden iddialar yapılır. Kalan tur sayısı, karar verici için hayati önem taşıdığı için durum tanımının bir parçası olarak dahil edilmek zorundadır. Bu aynı zamanda o ana kadar yatırılmış bahis miktarları için de geçerlidir. Bu, durum uzayının büyüklüğü için bir alt sınırın K×2,598,960≤∣X∣ olacağı anlamına gelir.

Daha sonra, bu dinamik programlama modeli için bir eylem a, en azından hangi kartların elden çıkarılacağını belirtmek zorunda olacaktır. Her turda en fazla üç kartın elden çıkarılabileceğini varsayalım. 5 karttan en fazla 3 kart seçmenin (5 3)+(5 2)+(5 1)+(5 0)=10+10+5+1=26 yolu vardır. Bu nedenle, her durum x için tüm uygun eylemler kümesi için bir alt sınır 26≤∣Ax∣ olacaktır.

Daha sonra, maliyet fonksiyonu R(x,a)’nın bellek üzerinde tablo şeklinde saklandığını varsayarsak, bu tablo K×2,598,960×26≤∣X∣∣Ax∣ girdiden az olmamalıdır. Daha kötüsü, geçiş olasılığı çekirdeği P(y∣x,a) bellek üzerinde tablo şeklinde saklandığında, bu tablo aşağıdaki kadar girdili yer kaplayacaktır:

Elbette, problemde daha kompakt bir gösterime izin veren bazı özel yapılar olabilir, ancak bu fırsat olmadığında, ilgili sınırlar bunlardır.

İkinci engel, pekiştirmeli öğrenme ile dinamik programlama arasındaki fark açısından daha temeldir. Model bileşenleri R(x, a) ve P(y ∣ x, a)’yı verimli bir şekilde depolama ve erişme yeteneğimize güvendiğimizi varsayalım. Hala bu bileşenlerin ne olması gerektiğine karar verme sorunuyla karşı karşıya kalırdık. Açıkça, fark edilebilir olasılık kuralları söz konusu olurdu, ancak eylem ve ödül arasında tam bir ilişki geliştirmek yalnızca matematiksel teoriyi kullanarak zor olurdu.

Pekiştirmeli öğrenmenin ajan-çevre etkileşim modeli

Pekiştirmeli Öğrenme Platformu

Dinamik programlamanın prensipleri, otomatik poker oynama uygulaması kavramının en azından kavramsal olarak sağlam olduğunu öne sürer. Doğru bir şekilde formüle edilirse, Bellman’ın Optimallik Denklemi çözümüne dayalı böyle bir uygulama kanıtlanabilir şekilde optimal olur ve herhangi bir insandan daha iyi oynar. Bu nedenle, poker uygulamasında açıklanan böyle bir projeye yönelik engellerin üstesinden gelmek için bir miktar ilgi olmalıdır.

Önemli bir anlamda, pekiştirmeli öğrenme teorisi, dinamik programlama modelinin varlığını, özellikle bellek bağımsızlığı özelliklerini varsayar (Bertsekas, 2019). Ancak, karar verici yalnızca bu modelin çıktısını görür. Bunu netleştirmek için, yukarıdaki şekilde (Sutton & Barto, 2018a’nın Şekil 3.1'inden uyarlanmıştır) gösterilen pekiştirmeli öğrenme platformunu ele alalım. Diyagram, SDP’deki bir aşama olan k’yi ve bir sonraki aşamaya geçişi temsil eder. Şu andaki durum olan xₖ ile başlıyoruz. Ayrıca, önceki aşama maliyeti olan rₖ₋₁ kaydına sahibiz. Karar verici, ödülü optimize etmek ya da bir deneme-yanılma süreci ile en iyi eylemleri öğrenmek için eylemler seçen ajandır.

Makine öğrenmesi bağlamında, ajan, öğrenme ve karar verme yeteneğine sahip bir yapay zeka uygulamasıdır. Ajan, mevcut verileri (xₖ, rₖ₋₁) alır. Ajanın süreç geçmişini depolayabileceğini varsayabiliriz, ancak bunu yapabilme yeteneği önemli bir tasarım hususudur. Daha sonra ajan, çevreye girdi olarak verilen bir karar aₖ alır. Mevcut verilere dayanarak, çevre aşama ödülü rₖ ve bir sonraki aşamanın başladığı bir sonraki durumu xₖ₊₁ çıktısı verir.

Çevre, mevcut süreç durumu, sonraki durum ve ajanın seçtiği eyleme bağlı olarak ödüller döndürür. Eğer SDP bellek bağımsız ise, çevre, dinamik programlama modeli R, Q ile tanımlanır ve SDP modeli (R, Q) tarafından tanımlanan kurallara göre, giriş (xₖ, aₖ) temel alınarak (xₖ₊₁, rₖ) üretebilir.

Ancak, pekiştirmeli öğrenme açısından bakıldığında, (R, Q) açıkça temsil edilmez. Bir simülasyon platformunda, çevre, standart pseudo-rastgele simülasyon yöntemlerine dayalı olarak (xₖ₊₁, rₖ) çıktısı veren ayrı bir programdır (bu konuda mükemmel bölümler için bkz. (S. Ross, 2014) ve (Chambers, 1977)). Tabii ki, canlı bir uygulamada, çevre yalnızca kontrol alanıdır (örneğin, gerçek bir perakende işletmesi veya gişe sistemi kurulumu).

Bu durum, pekiştirmeli öğrenmenin, çevrenin ödül ve durum geçişlerini üretmek için kullandığı kuralların bilinmemesi anlamında modelden bağımsız olarak tanımlanmasına yol açar. Bir model, en azından örtük bir şekilde mevcuttur. Ancak, yalnızca herhangi bir durum-eylem çifti (x, a) üzerinden elde edilen ödülü gözlemleriz. Bu, prensipte, kontrollü bir deneme-yanılma süreciyle optimal bir eylem dizisini öğrenebileceğimiz anlamına gelir.

Bu, otomatikleştirilmiş poker uygulamamızda tanımlanan ikinci engelin üstesinden gelinmesine büyük ölçüde yardımcı olur. Bir uygulamayı çevrimiçi bir poker hizmetiyle entegre edersek, yukarıdaki şekilde temsil edilen türde bir çevreye sahibiz ve bir ajan programlayabiliriz. Ayrıca, bu yapı, otomatikleştirilmiş poker uygulamamızın ilk engelinin en azından kısmen üstesinden gelmemizi sağlar.

Pekiştirmeli öğrenme genellikle dinamik programlama bileşenleri R(x, a) veya P(y ∣ x, a)’yı tahmin etmeye çalışmaz. Bunun yerine, amaca bağlı olarak bir politika değer fonksiyonu V ϕ(x), x ∈ X veya Q-faktörleri Q(x, a),(x, a) ∈ K olarak bilinen ilgili nicelikleri tahmin etmeye çalışır (bu, ileriki yazılarda tanımlanacaktır). Bu nedenle, en kötü ihtimalle, karmaşıklık düzeyi |X| |Ax| olan nesneleri depolamalıyız, en iyi ihtimalle, yalnızca karmaşıklık düzeyi X olan nesneleri depolamamız yeterlidir. Bu, dinamik programlama modeli için gereken geçiş olasılığı çekirdeği için |X|² |Ax| depolama gereksinimiyle oldukça iyi bir şekilde karşılaştırılabilir.

Politika Bağımlı ve Politika Bağımsız (On-policy vs Off-policy) Pekiştirmeli Öğrenme

Pekiştirmeli öğrenmede iki temel hedef vardır: optimal davranışı öğrenmek ve optimal davranışı uygulamak. Örneğin, bir uygulamanın bir video oyunu oyuncusuna karşı bir rakip geliştirmek üzere tasarlandığını düşünelim. Bu durumda, uygulama “ajan”ı, oyuncu ise “çevre”yi temsil eder. Ajan, çevreyi keşfetmeden önce optimal stratejilere sahip olmayacaktır, ancak yine de etkili bir rakip olarak hareket etmesi beklenir.

Bu hedefler arasında bir çelişki vardır. Keşifçi davranış (exploratory behavior) deneme-yanılma yoluyla optimal stratejilerin öğrenilmesini sağlarken, faydacı davranış (exploitative behavior) öğrenilen stratejilerin uygulanarak ödüllerin maksimize edilmesine odaklanır. Genellikle öğrenmenin başında keşifçi davranışa ağırlık verilir, ajan yeterince bilgi topladıktan sonra faydacı davranış ön plana çıkar.

Pekiştirmeli öğrenme algoritmaları, bu iki davranışı dengelemek için farklı stratejiler kullanır:

• Politika Bağımlı (On-policy) algoritmalar: Ajan, öğrenme sırasında hem optimal bir politika oluşturmayı hem de süreç boyunca optimal maliyet/ödüller elde etmeyi hedefler. Bu, örneğin simüle edilmiş oyun rakiplerinde gereklidir.
• Politika Bağımsız (Off-policy) algoritmalar: Ajan, sadece optimal bir politika öğrenmeyi amaçlar. Öğrenme sürecinde optimal ödülleri elde etmek gerekmez. Örneğin, bir envanter yönetimi simülasyonunda, yalnızca öğrenme odaklı bir yaklaşım benimsenebilir.

Bu farklı yaklaşımlar, uygulamanın amacına ve bağlamına bağlı olarak seçilir.

Pekiştirmeli Öğrenme Sistemlerinin Bileşenleri

Politika Değerlendirmesi

Bir politika değer fonksiyonu Vϕ’nin oynadığı rol, hem pekiştirmeli öğrenme hem de dinamik programlama için ortaktır. Pekiştirmeli öğrenme terminolojisinde, en kısa yol SDP’ye epizodik denir. Bu nedenle, daha fazla maliyetin birikmediği bir son durum xΔ ile sonlanan durum geçişleri dizisinden oluşur. Hanoi Kuleleri gibi bir bulmacayı çözmek buna bir örnek olabilir. O zaman Vϕ(x0), başlangıç ​​durumu x0'dan bitiş durumu xΔ’ya kadar biriken toplam maliyet olarak yorumlanabilir. Algoritma tasarımcısının (okuyucunun) herhangi bir başlangıç ​​durumu ve geçmişi kullanarak ajan/ortam etkileşimlerini özgürce yeniden başlatabileceğini unutmamak önemlidir.

Hanoi Kuleleri

Yani, pekiştirmeli öğrenme platformumuzda başlangıç ​​durumu x0'ı ayarlayabiliriz. Ayrıca, aracının ak = ϕ(xk) eylemlerini seçmesini sağlayabiliriz (pekiştirmeli öğrenme algoritmamızın tasarımımızın bir parçası olarak). Daha sonra, diyelim ki N geçişten sonra, son durum xΔ’ya ulaşılana kadar ajan-çevre etkileşimlerini sürdürürüz. Biriken toplam maliyet R = r1 + r2 + … + rN − 1 + rN ‘dir, ancak R, ortalama E[R] = Vϕ(x0) olan bir rastgele değişkendir, bu nedenle bu simülasyonları tekrarlayabilir ve SDP’yi xΔ durumundan sonra x0 durumunda yeniden başlatabiliriz. Bunu n kez yaptığımızı varsayalım. Bu, x0'dan xΔ’ya giden yörüngelerin n adet simüle edilmiş tekrarını ve R denkleminde olduğu gibi hesaplanan n adet toplam maliyet tekrarı R1 , …, Rn verir.

Basit bir örneklem ortalaması yöntemi, n’yi artırarak giderek daha doğru hale getirilebilen tahmini verir:

Şu an için, pekiştirmeli öğrenmede önemli bir işlevi olacak bir şeye sahibiz, yani, önceki görevi tüm başlangıç ​​durumları x0 = x için tekrarladıktan sonra Vϕ(x)’i tahmin etme yeteneği. Elbette, bu, politika değeri yineleme algoritmasının yaptığı şeydir, ancak dinamik programlama modeli bileşenleri R(x, a) ve P(y ∣ x, a)’nın bir temsiline sahip değilsek, bu algoritma kullanılamaz.

Bu sorun için pekiştirmeli öğrenmede geleneksel terim politika değerlendirmesi veya politika tahminidir. Ancak, az önce tanımladığımızdan çok daha verimli politika değerlendirme yöntemlerinin geliştirilmesinin pekiştirmeli öğrenme teorisinin merkezi bir özelliği olduğunu belirtmemiz gerekir. Bu, özellikle birçok pekiştirmeli öğrenme algoritmasının çok sayıda politika değerlendirmesi gerektirebileceği düşünüldüğünde doğrudur.

İlk fark edilmesi gereken şey, her bir tekrar edilen trajektörün sadece Vϕ(x0)’in bir tahminini değil, aynı zamanda x1​’in Vϕ(x1)’ini de içerdiğidir; burada x1, trajektörde ziyaret edilen ikinci durumdur. Özellikle, R′=R−r1=r2+…+rN−1+rN​ şeklindedir.

Prensip olarak, x = xk durumunu ziyaret eden herhangi bir tekrarlanmış yörüngeden Vϕ(x) tahminlerini, R′′ = rk + 1 + … + rN − 1 + rN biçiminde elde edebiliriz, çünkü R′′, x = xk başlangıç ​​durumundan xΔ’ya kadar SDP tarafından hesaplanılan toplam maliyetin bir gözlemidir. Başlangıç ​​durumu x’ten R1(x), …, Rnx(x) gibi toplam maliyet gözlemleri olmak üzere nx tane toplayabildiğimizi varsayalım. Sonra, örneklem ortalamaları oluşturarak tüm politika fonksiyonunu tahmin edebiliriz:

Bu, Monte Carlo politika değerlendirmesi olarak bilinir; burada, ajan ϕ politikasını uyguladığında çevre tarafından üretilen toplam ödülleri doğrudan gözlemleyerek bir politika değer fonksiyonu Vϕ(x) tahmin ederiz. Bu yöntem iki farklı şekilde gelir. “İlk ziyaret” yöntemi, yalnızca bir durum bir bölüm içinde ilk kez ziyaret edildiğinde hesaplanılan maliyetleri kullanır, yani yalnızca durum x ilk kez gözlemlendiğinde elde edilen toplam maliyet gözlemleri Ri(x) kullanır. “Her ziyaret” yöntemi, tüm gözlemlerden bir bölüm içinde hesaplanılan tüm maliyetleri kullanır. İkinci yöntem daha fazla veri kullandığı için tercih edilebilir görünse de, aynı zamanda önyargılı bir tahmindir. nx’in rastgele olduğunu ve bu nedenle potansiyel olarak örnek ortalamasına önyargı getirdiğini hatırlayın. Bu, her ziyaret yöntemi için gerçekleşir ancak ilk ziyaret yöntemi için gerçekleşmez. Her iki yöntem de kullanılır ve hiçbiri tüm modeller için diğerine tercih edilmez. Ancak her ikisi için de, yaklaşıklık hatası nx → ∞ olduğunda sıfıra yaklaşır.

Pekiştirmeli Öğrenme ve Tekrarlı Güncelleme (Iterative Updating)

Bu noktada, örnek ortalaması için basit bir güncelleme formülünü gözden geçirmek faydalı olacaktır. Diyelim ki elimizde n tane gözlem var: x₁, x₂, …, xₙ. Daha sonra dizideki ilk m gözlemden elde edilen örneklem ortalamasını ele alalım:

Sonra belirli bir uygulama için gözlemleri ardışık olarak aldığımızı varsayalım. İlk m gözlemi aldıktan sonra x̄m’yi hesaplarız. Daha sonra bir sonraki gözlemi x_m+1 alırız ve x̄_m+1'i hesaplamak isteriz. Elbette, x̄_m+1'i ilk m+1 gözlemin hepsini kullanarak hesaplamak yerine, yalnızca x̄m ve x_m+1 gerektiren bir güncelleme kuralı kullanabiliriz:

Burada sabitler dizisini γm = 1/m, m ≥ 1 olarak tanımlıyoruz.

Pekiştirmeli öğrenmede, kuralların güncellenmesi genellikle şu şekilde düşünülür:

[yeni tahmin] [eski tahmin] + [adım boyutu] × [hedef]−[eski tahmin]

Bir güncelleme kuralındaki hedef, ardışık güncellemelerin hareket etmesini istediğimiz herhangi bir niceliktir ve bir hedefi temsil eder. Eski tahmin hedeften küçükse, artırılacaktır. Elbette, bir güncelleme kuralında kullanılan hedef rastgele olabilir, ancak her zaman aynı ortalama μ’ye sahipse, güncellemeler o değere doğru hareket etme eğiliminde olacaktır. Adım boyutu, pekiştirmeli öğrenmede genellikle bir öğrenme oranı olarak anılır ve güncellemenin büyüklüğünü kontrol eder. Bu değerin bir olarak ayarlandığında güncelleme kuralının basitçe şu hale geldiğini unutmayın:

[yeni tahmin] [eski tahmin] + 1 × [hedef]−[eski tahmin] = [hedef]

Bu arzu edilebilir görünse de, birçok pekiştirmeli öğrenme uygulamasında hedefin rastgele olduğu ve bu güncelleme kuralının oldukça istikrarsız bir davranışa yol açacağı unutulmamalıdır. Bu nedenle, öğrenme oranının genellikle yavaşça sıfıra düşmesine izin verilir.

x̄_m+ 1 = x̄m + γm + 1 x_m+1 − x̄m ile verilen örnek ortalaması için yinelemeli denklemi şu şekilde gösterebiliriz. Eski tahmin x̄m, hedef x_m+1, öğrenme oranı 1/m ve yeni tahmin x̄m + 1'dir. Her hedefin ortalaması μ aynıysa, ardışık güncellemeler bu değere doğru hareket etme eğilimindedir.

Monte Carlo politika değerlendirme yöntemi için, Vϕ(x)’i tahmin etmeye çalışıyoruz. Tahmin ediciyi V^ϕ(x) olarak belirtin. Güncelleme kuralı burada Rk = rk + 1 + … + rN iken şudur:

Bu ifadenin bir güncelleme kuralı olduğunu ve bu nedenle Vϕ(x) için alt simgeleri atlayabileceğimizi unutmayın, aksi takdirde Vkϕ(xk) eski tahmin ve Vk + 1 ϕ(xk) yeni tahmin olurdu. Burada, hedef Rk, başlangıç ​​durumu xk olan bir bölüm tarafından varsayılan toplam maliyetin doğrudan gözlemidir (ilk ziyaret yöntemi için, bu tür güncellemelerin hepsi yapılmaz). γ’nin belirtilmeden bırakıldığını, ancak genellikle güncelleme sayısıyla azaldığını unutmayın. Uygulamada, pekiştirmeli öğrenme, değerini seçmek için birden fazla stratejiye izin verir, ancak genellikle örneklem ortalaması için kullanılan γ = γm = 1/m ile aynı etkiye sahip olması amaçlanır.

Ancak, Rk tek olası hedef değildir. Şunu kabul ediyoruz:

Böylece r_k+1 + βVϕ(xk + 1) bir hedef olarak hizmet edebilir, ancak V ϕ(x_k+1) bilinmez (aksi takdirde tahmin etmemiz gerekmezdi).

Ancak, bir V^ϕ(x_k+1) tahminimiz var ve bu nedenle, r_k+1 + βV^ϕ(x_k+1) hedefimiz var, bu da güncelleme kuralına yol açıyor:

V^ϕ tahmininin kendisinin hedefte kullanılmasına bootstrapping denir. Bir güncelleme kuralında, tahminin kendisi bazen hedefin bir bileşeni olarak kullanılır. Bu da bootstrapping olarak adlandırılır. Monte Carlo yöntemine gelince, ya ilk ziyaret (first-visit) ya da çoklu ziyaret (many-visit) varyantı kullanılabilir. Güncelleme kuralları, öğrenme oranı dizisinin uygun bir şekilde seçilmesi durumunda tutarlıdır. Ancak, iki prosedür eşdeğer değildir ve ilk ziyaret ve çoklu ziyaret varyantlarında olduğu gibi, hiçbiri her durumda üstün değildir. Genellikle bir yanlılık-varyans dengesi söz konusudur. Monte Carlo yönteminin hedefi yanlılıktan arınmış (unbiased) iken, bootstrapping yönteminin hedefi yanlıdır. Ancak, bootstrapping yönteminin hedefi tipik olarak daha düşük varyansa sahiptir.

Önyargı-Varyans Dengesi

Herhangi bir parametre θ’nin θ^ kestiricisi, E[θ^] = θ ise tarafsızdır (aksi takdirde taraflıdırlar). Beklentimizin aksine, yaygın olarak kullanılan birçok kestirici de dahil olmak üzere tüm kestiriciler tarafsız değildir. Bir kestirimin önyargısı şu şekilde tanımlanır:

Ortalama kare hatası için, tahmin edici θ’nin sapması şu şekilde verilir:

Biası θ^’den çıkararak önyargısız bir tahmin elde etmek ve böylece riski azaltmak basit bir iş gibi görünebilir. Ancak, bias θ’ya bağlıysa (ki θ bilinmeyendir) bunu yapamayız ve bu durum genellikle böyledir.

Ortalama kare hata (MSE), güncellenmiş tahminciler θ^_n, n ≥ 1'in bir dizisinin tutarlılığını tanımlamak için kullanılabilir. Bir dizinin tutarlı olduğunu, θ^_n’in MSE’si n arttıkça sıfıra yaklaşıyorsa söyleriz. Pekiştirmeli öğrenmede önemli bir soru, bir güncelleme dizisinin tutarlı olup olmadığıdır.

Eşitlik MSE = var[θ^] + Bias[θ^]² ilişkisi, bias-varians ödünleşimini ortaya çıkarır; bu, MSE’yi minimize etmek için varians ve bias arasında en iyi dengeyi bulma girişimidir. En iyi tahminci, mutlaka en küçük variansa veya en küçük bias değerine sahip olan değildir, ancak bu ikisi arasındaki en iyi ödünleşimi (en iyi anlamında en küçük MSE’yi) sağlayan tahmincidir.

Aslında, bunu daha önce karşılaşmıştık. Monte Carlo politika değerlendirmesinin her ziyaret varyantının, daha fazla veri kullandığı için ilk ziyaret varyantına göre daha küçük bir variansa sahip olduğunu hatırlayın. Ancak, her ziyaret varyantı biaslıdır, ilk ziyaret varyantı ise değildir. Hangi varyantın en küçük MSE’ye sahip olacağı, uygulamaya bağlıdır (Bertsekas & Tsitsiklis, 1996, Bölüm 5.1–5.2). Ancak, her iki varyant da tutarlıdır.

TD(λ)

Birçok pekiştirmeli öğrenme uygulamasında, politika değerlendirmesi birden fazla kez gerçekleştirilmelidir. Pekiştirmeli öğrenmenin başarısının büyük bir kısmı, zamansal fark öğrenmesi olarak bilinen bir politika değerlendirme yöntemine atfedilebilir. Bu, genellikle TD(λ) olarak adlandırılan yöntemler ailesidir; burada λ ∈ [0, 1], belirli bir TD(λ) algoritmasını tanımlayan iz bozunma parametresidir. λ’nın daha yüksek değerleri, güncellemelerin gelecekteki maliyetler/ödüllerden daha fazla etkilenmesine izin verir.

TD(λ)’yı anlamak için, özellikle güncelleme kurallarını dikkatlice karşılaştırmak faydalı olacaktır. Özellikle, ikinci denklem şu şekilde yazılabilir:

Burada dk, verilen bir politika değer fonksiyonu politikası Vϕ(x)’in zamansal farkıdır. Zamansal fark, (a) eylem a seçildiğinde, daha sonra politika ϕ kullanıldığında ve (b) politika ϕ her zaman kullanıldığında hesaplanılan toplam maliyet/ödül farkıdır. Bunu yazabiliriz:

O zaman, dk, dk + 1, … zamansal farklarının ağırlıklı toplamına dayalı genel bir güncelleme kuralı tanımladığımızı varsayalım.

Bazı parametreler için λ ∈ [0, 1]. Örneğin, ilk ziyaret veya her ziyaret varyantını seçtikten sonra, bu güncelleme kuralı TD(λ) politika değerlendirme yöntemini tanımlar.

Aslında, biraz cebirden sonra, TD(0)’ın güncelleme kuralı tarafından tanımlanan önyükleme yöntemi olduğunu, TD(1)’in ise güncelleme kuralı tarafından tanımlanan Monte Carlo yöntemi olduğunu görebiliriz. λ’nın 0 ile 1 arasındaki herhangi bir değeri, λ’nın 0'a yakın olması önyüklemeyi, λ’nın 1'e yakın olması ise Monte Carlo örneklemesini vurgulayan bir hibrit yöntemi tanımlar. λ’nın en iyi seçimi, pratikte, genellikle deneme yanılma meselesidir. Bildirilen tercih edilen değerler kesinlikle 0 ile 1 arasında olma eğilimindedir.

Deneyim Tekrarı ve Seyrek Ödüller

Pekiştirmeli öğrenmenin ayırt edici özelliği, politikasını deneyim (çevre) yoluyla öğrenmesidir; bu çevre, simüle edilmiş veya gerçek olabilir. Bu, örneğin TD(λ) algoritmasında kullanılan bu deneyimi tanımlayan verilerin potansiyel olarak oldukça değerli bir meta olduğunu ifade eder. Deneyim tekrarı, verilerin depolanıp yeniden kullanıldığı bir dizi tekniği ifade eder. Rastgele yeniden örnekleme, temelde yeni deneyimler oluşturmak için kullanılır. Deneyim tekrarı ve ilgili yöntemler, pekiştirmeli öğrenme uygulamalarının performansını iyileştirmek için uzun süredir kullanılmaktadır (Cichosz, 1999; Bertsekas, 2019).

Deneyim tekrarının varyantları, pekiştirmeli öğrenme uygulamalarında sıklıkla ortaya çıkan önemli bir sorun olan seyrek ödül problemine (bir bölümde nadiren ortaya çıkan, muhtemelen yalnızca bölümün sonunda alınan ödüller) odaklanmaktadır. Örneğin, bir oyun oynama uygulaması tasarlamak istediğimizi varsayalım. Bu, prensipte pekiştirmeli öğrenme veya dinamik programlama modeline dayanabilir. Ödül kavramı her iki yöntemde de benzerdir ve modelin en basit formunda, yalnızca bir aşamada sıfırdan farklı bir ödül elde edilebilir. Özellikle, R(x, a) = 0'dır, ancak durum-eylem çifti (x, a) doğrudan bir kazanıma yol açarsa, R(x, a) = 1 olur. Daha genel olarak, pekiştirmeli öğrenme platformunun çevresinden gelen ödüllerin çoğu sıfırsa, uygulamanın optimal bir politikaya doğru ilerleme kaydetmesi zor olacaktır.

Bu soruna bir çözüm, öncelikli (veya seçici) deneyim tekrarıdır (Isele & Cosgun, 2018). Deneyim verilerinin yeniden örneklemesi, pozitif ödüllere sahip dizilerin veya daha genel olarak, daha yüksek ödüllerle sonuçlanan dizilerin temsilini artıracak şekilde ağırlıklandırılabilir. Bu, öğrenmeyi daha etkili hale getirir.

Bir diğer varyant ise geriye dönük deneyim tekrarlandırmasıdır. Belirli bir veri bölümünün yeniden örnekleme için mevcut olduğunu varsayalım. Belki de bu bölümde bir hedefe ulaşılamamış ve bu nedenle başarısızlık olarak sınıflandırılabilir. Ancak, benzer bir hedefin başarılmış olması mümkün olabilir. Örneğin, bir araç bir hedef konuma yönlendirilememiş olabilir, ancak hedefin beş adım sağındaki bir konuma ulaşmış olabilir. Dolayısıyla, hedef ulaşılan konuma değiştirilirse, bölüm bir başarı olarak kabul edilebilir ve değerli bir öğrenme verisi olabilir (örneğin, “başarılı politika” değiştirilebilir veya benzer bir görevi gerçekleştirmek için kullanılabilir).

Daha geniş bir ödül kavramı da tanımlanabilir. Ödüllerin seyrek olduğu durumlarda, bir hedefe yönelik amaçlı şekilde ilerleyen bir politika geliştirmek için yeterli temel yoktur. Bu durumda, bir görevin başarılı bir şekilde tamamlanmasıyla sonuçlanmayan, ancak görevin tamamlanmasını kolaylaştırması muhtemel olan davranışlara yönelik içsel ödüller tanıtılabilir. Örneğin, merak odaklı davranış daha büyük bir deneyim çeşitliliği arar ve pekiştirmeli öğrenme platformunda, belirli bir görevin tamamlanmasından bağımsız olarak ödüllendirilebilir.

Politika İyileştirme

TD(λ) yöntemiyle bir değer fonksiyonu Vϕ’yi yaklaşık olarak hesaplayarak bir politikayı (ϕ) nasıl değerlendireceğimizi öğrendik. Ancak, toplam maliyeti en aza indiren veya toplam ödülü maksimize eden en iyi politika ϕ*’yi belirleme kontrol problemine hala odaklanmamız gerekiyor. Φ’nin tüm uygun politikalar ailesi olduğunu varsayalım (ϕ ∈ Φ). Diyelim ki iki politika ϕ1, ϕ2 ∈ Φ veriliyor. Politika değerlendirme yöntemini her zaman kullanarak değer fonksiyonlarını Vϕ1 ve Vϕ2 tahmin edebilir ve karşılaştırabiliriz; böylece değerlendirilen iki politika arasından en iyisini seçebiliriz. İlke olarak, tüm politikalar ϕ ∈ Φ’yi değerlendirebilir ve ardından en iyi politikayı ϕ* ∈ Φ olarak belirleyebiliriz. Eğer Φ küçükse, bu yöntem uygulanabilir.

Aslında, ödülleri doğrudan karşılaştırarak birden fazla eylem arasından birini seçmek, bandit süreç modellerinin (Berry & Fristedt, 1985; T. Lai & Yakowitz, 1995) amacıdır. Ancak, tipik bir SDP uygulaması için Φ bu yaklaşım için çok büyük olacaktır. Otomatik poker oynama uygulamasını ele alalım. Durum uzayının büyüklüğü için K × 2,598,960 ≤ |X| ve uygun eylem uzayının büyüklüğü için 26 ≤ |Ax| alt sınırlarını geliştirmiştik. Bir politika ϕ, her durumu (x ∈ X), bir eyleme (ϕ(x) = a ∈ Ax) eşlemelidir.

Kombinatorik temel ilkeleri kullanarak, toplam politika sayısı için şu alt sınırı elde ederiz:

Açıkça, her ϕ ∈ Φ için basitçe politika değerlendirmesi yapamayız. Yine de pekiştirmeli öğrenme bu karmaşıklıktaki sorunlara uygulanabilir ve uygulanmaktadır.

Yaygın bir yöntem, dinamik programlamanın politika yineleme yöntemine dayanan “Aktör-Eleştirmen” yöntemidir. “Eleştirmen”, örneğin bir TD(λ) algoritması kullanarak politika değerlendirmesi yapar. Daha sonra “Aktör” politika iyileştirme adımını gerçekleştirir. “Aktör”ün eylemleri değiştirme ve ödülleri gözlemleme yeteneği, Q faktörlerinin tahmin edilmesine izin verir.

Daha sonra bunlar politikayı iyileştirmek için kullanılır.

Q Faktörleri ve Kontrol Problemi

Pekiştirmeli öğrenmedeki en önemli yöntemlerden biri Q-öğrenimi olarak bilinir ve nispeten yakın zamanda Chris Watkins’in 1989 tezinde geliştirildi ve daha sonra daha kesin bir şekilde karakterize edildi. Q-öğrenimi, hedefi Q-faktörü Q(x, a) olan bir TD(0) algoritmasıdır. Aslında şu şekildeki Bellman denkleminin bir ayrıştırılmasına dayanır:

Kontrol problemi için, Denklem’e ikame edilebilen en iyi politika ϕ* ile ilgileniyoruz. Ancak, ϕ* henüz belirlenmediği için, yalnızca dolaylı olarak uygulanabilir. Daha sonra, kontrol problemi için kullanılacak olan ortaya çıkan Q faktörlerini basitçe Q(x, a) olarak gösteriyoruz. Sonra Denklem şu hale gelir:

Sonra, yukarıdaki denklem pekiştirmeli öğrenme kontrolünün iki biçimine daha yol açar.

Q-learning

Şunu yazabileceğimizi hatırlayalım:

Bu, denklem’e ikame edilerek elde edilebilir:

Bu daha sonra belirli bir değer fonksiyonu Vϕ yerine Q-faktörleri Q(x, a)’yı tahmin etmek üzere tasarlanmış bir TD(0) algoritması biçimine yol açar. Bu güncelleme kuralını kullanır:

Temel olarak Q-öğrenimi, Bellman denkleminin bir yaklaşımına dayalı olarak Q faktörlerinin yinelemeli bir tahminidir ve şu tahmini içerir:

xk durumundan seçilen ak eyleminin, gerçekte optimal kontrole, yaklaşık veya başka bir şekilde ulaşmaya yönelik herhangi bir girişimi temsil etmesi gerekmediğini unutmayın. Bu nedenle, Q-öğrenme, politika bağımsız bir algoritma olarak adlandırılır. Q-faktörlerini tahmin etmek için tasarlanmıştır, ancak bunu, optimal kontrol tarafından yönetilen bir SDP’yi gözlemlemeden de yapabilir. Bu nedenle, optimal maliyet performansına ulaşmak için herhangi bir girişimde bulunmak gerekli değildir.

SARSA (State-Action-Reward- State-Action)

SARSA, başlangıçta Rummery ve Niranjan tarafından 1994'te önerilen bir pekiştirmeli öğrenme kontrol algoritmasıdır. Adı “durum-eylem-ödül-durum-eylem” ifadesinin kısaltmasıdır. Qlearning gibi, Q-faktörleri Q(x, a)’yı tahmin etmek için kullanılan bir TD(0) yöntemidir ve yukarıda verilen tahmine benzer bir tahmine dayanır. Ancak, hesaplanılan maliyeti optimize etmek için optimal bir politika uygulamayı amaçladığından, politikaya uygun bir algoritmadır.

Buna göre, Q-faktörlerinin en son tahminlerini kullanan kuralı kullanarak eylemleri seçer:

Bu, şu tahminle sonuçlanır:

Güncelleme kuralı daha sonra şu şekile gelir:

Keşif ve Sömürü

Pekiştirmeli öğrenmede kontrol yöntemleri genellikle Q-faktörlerinin tahminine dayanır, bu durum Q-learning veya SARSA güncelleme kurallarından da anlaşılmaktadır.

TD(λ) algoritmalarında, belirli bir durum-eylem çifti x, a ∈ K için bir Q-faktörü Q(x, a) tahmini, bir örnek yörüngesi o çifti ziyaret ettiğinde (yani, (xk, ak) = (x, a) bir k aşaması için doğru olduğunda) güncellenir. Hatırlayacağınız üzere çoğu istatistiksel tahmin için MSE ≈ C / √n formülüne sahibiz; burada C bir sabit ve n, tahmine katkıda bulunan gözlem sayısıdır.

Bu durum TD(λ) (Bertsekas, 2019) için de geçerlidir, burada n, (x, a) çiftine yapılan ziyaretlerin sayısı olur. Durum x için optimal eylem ϕ*(x) = a*, Q(x, a)’yı minimize eden eylemdir, aşağıdaki kimliğe göre:

Bu nedenle, optimal eylem a∗ ile doğru tanımlamanın garanti edilemeyeceğini anlamak önemlidir, eğer Q(x,a) tüm a∈A için tam olarak bilinmiyorsa. Bununla birlikte, tüm Q faktörlerinin yaklaşık hata payı sıfıra yaklaştığında, her durum için optimal eylemleri doğru şekilde tanımlama olasılığının 1 'e yaklaştığı da doğrudur.

Az önce savunduğumuz gibi, Q(x,a) tahminleri için MSE≈Cn olacaktır; burada nnn, pekiştirmeli öğrenme algoritmasının öğrenme sürecinde (x,a) çiftinin kaç kez ziyaret edildiğini temsil eder. Dolayısıyla, genel bir kural olarak, pekiştirmeli öğrenme algoritmasının optimal politikaya yakınsaması için her durum-eylem çiftinin (x,a)∈K sonsuz kez ziyaret edilmesi gereklidir. Pratikte bu, pekiştirmeli öğrenme modelinin tüm durum-eylem uzayını dengeli bir şekilde keşfetmeye devam etmesi gerektiği anlamına gelir.

Politika bağımlı (on-policy) ve politika bağımsız (off-policy) pekiştirmeli öğrenme algoritmaları arasındaki ayrımı hatırlayın. Bu, pekiştirmeli öğrenme platformunun ajan bileşeninin iki farklı davranış biçimine dayanmaktadır (yukarıdaki Şekil’e bakınız). Keşif davranışı, optimal politikaları öğrenmekle ilgilidir, onları uygulamakla değil. Az önce tartıştığımız gibi, bu davranışın özel amacı, her durum-eylem çiftinin (x,a) sürekli ziyaret edilmesini sağlamaktır. Yalnızca optimal politikayı öğrenmekle ilgilenen bir pekiştirmeli öğrenme algoritması politikasız bir algoritmadır ve ajanının yalnızca keşif davranışı sergilemesi gerekir. Bu durum, eylem seçiminde herhangi bir özel kısıtlama olmadığı için Q-öğrenme gibi politikasız algoritmalar için bir sorun teşkil etmez.

Buna karşılık, politikalı bir algoritma maliyeti veya ödülü optimize etmeye çalışır. Eğer Q faktörleri Q(x,a) tam olarak bilinseydi, bu yalnızca politika kullanılarak kolayca yapılabilirdi:

Bu, gördüğümüz gibi optimal olandır. Elbette, bir pekiştirmeli öğrenme uygulamasında, Denklem’de kullanılması için yalnızca Q(x,a) tahminleri mevcut olacaktır.

Bu şekilde oluşturulan bir politika fonksiyonu ϕ(x) tarafından seçilen eylemler, açgözlü bir politika olarak adlandırılır. Bir on-policy algoritmasının amacı ödülü optimize etmek olduğundan, bu tür bir politikayı kullanması doğaldır. SARSA bir on-policy algoritmadır ve açgözlü bir politikadan faydalanır.

Elbette, yalnızca Q(x,a) tahminleri mevcut olduğunda, açgözlü bir politikanın optimal olacağına dair bir garanti yoktur. Bu garanti yalnızca her bir Q faktörü tahmininin giderek daha doğru hale gelmesiyle mümkün olur ki bu da yalnızca ajanın yeterli düzeyde keşif davranışı göstermesi durumunda gerçekleşebilir.

Bu durum, sömürü ile keşif arasındaki denge sorununu tanımlar. Bu, on-policy pekiştirmeli öğrenmenin iki doğası gereği çelişen hedefinden kaynaklanır. Birincisi, optimal politikayı öğrenmek isteriz (keşif). İkincisi, SDP çevrim içiyken optimal politikayı kullanmak isteriz (sömürü). İlkesel olarak yalnızca optimal politikayı yaklaşık olarak bulabileceğimizi kabul ederiz. Bu, yaklaşık değer ne kadar doğru olursa, minimize etmek istediğimiz gerçek maliyetin o kadar düşük olacağı anlamına gelir. Ancak öğrenebilmek için SDP’nin keşif yapması gerekir ki bu da doğası gereği optimal olmayan bir durumdur. Bu nedenle amaç, iki davranış arasında bir denge kurmaktır. Kısaca, sömürü ödülü maksimize etmeye yönelik çabayı ifade ederken, keşif öğrenme odaklı davranışı ifade eder.

Basit bir çözüm ϵ-açgözlü algoritmadır. İlk olarak, Denklem’deki bir politikayı maliyeti azaltmaya çalıştığı için açgözlü olarak adlandırırız. Bir ϵ-açgözlü politika, açgözlü politikayı 1−ϵ1 olasılıkla (sömürü) ve keşif politikasını ϵolasılıkla seçen rastgele bir politikadır. Bu, basitçe tüm uygun politikalar arasından rastgele bir seçim olabilir. Daha sonra ϵ genellikle sıfıra yakınsar, böylece açgözlü politika giderek baskın hale gelir. Ancak, keşif davranışının sonsuz kez seçilmesini sağlamak için ϵ’un yeterince yavaş azalması gerekir (örneğin ϵk=1/k bu durumu sağlar).

Pek çok bilinen pekiştirmeli öğrenme algoritması, durum-eylem uzaylarının dengeli örneklemesine dayanır; örneğin, öncelikli tarama. Ayrıca, bazı algoritmalar özel olarak sömürü/keşif dengesini sağlamak amacıyla tasarlanmıştır.

E³ algoritması, keşif ve kesinlik eşdeğeri kontrollerini (veya izin verilen öğrenme miktarı göz önünde bulundurularak yapılabilecek en iyiyi) harmanlar. Rmax algoritması ise daha basit bir yaklaşımı benimseyerek, yeterince temsil edilmeyen durum-eylem çiftleri (x,a) için maliyet R(x,a) değerini geçici olarak düşürerek keşif davranışını daha verimli bir şekilde hedefler.

Yapay Sinir Ağları ve Pekiştirmeli Öğrenme

Pekiştirmeli öğrenmedeki özellikle dikkat çekici bir uygulaması, TD-Gammon olarak bilinen ve tavla oyununu rekabetçi bir seviyede oynayabilen bir SDP’nin geliştirilmesiydi. Bu SDP dinamik programlama modeli olarak formüle edilseydi, durum uzayı X’in tüm olası tahta konfigürasyonlarını içermesi gerekecekti ve bu nedenle açıkça tam biçimde depolanamayacak kadar büyük olacaktı. Bu tür uygulamaları mümkün kılmak için, dinamik programlama modeli bileşenleri R ve Q, değer fonksiyonları V(x) veya Q-faktörleri Q(x, a) için en azından bir yaklaşımı olabildiğince verimli bir şekilde depolamak amacıyla sıkıştırma teknikleri kullanmak bir olasılık olacaktır.

Bu, dinamik programlama için yapay sinir ağları (ANN) veya derin pekiştirmeli öğrenme kullanılarak gerçekleştirilebilir. Yapay sinir ağlarının ilk olarak 1940'larda tanıtıldığını, ancak derin öğrenmenin ortaya çıkmasıyla daha yakın zamanda çok daha fazla önem kazandığını belirtmek gerekir.

Çok Katmanlı Algılayıcı (Perseptron)

Yapay sinir ağı (YSA), bir girdiden bir çıktıya eşler. Bu nedenle, bir denetimli öğrenme uygulaması için eğitilebilir.

Geniş bir ağ yelpazesi, nt düğümü V’nin i = 1, …, nt olarak etiketlendiği yönlendirilmiş bir grafik (V, E) biçimindeki bir mimariye dayanır. Örneğin, çok katmanlı algılayıcı aşağıdaki mimariye sahiptir. Kenar (i, j) ∈ E, düğüm i düğüm j’ye bağlanırsa vardır. Düğüm i, gerçek sayı xi ile etiketlenir ve kenar (i, j), gerçek değerli ağırlık wij ile etiketlenir.

Düğümler üç ayrı katmanda düzenlenir, ni düğümden oluşan bir girdi katmanı, nℎ düğümden oluşan bir gizli katman ve tek bir düğümden oluşan bir çıktı katmanı. Ağlar genellikle tam olarak bağlıdır, yani her girdi düğümü her gizli düğüme bağlıdır ve her gizli düğüm çıktı düğümüne bağlıdır. İsteğe bağlı olarak her girdi düğümü çıktı düğümüne bağlıdır (katman bağlantılarını atla), bunlar burada uygulanır. Başka hiçbir bağlantı türüne izin verilmez. Girdi ve gizli düğümler I ve H’yi ve girdi-gizli, gizli-çıktı ve girdi-çıktı kenarlarını sırasıyla IH, HO ve IO olarak belirtin. Gizli katman düğümleri için etiketler şu formülle verilir:

Burada ϕ(u) eşik fonksiyonudur (genellikle ϕ(u) = exp(u) / 1 + exp(u)).
Bu, girdi vektörü ile çıktı düğüm etiketi arasında bir ilişki oluşturur:

Bir girdi düğümü (0 etiketli önyargı düğümü) eklenir ve bu, 1 sabit girdisini kabul eder. ϕ dönüşümünün çıktı düğümüne uygulanmadığına dikkat edin. Gözetimli öğrenme uygulamasında olduğu gibi, YSA, esasen doğrusal olmayan bir regresyon modelinin parametreleri olarak işlev gören ağırlıkları belirlemek için eğitim verilerini kullanır.

Derin Sinir Ağları

Çok katmanlı algılayıcı (MLP), birçok yapay sinir ağının (ANN) temel özelliklerini yakalar. Derin bir sinir ağının tipik bir özelliği, mimarisinin birden fazla gizli katmanı desteklemesidir. Bunun değeri, aşağıdaki şekilde gösterildiği gibi Sec. u1.box.poker’deki otomatik poker uygulamasında kullanılabilecek bir ANN mimarisinin kısmi bir görünümünü düşünerek açıklanabilir. Bir çıktı düğümü ve iki gizli katman bulunmaktadır. Girdi katmanı, 52 oyun kartının her biri için bir düğüm içerir. Bu nedenle, girdi 5 kartlık bir poker elini temsil edebilir. Eğer elde ilgili kart varsa, her bir girdi düğümü 1 olarak ayarlanır (girdi katmanının yalnızca ilk 8 düğümü gösterilmiştir).

Derin öğrenmede amaç, özellik seçiminin ilk birkaç gizli katmana dahil edilmesidir. Aşağıdaki şekilde, ilk gizli katmanda her bir kart türü (maça, karo, kupa ve sinek) için ve her bir rütbe ile ilişkili ilk iki düğüm için (2, 3,…, 10, J, Q, K, A) düğümler olduğunu fark edin. Ayrıca, “maça” olarak etiketlenmiş gizli katman düğümünün yalnızca o türü temsil eden girdi düğümlerine bağlı olduğunu gözlemleyin. Bu nedenle, giriş elindeki “maça” türü kartların sayısını spesifik olarak depolayabilir. Benzer şekilde, “2 maça” olarak etiketlenmiş gizli katman düğümü, yalnızca o rütbeyi temsil eden girdi düğümlerine bağlıdır ve bu nedenle 2 rütbesine sahip kartların sayısını depolar.

Bu nedenle, önceki gizli katmanlar özellik seçimi (Sec. 1.1) işlevini yerine getirir ve elin temel özelliklerini kompakt bir biçimde yakalar. Bu bilgi daha sonra, değer fonksiyonunu yaklaşık olarak hesaplamak için ek gizli katmanlarda kullanılır. Bu yaklaşımın pekiştirmeli öğrenme için önemli bir avantajı, her durumu ziyaret etmeye gerek kalmadan değer fonksiyonunun iyi bir yaklaşık çözümüne ulaşılabilmesidir.

u1.box.poker bölümünün otomatik poker uygulaması için ANN mimarisi.

Özet

Bu yazıda, gözetimli öğrenme ve gözetimsiz öğrenme ile birlikte makine öğrenmesinin temel dallarından birini oluşturan pekiştirmeli öğrenme ile tanıştık. Pekiştirmeli öğrenmenin uygulama alanlarını, yöneylem araştırmasını ve yapay zekadaki birçok klasik kontrol problemini çözmek için uzun süredir kullanılan dinamik programlamadaki matematiksel temelleri öğrendik. Her iki yöntemin de amacı, ardışık karar süreçleri (SDP: Sequential Decision Processes) için optimal karar kurallarının (veya politikalarının) belirlenmesidir. Daha sonra pekiştirmeli öğrenme ve dinamik programlama karşılaştırılarak, pekiştirmeli öğrenme ve diğer makine öğrenme türlerinin aşabildiği klasik yöntemlerin bazı eksiklikleri vurgulandı.

Ajan ve ortamdan oluşan pekiştirmeli öğrenme platformu tanıtıldı. Ajan, belirli bir ortam için ödüllerin ajanın eylemlerine bağlı olduğu kontrollü bir deneme-yanılma süreciyle optimal karar kurallarını öğrenmekten sorumludur. Ortam, bir bilgisayar simülasyonu veya gerçek bir sistem olabilir. Yeterli öğrenmeden sonra bir politika bağımlı algoritma, optimal karar kurallarını uygular. Pekiştirmeli öğrenme ile ilişkili çeşitli teknikler gözden geçirildi. TD(λ), pekiştirmeli öğrenme platformunun belirli bir politika ile elde edilen ödülü değerlendirmek (politika değerlendirmesi) veya optimal kontrolü belirlemek için kullanılan Q-faktörleri tahmin etmek için kullanabileceği bir algoritma sınıfını ifade eder. Bu şekilde optimal kontrolü belirlemek için iki yöntem tanımlanmıştır: Q-öğrenme (politika bağımsız) ve SARSA (politika bağımlı). Optimal politika belirlemek için kullanılan politika yinelemesi (veya aktör-eleştirmen yöntemi) olarak bilinen alternatif bir yöntem de tanıtıldı.

Politika bağımlı pekiştirmeli öğrenme algoritmaları için keşif ve sömürü (exploration versus exploitation) arasındaki denge tartışıldı. Bu, ödülleri optimize etme zorunluluğunun (açgözlü veya sömürücü kontrol kullanarak) ajanın öncelikle optimal politikayı öğrenme ihtiyacıyla çeliştiği durumlarda ortaya çıkar. Öğrenme için gerekli olan keşif kontrolü, ödülleri optimize etme açısından neredeyse her zaman optimal değildir. Ancak, optimal politika belirlenene kadar ödüller optimize edilemez. Keşiften sömürüye kademeli bir geçişe izin veren bir dizi algoritma tanıtıldı (ϵ-açgözlü politikalar, E3 algoritması ve “R-max” algoritması bunlara örnek olarak verildi).

Son olarak, pekiştirmeli öğrenmede, özellikle yapay sinir ağları (YSA) gibi gözetimli öğrenme tekniklerinin kullanımı tartışıldı. Birçok SDP, bilgisayar belleğinde tablo biçiminde temsil edilemeyecek kadar büyük durum uzayları X oluşturur (örneğin, tavla oyununun yaklaşık 1²⁰ farklı durumu vardır). Dahası, bir pekiştirmeli öğrenme modeli deneyim yoluyla öğrendiğinden, büyük bir durum uzayı X’in yeterince keşfedilmesi pratik zorluklar yaratabilir. Yapay Sinir Ağları ve diğer yaklaştırma (approximation) yöntemleri, büyük durum uzayları tarafından dizinlenmiş tabloların kompakt temsillerini oluşturarak bu veri yapılarını uygulanabilir hale getirir. Ayrıca, derin sinir ağları gibi yeni yöntemler özellik seçimini otomatikleştirerek, daha verimli öğrenmeyi sağlamak için durum uzayının boyutunu azaltır.