Ödevsel

Takviyeli Öğrenme

12 Temmuz 2007

Takviyeli Öğrenme

Takviyeli öğrenme, kendi ortamında algılama ve hareket yapan bir özerk etmenin amacını gerçekleştirmek için en uygun hareketleri yapmayı nasıl öğrenebileceği sorusuna cevap verir. Bu çok genel problem, bir hareketli robotun kontrolü öğrenme, fabrikalardaki işlemleri optimize etmeyi öğrenme ve oyun oynamayı öğrenme gibi işleri kapsar. Etmen ortamında bir hareket yaptığı zaman, bir eğitici ortaya çıkan durumun istenilebilirliğini göstermek için bir ödül veya ceza sağlar. Mesela bir oyunu oynama etmeni eğitildiği zaman, eğitici oyun kazanıldığında pozitif bir ödül, kaybedildiğinde negatif bir ödül ve diğer durumlarda sıfır ödül sağlayabilir. Etmenin amacı, en büyük toplam ödülü üreten hareketlerin sırasını öğrenmektir.

Yukarıdaki amaca yönelik bir robotun inşa edilmesi istenirse, robot veya etmen, ortamının durumunu gözlemek için sensörlere ve bu durumu değiştirmek için de yapabileceği hareketlerin bir kümesine sahip olmalıdır. Örneğin hareketli robot, bir kamera veya sonarlar gibi sensörlere ve ileri git ve dön gibi hareketlere sahip olabilir. Onun görevi, amacını gerçekleştirecek hareketlerin seçimi için bir kontrol stratejisi veya politikasını öğrenmektir. Mesela, robotun batarya seviyesi ne zaman düşerse, kendi şarj edicisine gitme gibi bir amacı olabilir. Etmen amacı, etmenin her bir farklı durumdan çıkarabileceği her bir farklı harekete sayısal bir değer atayan (anlık ödül) bir ödül fonksiyonuyla tanımlanabilir. Örneğin, bir şarj ediciye yaklaşma amacı, şarj ediciye derhal bağlanma sonucunu doğuran durum-hareket geçişine pozitif bir ödül atanarak (100 gibi) sağlanabilir. Bu durumda diğer bütün durum-hareket geçişlerine sıfır ödülü atanır. Bu ödül fonksiyonu robot içinde inşa edilebilir veya sadece robot tarafından yapılan her bir harekete ödül veren harici bir öğretmen tarafından da bilinebilir. Robotun işi, sıralı hareketleri yapmak, onların sonuçlarını gözlemek ve kontrol politikasını öğrenmektir. İstenilen kontrol politikası, herhangi bir başlangıç durumundan etmen tarafından zamanla toplanılan ödülü maksimize eden hareketleri seçmektir. Robot öğrenmesi için bu genel ortam şekil 4.3’de gösterilmiştir.

Şekil 1: Ortamıyla etkileşen etmen.

Şekil 4.3’dan görüldüğü gibi, toplam ödülü maksimize etmek için bir kontrol politikasını öğrenme problemi çok geneldir ve robot öğrenme işleri ötesinde bir çok problemi kapsar. Problem genelde, süreçlerin sırasını bulmak ile uğraşır. Örneğin, üretim optimizasyon problemlerinde, öyle üretim hareketleri seçilmelidir ki maksimize edilecek ödül, üretilen malın satış değerinden mal olma maliyetinin çıkarılma değeridir. Başka bir örnek olarak da planlama problemleri gösterilebilir. Büyük bir şehirdeki yolculara hangi taksilerin gönderileceğini seçmede maksimize edilecek ödül, yolcuların bekleme zamanına ve hareket halinde iken taksilerin harcayacakları toplam benzin miktarına bağlıdır. Amaç, verilen bir hareketin sırasının kalitesini tanımlamaktır. İstenilen duruma erişmek için arama (search) yöntemini kullanan bir sistem her bir adımda alternatif hareketler arasından bir seçim yapar. Takviyeli öğrenmede ise hareketlerin belirsiz sonuçlar çıkarabileceği ve öğrenicinin kendi hareketlerinin sonuçlarını tanımlayan bir alan (domain) bilgisine sahip olmadığı göz önüne alınır. Takviyeli öğrenme ile yapılan uygulamaların belki de en tanınmışı Tesauro’nun (1995) TD-GAMMON oyun programıdır. Bu program birinci sınıf tavla oyuncusu olmak için takviyeli öğrenmeyi kullanmıştır.

