g u t x .com.tr İpek yolu - Çin'i anlamaya götürürüm

Pekiştirmeli öğrenmede her yerde bulunan Bellman optimallik denkleminin arkasındaki matematiksel ilke nedir?

Yazar | Vaibhav Kumar

Derleme | Ashburn Fei

Düzenle | Kongun Sonu

StarCraft ve Go gibi oyunlarda, pekiştirmeli öğrenme dünyaca ünlü bir başarıya ulaştı. Bu başarıların arkasındaki temel, Markov Karar Sürecini (MDP) çözmek için kullanılan Bellman Optimality Equation'dur.

Bellman denkleminin pekiştirmeli öğrenmede her yerde olduğu söylenebilir ve bu denklemin matematiksel temelini anlamak, RL algoritmasının çalışma prensibini anlamak için gereklidir. Markov karar sürecini çözmek için Amerikalı uygulamalı matematikçi Richard Bellman (Richard Bellman) tarafından önerildi.

Veri Bilimine Doğru blog yazarı Vaibhav Kumar, bu makalede matematiksel titizliği kaybetmeden anlaşılması kolay olan bu denklemin ardındaki matematiksel temele ayrıntılı bir giriş yaptı.

İyi makaleler takdir edilir, aşağıdaki tercüme edilmiş orijinal metinler sizinle paylaşılır:

AlphaStar ve AlphaGO oyunlarında, pekiştirmeli öğrenme dünyaca ünlü bir başarıya ulaştı. Bu başarıların arkasındaki temel, Markov karar süreçlerini (MDP) çözmek için kullanılan Bellman optimallik denklemidir.

Bellman Optimality Denklemi

Bellman optimallik denklemi, dinamik programlama (DP) algoritması ile çözülebilen özyinelemeli bir denklemdir.Bu denklemi çözerek, optimal değer fonksiyonu ve optimal strateji bulunabilir.

1. Bu makaleye dahil edilecek matematiksel semboller

S durum uzayı anlamına gelir
V değer işlevini temsil eder
V *, optimum değer işlevini temsil eder
V (s), durum s olduğunda değer fonksiyonunun değerini temsil eder
strateji anlamına gelir
* en uygun stratejiyi temsil eder
(s), durum s olduğunda strateji tarafından gerçekleştirilen eylemi döndürür
P, geçiş olasılığı matrisini temsil eder
A, olası tüm eylemler kümesini temsil eder

2. Ön bilgi

Makalenin anlaşılmasını kolaylaştırmak için elimden gelenin en iyisini yapmaya çalışsam, ancak uzunluğu ile sınırlı ve aynı zamanda analizin titizliğini sağlamak için hala okuyucunun aşağıdaki ön koşullara sahip olduğunu varsayıyorum:

Markov Karar Süreci (MDP)
Bellman denklemi ve bu denklemi çözmek için yinelemeli yöntemin nasıl kullanılacağı
RL temeli, değer fonksiyonu, ödül, strateji, indirim faktörü vb. Kavramlar
Lineer Cebir
Vektör türetme

Üç, Bellman denkleminin ana noktalarını anlamak için

RL ve MDP hakkında biraz araştırma yaptıysanız, böyle bir ifadeyle karşılaşmış olmalısınız: "Her MDP için, her zaman diğer tüm stratejilerden daha iyi veya eşit olan en az bir strateji vardır."

Sutton ve Barto'nun klasik ders kitaplarında ve David Silver'ın ders serilerinde bu ifadeleri okumak veya duymak çok sezgisel ve apaçık görünüyor. Bununla birlikte, daha derinlemesine çalışmalı ve bunun neden daha spesifik bir şekilde söylendiğini anlamalıyız (tabii ki, yazar matematiksel olarak özeldir, ancak sezgisel olarak sezgiseldir). Bu nedenle bu yazımda aşağıdaki teoremleri matematiksel olarak ispatlayacağım:

Herhangi bir sınırlı MDP için optimal bir strateji vardır * ve diğer tüm olası stratejiler bu stratejiden daha iyi olmayacaktır.

En iyi stratejiyi aramadan önce, strateji dizisini anlamamız gerekir. Yani, bir stratejinin (1) başka bir stratejiden (2) daha iyi olduğunu ne zaman düşünürüz?

Durum uzayındaki her durum için, bu durumda 1 kullanılarak türetilen değer fonksiyonunun değeri, bu durumda 2 kullanılarak türetilen değer fonksiyonunun değerinden büyük veya ona eşitse, o zaman 1 stratejisinin 2 stratejisinden daha iyi olduğu söylenebilir. Matematiksel olarak şu şekilde yazılabilir:

Stratejiler arasında karşılaştırma

Artık stratejileri nasıl karşılaştıracağımızı bildiğimize göre, her zaman diğer tüm stratejilerden daha iyi bir strateji olduğunu kanıtlamamız gerekiyor. Bellman optimal operatörünün L-sonsuz norm metriğiyle gerçek sayıların tam metrik uzayında kapalı bir eşleme olduğunu kanıtlayarak bu noktayı kanıtlamak için Banach'ın sabit nokta teoremini kullanacağız. Bu nedenle, önce sabit nokta probleminden ve Cauchy dizisinin tam metrik uzayından bahsediyoruz.