Uygun hareketleri seçmek için bir kontrol politikasını öğrenme problemi, fonksiyon yaklaşım problemlerine benzerlik gösterir. Öğrenilmesi gereken hedef fonksiyon P: S ®A kontrol politikasıdır. Bir başka deyişle S kümesinden şu andaki s durumu verildikten sonra A kümesinden uygun bir hareket a’yı çıkarma politikasıdır. Bununla birlikte takviyeli öğrenme birkaç yönden diğer fonksiyon yaklaşım yöntemlerinden ayrılır (Mitchell, 1997).

1. Gecikmiş Ödül: Etmenin amacı, şu andaki s durumundan, optimal hareket a= P(s)’i planlayan bir hedef fonksiyon öğrenmektir. Diğer bir çok öğrenme yöntemlerinde P gibi bir hedef fonksiyon öğrenildiği zaman her bir eğitme örneği (s, P(s)) şeklindedir. Takviyeli öğrenmede ise eğitme bilgisi bu formda değildir. Bunun yerine eğitici; etmen hareketlerini yürütürken sadece anlık ödül değerlerin sırasını sağlar.

2. Kısmen Gözlenebilir Durumlar: Her ne kadar herhangi bir zaman adımında etmen sensörlerinin ortamın bütün durumunu algılayabildiğini kabul etmek uygun olsa da, bir çok pratiksel durumda sensörler yeterince bilgi sağlayamaz. Örneğin, sadece önünü görmeye yarayan kameraya sahip bir robot arkasında ne olduğunu idrak edemez. Böyle durumlarda hareketler seçildiği zaman şu andaki gözlemlerle birlikte öncekileri de dikkate almak etmen için gerekli olabilir.

3. Hayat Boyu Öğrenme: Birbirinden izole edilmiş fonksiyon yaklaşımından farklı olarak, robot öğrenme aynı sensörler kullanarak aynı ortamda birden fazla ilgili işi öğrenmeyi ihtiva edebilir. Örneğin, hareketli bir robotun aynı anda, şarj edicisine yaklaşma, dar koridorlar boyunca gezinme ve lazer yazıcıdan çıktıları toplama gibi öğrenme amaçları olabilir.

Öğrenme İşlemi

Sıralı kontrol yöntemlerini daha kesin bir ifadeyle formülize etmek için bir takım kabullerin yapılması gereklidir. Örneğin etmen hareketlerinin belirli veya belirsiz oldukları düşünülebilir. Aynı şekilde, etmen bir hareketden sonra meydana gelecek durumu tahmin edebilir. Diğer bir taraftan etmen, ona optimum hareketlerin sırasını gösteren bir uzman tarafından eğitilebilir veya hareketlerin seçimi tamamen etmene bırakılabilir.

Bu bölümde öncelikle Markov Karar Süreç (MDP) tabanlı problemlerin öğrenilmesi üzerinde durulmuştur. MDP’de bir etmen, ortamındaki farklı durumlar kümesi S’i algılayabilir ve yapabileceği A hareketlerinden birini uygulayabilir. Her bir ayrık zaman adımı t’de etmen şu andaki durum st ‘yi algılar ve ona uygun at hareketini yürütür. Ortam etmene anlık ödül rt=r (st , at )’ı vermekten ve bir sonraki durum st+1 = d(st, at )’yi üretmekten sorumludur. Burada d ve r fonksiyonları ortamın parçasıdır ve etmenin bilmesine gerek yoktur. Bir MDP’de d(st, at ) ve r (st , at ) fonksiyonları sadece şu andaki durum ve harekete bağlıdır, daha öncekilere bağlı değildir. Burada S ve A’nın sonlu bir kümeye sahip olduğu göz önüne alınmıştır.

Etmenin amacı, şu anda gözlenen durum st ‘ye göre bir sonraki at hareketini seçmek için P: S ®A politikasını, yani P( st )=at ‘ı öğrenmektir. P politikası etmenin zamanla en büyük toplam ödülü elde etmesiyle öğrenilebilir. Bunun için rasgele bir başlangıç durumu st’den rasgele bir politika takip edilerek elde edilen toplam ödül VP(st) ile tanımlanabilir. Bu durum aşağıda verilmiştir.

(1)

Burada ödüllerin sırası rt+i , st durumundan başlanarak ve yukarıda tanımlandığı gibi, yani at=P( st ), at+1=P( st+1 ) ile hareketleri seçmede kullanılan P politikası sayesinde üretilir. g ise 0

g < 1 arasında bir değer olup anlık ödüllere karşılık geciktirilmiş relatif değeri belirler. Özellikle gelecek i zaman adımında alınan ödüller gi faktörüyle üstel bir şekilde azaltılır. Eğer g=0 olursa, sadece anlık ödül göz önüne alınır. Eğer g bire yaklaşırsa geleceğin ödüllerine anlık ödüle göre daha büyük önem verilir.

VP(s), başlangıç durumu s’den bir P politikasıyla öğrenilen “azaltılmış toplam ödül” olarak adlandırılır. Gelecek ödülleri anlık ödüllere göre azaltmak mantıklıdır. Çünkü bir durumda daha sonrakinden ziyade daha yakın olan ödül tercih edilir. Bununla birlikte toplam ödülün başka tanımları da vardır. Örneğin, sonlu çevre ödülü;

,h adımı üzerinde azaltılmamış toplam ödülleri gösterir. Ortalama ödül ise;

etmenin bütün yaşamı üzerinde zaman adımı başına aldığı ödüldür.

Artık bundan sonra etmenin amacı bütün s durumları için toplam ödülü maksimize eden bir VP(s) politikası öğrenmektir. Bu politikaya “optimal politika” denir ve P* ile gösterilir.

(2)

Notasyonun basitleştirilmesi için böyle bir optimal politikanın değer fonsiyonu yerine, V*(s) kullanılır. V*(s) etmenin s durumundan başlayarak elde edebileceği maksimum azaltılmış toplam ödülü, yani s durumundan başlayıp optimal politika takip edilerek elde edilen azaltılmış toplam ödülü gösterir.

Bu kavramların daha iyi açıklanması için aşağıda bir örnek verilmiştir (grid-world ortamı). Şekil 4.4’ün en üstteki diyagramında 6 bölme, etmen için 6 mümkün durumu veya yeri temsil eder. Diyagramdaki her bir ok etmenin bir durumdan diğerine geçebileceği mümkün hareketi temsil eder. Her bir okla ilişkilendirilmiş sayı, etmenin ilgili durum-hareket geçişini yürütmesi durumunda alacağı anlık ödül r(s, a)’yı gösterir. Bu özel ortamda anlık ödül, G durumuna geçme dışındaki bütün durum-hareket geçişleri için sıfırdır. G amaç durumudur (goal state). Etmen G durumuna girdikten sonra yapabileceği tek hareket bu durumda kalmaktır. Bu nedenle G yutucu durum (absorbing state) olarak adlandırılabilir.

Durumlar, hareketler, anlık ödüller tanımlandıktan ve azalma faktörü g seçildikten sonra, optimal politika P* ve onun değer fonksiyonu V*(s) belirlenebilir. Örnek için g=0.9 olarak alınmıştır. Şekil 4.4’ün en altdaki diyagramı bu ortam için bir optimal politikayı gösterir, fakat bundan başka optimal politikalar da vardır. Tüm politikalar gibi optimal politika da etmenin herhangi bir durumda seçeceği her hereketi belirleyebilir. Aynı zamanda optimal politika, etmeni G duruma en kısa yoldan ulaştırır. Şeklin ortadaki diyagram her bir durum için V* değerlerini gösterir. Örneğin, bu diyagramda en alttaki sağ durum göz önüne alındığında bu durum için V* değeri 100’dür. Çünkü bu durumda optimal politika, 100 anlık değeri olan yukarıya git hareketini seçer. Bundan sonra etmen yutucu durumda kalacak ve herhangi bir ödül

Şekil 4.4: Ayrık durumlardan meydana gelen belirli bir etmen ortamı.