Son paragraf korkutucu gelebilir, ancak her temel terimin anlamını anladığımızda, çok kolay ve sezgisel hale gelecektir. Bu yüzden korkmayın! Kalın yazılmış terimleri üst paragrafta tek tek tartışacağız. Korkularımızın üstesinden gelelim ve her kavramı aşağıdan yukarıya bir yaklaşımla öğrenelim:

1. Sabit nokta sorunu

Çoğumuzun denklemlerin köklerini bulma sorununa aşina olduğuna inanıyorum. F (x) = 0 fonksiyonunun olduğu x noktasını buluruz. Sabit nokta probleminde, x noktasını f (x) = x olacak şekilde çözeriz.

Adından da anlaşılacağı gibi, x noktası sabit bir noktadır, yani f (x) fonksiyonu ona uygulansa bile değeri değişmeyecektir. Başka bir g (x) = f (x) -x = 0 fonksiyonu oluşturarak, sabit nokta problemi bir denklemin köklerini bulma problemine dönüştürülebilir.

Aslında, bir denklemin kökünü bulma sorunu, aynı zamanda sabit bir nokta bulma sorununa da dönüştürülebilir. Ancak (belirli koşullar altında) sabit nokta problemini çözmek daha kolaydır, bu da sabit nokta problemini çok ilginç ve kullanışlı hale getirir (hesaplama yükünden tasarruf sağlar).

Sabit nokta problemini çözmek için, başlangıç değeri olarak rastgele bir x seçin ve f (x) 'i sonsuz bir şekilde tekrar tekrar uygulayın. "Fonksiyon yakınsak" ise, sabit nokta problemine bir çözüm bulacaksınız.

Matematiksel olarak konuşursak, bu çok basit, önce bir notasyon sunalım:

Fn (x) notasyonu, fonksiyonun x noktasında sürekli olarak n kez uygulanması anlamına gelir.

Şimdi, eğer işlev yakınsaksa, belirli bir değere, örneğin x * 'e yakınsaması gerekir. Aşağıdaki argüman, bu x * değerinin gerçekten de sabit nokta probleminin çözümü olduğunu göstermektir:

Rasgele bir x0 değeri seçelim ve f (.) Fonksiyonunu x * elde etmek için sonsuza kadar uygulayalım ve ardından aşağıdaki şekilde gösterildiği gibi sabit nokta problemini çözmek için kullanalım:

Sabit nokta problemlerini çözün

Bunun arkasındaki önsezi basittir, eğer bir fonksiyon belirli bir noktada birleşirse, o yakınsama noktasındaki fonksiyonun değeri yakınsama noktasının kendisidir. Bu nedenle, bu yakınsama noktası sabit noktadır.

Aşağıdaki kod aracılığıyla fonksiyonun sabit bir noktaya yakınsadığı deneyimlerden de gözlemlenebilir, kod bağlantısı aşağıdaki gibidir:

https://gist.github.com/TimeTraveller-San/8e37399d4740928a258f395413bde2e7/raw/c48fecd50fa29634eea144917f92787c3ccd7bf3/Fixed%20point%20problem.ipynb

2. Metrik uzay

Bir metrik uzay yalnızca bir metriğin tanımlandığı bir koleksiyondur ve bir metrik, koleksiyondaki herhangi iki öğe arasındaki mesafeyi tanımlar. Örneğin, Öklid uzayı bir metrik uzaydır ve mesafesi Öklid mesafesi olarak tanımlanır. Bu nedenle, metrik uzay M (X, d) olarak ifade edilebilir, burada X bir küme ve d bir metriktir. Bir metrik d aşağıdaki dört özelliği karşılamalıdır:

Birlik: d (x, x) = 0
Negatif olmama: d (x, y) > 0
Simetri: d (x, y) = d (y, x)
Üçgen eşitsizliği: d (x, z) d (x, y) + d (y, x)

3. Cauchy dizisi

Metrik uzay (X, d) için, X (x1, x2, x3 .... xn) kümesindeki elemanların dizisi Cauchy dizisidir, eğer herhangi bir pozitif gerçek sayı için, aşağıdaki denklemin olduğu şekilde bir N tamsayısı vardır Kurulmuş:

Cauchy dizisi

Buradaki matematiksel açıklama biraz karmaşıktır ve yeterince sezgisel değildir (ancak gerçek tanım böyledir). Basit bir deyişle, metrik uzay elemanları dizisi belirli bir noktada birleşiyorsa (belirli bir noktaya sonsuz derecede yakınsa), bu dizi Cauchy dizisidir.

4. Metrik Boşluğu Tamamlayın

X kümesindeki öğelerden oluşan olası her Cauchy dizisi, X kümesindeki öğelere yakınlaşırsa, metrik uzay (X, d) tamamlanır. Başka bir deyişle, set öğelerinden oluşan her Cauchy dizisinin sınırına karşılık gelen öğeler de kümeye aittir, bu nedenle buna "tam" denir.