almayacaktır. Benzer şekilde en altdaki orta durum için V* değeri 90’dır. Çünkü optimal politika etmeni bu durumdan önce sağa (sıfır değerinde bir anlık ödül üreterek) sonra da yukarı doğru (100 anlık değeri üreterek) hareket ettirecektir. Böylece en alttaki orta durum için azaltılmış gelecek ödül;

dır.

Bu özel ortamda etmen yutucu durum G’ye ulaştıktan sonra onun sonsuz geleceği artık bu durumda kalmaktan ve sıfır ödüller almaktan ibarettir.

4.3.2 Q Öğrenme

Q Öğrenmenin amacı, rasgele bir ortam içinde etmene optimal politikayı nasıl öğrenebileceğini göstermektir. Fonksiyon P*:S®A ‘yı doğrudan öğrenmek zordur. Çünkü kullanılabilir eğitme verileri (s, a) formundaki eğitme örneklerini sağlamaz. Bunun yerine öğrenici için kullanılabilir eğitme bilgisi sadece anlık ödüller r(si, ai)’in sırasıdır. Bu çeşit eğitme bilgisi verildikten sonra, durumlar ve hareketlerin tanımladığı bir sayısal değerlendirme fonksiyonunu öğrenmek ve sonra bu değerlendirme fonksiyonuna göre optimal politikayı gerçekleştirmek daha kolaydır.

Birden fazla değerlendirme fonksiyonları içinde etmen V*’ı öğrenmeye çalışmalıdır. Örneğin, V*(s1) > V*(s2) ise etmen s2’nin yerine s1’i öğrenmeyi tercih etmelidir. Etmen politikası durumlar yerine hareketler arasında seçim yapmalıdır. s durumunda optimal hareket; anlık ödül r(s, a) ile g değeriyle azaltılmış V* ’nın toplamını maksimize eden a hareketidir. Yani;

(3)

d(s, a), s durumuna a hareketi uygulandıktan sonra meydana gelen durumu gösterir. Böylece etmen, eğer mükemmel bir anlık ödül fonksiyonu r ve durum geçiş fonksiyonu d bilgisine sahip ise V* ‘yı öğrenerek optimal politikayı kazanabilir. Yani etmen, hareketine cevap olarak ortam tarafından kullanılan r ve d fonksiyonlarını bilirse, herhangi bir s durumu için optimal hareketi (3) nolu denklemden hesaplayabilir. Fakat etmenin her durum-hareket geçişi için anlık sonuçları (anlık ödül ve sonraki durum) tahmin edebilmesi mümkün değildir. Bir başka deyişle; robot kontrolü gibi bir çok pratiksel problemlerde rasgele bir duruma rasgele hareket uygulayarak tam sonucu önceden tahmin etmek, etmen veya onun programcısı için mümkün değildir. d ve r’nin bilinmediği durumlarda etmen (3) nolu denklemi değerlendiremediğinden V* öğrenilemez.

4.3.2.1 Q fonksiyonu

Bir değerlendirme fonksiyonu Q(s, a) tanımlansın. Bu şekilde onun değeri s durumundan başlayarak ve ilk hareket olarak a‘yı uygulayarak başarılabilen maksimum azaltılmış toplam ödüldür. Diğer bir deyişle, Q’nun değeri; s durumunda a hareketi yürütülerek anlık olarak alınan ödül ile bundan sonraki durumun optimal politikayı takip etme değerinin g ile azaltılmış toplamıdır. Yani;

(4)

Q(s, a), s durumunda optimal hareket a’yı seçmek için (3)’deki denklemin maksimize edilen terimidir. Bundan dolayı (3) nolu denklem Q(s, a)’ya göre yeniden yazılabilir.

(5)

Bu denklem gösterir ki eğer etmen, V* fonksiyonu yerine Q fonksiyonunu öğrenirse r ve d fonksiyon bilgilerine sahip olmasa bile optimal hareketleri seçebilir. Bu denklem ile s durumunda sadece Q(s, a)’yı maksimize edecek a hareketleri göz önüne alınır. Q öğrenme algoritmasının olumlu bir yönü; şu andaki durum ve hareket için Q değeri, eğer s durumunda a hareketi seçilirse gelecekte azaltılmış toplam ödülü belirlemek için gerekli bütün bilgiyi tek bir sayıda toplayabilir. Bu durum şekil 4.4 deki örnekten de görülmektedir. Dikkat edilirse her bir durum hareket geçişleri için Q değerleri; r değeri ile V*’nın g ile azaltılmış değer toplamıdır. Ayrıca şekilde gösterilen optimal politika, maksimum Q değerli hareketleri seçmede de uygunluk gösterir.

4.3.2.2 Q Öğrenme için bir algoritma

Q fonksiyonunu öğrenme, optimal politikayı öğrenmeye benzer. Burada anahtar problem, sadece anlık ödüller r’nin zamanla sırası verildikten sonra Q’nun eğitme değerlerini belirleyen yolu bulmaktır. Bu iteratif bir yaklaşımla başarılabilir. Bunun için aşağıda Q ve V* arasında bir ilişki verilmiştir.

Bu durumda (4) nolu denklem yeniden yazılırsa;

(6)

Q’nun bu recursive tanımı iteratif olarak Q’ya yaklaşan algoritmaların temelini oluşturur (Watkins, 1989). Öğrenici, gerçek Q fonksiyonunu tahmin edebilmesi için sembolünü kullanır. Bu sembol bir anlamda öğrenicinin Q hakkındaki hipotezidir. , her bir durum hareket çifti için ayrı bir girişi olan tablo ile gösterilirse, her (s, a) çifti için tablo da değeri vardır. değeri öğrenicinin gerçek Q(s, a) değeri için şu andaki tahminini gösterir. Tablo başlangıç olarak rasgele değerlerle doldurulabilir. Fakat başlangıç değerleri olarak sıfır alınırsa algoritmayı anlamak daha kolay hale gelir.

Etmen şu andaki durum s’i sürekli olarak gözler, bir a hareketini seçer ve bu hareketi yürütür. Bu yapılırken ortaya çıkan ödül r=r(s, a) ve yeni durum sı =d(s, a)’i bir sonraki hareket için gözler. Daha sonra her bir geçiş için ’yı aşağıdaki eğitme kuralına göre güncelleştirir.

(7)

Bu eğitme kuralı her ne kadar değerini kullansa da (6) nolu denlemden çıkarılmıştır. (6) nolu denklemde Q, d(s, a) ve r(s, a)’ye göre tanımlansa da (7) deki denklemde eğitme kuralının bu fonksiyonları bilmesine gerek yoktur. Bunun yerine etmen ortamındaki hareketi yürüttükten sonra meydana gelen yeni durum sı ve r ödülünü gözler ve daha sonra buna göre hareket eder. Aşağıdaki tabloda belirli bir Markov karar süreci (MDP) için Q öğrenme algoritması verilmiştir. Bu algoritma kullanılarak etmenin tahmini ’su sonuçta gerçek Q fonksiyonuna yaklaşır.

Her bir s, a için ’yı sıfıra ata.

Şu andaki s durumunu gözle

Öğrenme gerçekleşinceye kadar tekrarla:

Bir a hareketini seç ve onu yürüt,

Anlık ödül r’yi al,

Yeni durum s’nü gözle,

değerini yandaki kurala göre güncelleştir:

s¬sı

Tablo 4.1: Belirli durum ve hareketleri kabul eden Q öğrenme algoritması.

4.3.2.3 Bir açıklayıcı örnek

Q öğrenme algoritmasının çalışmasını anlamak için aşağıda bir örnek verilmiştir. Bu örnekte etmen ızgara dünyasında bir hücre sağa doğru hareket eder ve bu geçiş için sıfır anlık ödülü alır. Sonra, henüz yürütülen durum-hareket geçişi için tahmini , (7) nolu denklemdeki eğitme kuralına göre hesaplanır. Eğitme kuralına göre bu geçiş için yeni tahmini, alınan anlık ödül (sıfır) ile sonraki durumun en yüksek ’sunun g (0.9) ile azaltılmış değerinin toplamıdır. Şekil 4.5 de gösterilen bu ortamın anlık ödül değerleri ise şekil 4.4’deki gibi kabul edilsin. Bu durumda anlık ödül, amaç duruma girilmesi haricinde her yerde sıfırdır. Bu ortam yutucu bir durum içerdiğinden dolayı eğitme bölümlerden (episodes) ibaret olarak kabul edilebilir. Her bir bölüm boyunca etmen rasgele seçilen bir durumdan başlar ve yutucu duruma ulaşıncaya kadar hareketlerin yürütülmesine müsade edilir. Amaç duruma ulaşıldığı zaman bölüm sonlanır ve etmen bir sonraki bölüm için rasgele seçilen yeni bir başlangıç duruma aktarılır.

Q öğrenme algoritması sıfır ile yüklenmiş bütün değerlerinde, etmen amaç duruma erişinceye kadar veya sıfır olmayan bir ödül alana kadar tablo girişi için herhangi bir değişiklik yapmayacaktır. Fakat amaç durumdan bir önceki durum için değeri artık sıfırdan farklı olacaktır. Bir sonraki bölümde ise eğer etmen amaç duruma komşu olan duruma geçerse aynı şekilde bu durum için sıfırdan farklı bir değeri elde edilmiş olur. Algoritma bu şekilde

Şekil 4.5: Bir hareket yürütüldükten sonra değerinin güncelleştirilmesi

bölümlerin istenilen değere kadar ilerledikten sonra, etmen bütün durum hareket geçişleri

için sıfırdan farklı değerleri üretecektir. Örnek olarak şekil 4.5’de s1 ‘den s2 duruma asağ hareketi uygulanırsa aşağıdaki değeri elde edilir.

Sonuç olarak da şekil 4.4 de gösterilen Q değerlerini içeren tablosu elde edilir. Sonraki bölümde de görüleceği gibi belirli kabuller altında tablo 4’de ifade edilen Q öğrenme algoritması Q fonksiyonuna yaklaşacaktır. Eğer Q öğrenme algoritması ödülleri negatifden farklı belirli bir MDP için uygulanacak olursa ve başlangıçta bütün değerlerine sıfır değeri atanacak olursa iki önemli özellik ortaya çıkar. Bunlardan biri; değerleri eğitme boyunca asla azalmaz. Yani; , eğitme prosedürünün n.’inci iterasyonundan sonraki öğrenilen değeri olarak kabul edilirse (yani etmen tarafından yapılan n.’inci durum hareket geçişinden sonra) o zaman;

dir.

İkinci bir özellik ise bütün yer değiştirme sürecine her değeri, sıfır ile Q değeri arasındadır. Yani;

dir.

4.3.2.4 Yakınsama

Tablo 4’deki algoritma ile gerçek Q fonksiyonuna eşit ’ya doğru bir yakınsamanın sağlanabilmesi için belirli şartların kabul edilmesi gerekir. Bu kabullerden biri sistemin belirli MDP’ye sahip olduğu, ikincisi bütün durum ve hareketler için anlık ödüllerin var olduğu (

r(s, a)

< c olmak üzere) ve üçüncüsü ise etmenin her mümkün durum hareket çiftini sonsuz bir şekilde sık ziyaret ettiğidir. Bu üçüncü kabul, eğer a hareketi s durumu için geçerli bir hareket ise, o zaman etmenin a hareketini s durumundan tekrarlı bir şekilde yürütebileceğini ifade eder. Bu şartlar bazı durumlarda genel bazılarında ise oldukça sınırlı olabilir. Öyle ki daha önce verilen örnekten daha genel ortamlar tanımlanabilir. Bu genel ortamlarda ödüllerin değeri pozitif ve negatif olabileceği gibi sıfırdan farklı ödül üreten birden fazla durum hareket geçişi de olabilir. Etmenin sonsuz şekilde sık durum hareket geçişine maruz kalma şartları sınırlıdır. Bu ancak geniş alanlarda kabul edilen bir yaklaşımdır. Yakınsamanın temelini teşkil eden anahtar fikir, en büyük hatalı ne zaman güncelleştirilirse, bir önceki değerinden g kadar azaltılmış bir hataya sahip olur.

Teorem 1: Belirli bir MDP için Q öğrenmenin yakınsaması.

ödülleriyle sınırlandırılmış belirli bir MDP’de Q öğrenme algoritmasının kullanıldığı farz edilsin. Q öğrenme algoritması (7) nolu eğitme kuralını kullanır. tablosu ise başlangıç olarak keyfi sonlu değerler ile yüklensin. , ’in n.’inci güncelleştirilmiş durumunu gösterirken; eğer her bir durum hareket çifti sonsuz şekilde sık ziyaret edilirse, o zaman , n®¥ iken bütün s ve a için ’ya yaklaşır.

İspatı: Her biri durum hareket geçişi sonsuz şekilde sık meydana geldiğinden, bu geçişin en az bir defa meydana geldiği ardışık taramalar göz önüne alınsın. tablosundaki bütün girişlerin maksimum hatası her aralık boyunca en az g faktörüyle azaltılır (0

g<1). , n.’inci güncelleştirmeden sonra tahmin edilen Q değeridir. Dn, ’de maksimum hata olsun. Yani;

d(s, a) yerine sı kullanarak, n+1 iterasyon üzerinde güncelleştirilecek tablo girişi için düzeltilen deki hata bulunmak istenirse;

Yukarıdaki ikinci ve üçüncü satır arasındaki ilişki aşağıdaki gibidir.

Üçüncü satırdan dördüncü satıra geçildiğinde ise yeni bir sıı değişkeni tanımlanmıştır. Bu değişken sayesinde Dn’in tanımına uygun bir ifade elde edilebilir. Böylece herhangi bir (s, a) için güncelleştirilen , tablosunda maksimum hata Dn’in en fazla g katıdır. Başlangıç tablosundaki en geniş hata D0 ile gösterilirse, bütün (s, a)’ların ziyaret edildiği birinci taramadan sonra tablodaki en geniş hata g D0 olacaktır. Bu şekilde k’ıncı taramadan sonra hata en fazla gk D0 olur. Her bir durum sonsuz bir şekilde sık ziyaret edildiğinden, n®¥ iken tarama sayısı sonsuz ve Dn®0’dır.

4.3.2.5 Deneysel stratejiler

Dikkat edilirse tablo 4’deki algoritma, hareketlerin etmen tarafından nasıl seçildiğini belirlemez. Bunun için gerekli olan strateji, etmen için güncel yaklaşım ’yu kullanmak suretiyle ’yı maksimize eden s durumunda a hareketini seçmektir. Bununla birlikte bu strateji ile etmen, daha yüksek değerli diğer hareketleri keşfetmede başarısız iken yüksek değerlerine sahip olmak için ilk eğitme sırasında bulunan hareketleri sürekli olarak işleme riskini alır. Gerçekde yukarıdaki yakınsama teoremi, her bir durum hareket geçişinin sonsuz şekilde sık meydana gelmesine bağlıdır. Eğer etmen daima şu andaki ’yı maksimize eden hareketleri seçerse, açıkca bu durum meydana gelmez. Bu nedenle hareketleri seçmede bir olasılık yaklaşımı kullanmak Q öğrenmede esasdır. Daha yüksek değerlikli hareketler daha yüksek olasılıklara atanır. Fakat her hareketin de sıfırdan farklı bir olasılığı vardır. Her bir hareketin olasılığı aşağıdaki formülle ifade edilebilir.

Burada P(ai

s), etmen s durumunda iken ai hareketini seçme olasılığıdır. k (k >0) yüksek değerli hareketi onaylayan seçimin ne kadar güçlü olduğunu belirleyen bir sabittir. k’nın daha büyük değeri ’nun ortalaması üzerindeki hareketlere daha yüksek olasılık atar. Etmenin öğrendiğini kullanma ve inandığı hareketleri arama ödülünü maksimize eder. Bunun aksine küçük k değerleri diğer hareketlere daha yüksek olasılık verir. Etmenin şu anda yüksek değerlerine sahip olmayan hareketleri keşfetmesine imkan sağlar. Bazı durumlarda k iterasyon sayısıyla değiştirilir. Böylece etmen öğrenmenin ilk safhaları boyunca keşfetme amaçlıdır, daha sonra derece derece kullanma stratejisine doğru kayar.

4.3.3 Belirsiz Ödüller ve Hareketler

Şimdiye kadar Q öğrenme hep belirli ortamlar için göz önüne alındı. Burada ise belirsiz durumlar ele alınacaktır. Ödül fonksiyonu r(s, a) ve hareket geçiş fonksiyonu d(s, a) olasılık sonuçlarına sahip olabilir. Örneğin, Tesauro’nun (1995) tavla oynama programında, hareket sonuçları doğal şekilde olasılıklıdır. Çünkü herbir hareket, bir çift zarın yuvarlanmasını içerir. Benzer biçimde gürültü sensörlü ve effektörlü robot problemlerinde hareket ve ödülleri belirsiz olarak modellemek çoğu zaman uygundur. Böyle durumlarda d(s, a) ve r(s, a) fonksiyonlarına önce s ve a’ya dayandırılmış sonuçlar üzerinde bir olasılık dağılımı üretmek ve sonra bu dağılımdan bir sonuç çıkartmak gerekir. Bu olasılık dağılımları sadece s ve a’ya bağımlı (yani önceki durum ve harekete bağlı değillerdir) olurlarsa, böyle sistemler belirsiz Markov karar süreçleri (MDP) olarak adlandırılırlar.

Belirsiz durumlarda, hareketlerin sonuçları artık belirli değildir gerçeği göz önüne alınarak öğrenicinin amacı yeniden ifade edilmelidir. P politikası takip edilerek elde edilen azaltılmış toplam ödülün beklenti değeri (belirsiz sonuçlar için) aşağıdaki gibi ifade edilebilir.

Burada rt+i ödüllerinin sırası s durumundan başlayıp P politikası takip edilerek üretilir. Dikkat edilirse bu (1) nolu denklemin genelleştirilmiş halidir. Daha önceki gibi optimal politika P*, bütün s durumları için VP(s)’i maksimize eden P politikası olarak tanımlanır. (4) nolu denklemin beklenti değeri alınarak, Q tekrar ifade edilmek istenirse;

(8)

Burada P(sı

s, a), s durumunda a hareketi uygulanarak sı durumunu üretme olasılığıdır. Buradan Q aşağıdaki gibi recursive olarak tekrar yazılabilir.

(9)

Bu denklem (6) nolu denklemin genelleştirilmiş halidir. Daha önce belirli durum için çıkartılan eğitme kuralı, belirsiz ortamın yakınsamasında başarısız kalır. Örneğin, (s, a) geçişinin tekrarlandığı her bir zaman farklı ödüller üreten bir belirsiz ödül fonksiyonu r(s, a) göz önüne alındığında, eğitme kuralı; tablo değerlerini uygun Q fonksiyonuyla yüklese bile değerlerini sürekli olarak değiştirecektir. Kısaca bu eğitme kuralı yakınsama sağlamayacaktır. Bu zorluğun üstesinden eğitme kuralı değiştirilerek gelinebilir. Düzeltilmiş eğitme kuralı, ’nun Q’ya yakınsamasını temin etmede yeterlidir.

(10)

Burada; dir. (11)

s ve a n’inci iterasyon boyunca güncelleştirilen durum ve hareketlerdir. visitsn(s, a) ise n’inci iterasyonu da içeren durum hareket çiftinin ziyaret edilme sayısıdır. Düzeltilmiş kuralda anahtar fikir, revizyonlarının belirli durumdan daha derecesel olarak yapıldığıdır.

Eğer an 1’e set edilirse, belirli durum için eğitme kuralı elde edilir. an değeri, n artar iken düşer. Böylece güncellemeler, eğitme ilerlerken daha küçük olur. Eğitme boyunca uygun bir oranda an azaltılarak Q fonksiyonuna yakınsama sağlanabilir. Yukarıda verilen an’in seçimi Watkins ve Dayan’ın (1992) aşağıdaki teoremine göre yakınsama şartlarını sağlayan yöntemlerinden biridir.

Teorem 2: Belirsiz bir MDP için Q öğrenmenin yakınsaması.

ödülleriyle sınırlandırılmış belirsiz bir MDP’de Q öğrenme algoritmasının kullanıldığı farz edilsin. Q öğrenme algoritması (10) nolu eğitme kuralını kullanır. tablosu ise başlangıç olarak keyfi sonlu değerler ile yüklensin ve azalma faktörü de 0

g<1 olsun. n(i, s, a), a hareketinin s durumuna i defa uygulanma sayısını da gösteren bir iterasyon bilgisi olsun.

Eğer her bir durum hareket çifti sonsuz şekilde sık ziyaret edilirse, 0

an <1 ve;

ise,

o zaman n®¥ iken 1 olasılıkla dir.

Kategori: EÄŸitim