Bölüm 13: Öğrenme ve Adaptasyon

13.1Giriş

Denge analizi oyunları çoğunlukla “dışarıdan” çözer: kazanç matrisi verilir, denge hesaplanır ve oyuncuların o dengeyi oynayacağı kabul edilir. Bu bölümde bakış açısı değişir. Oyuncuların kendisi bir algoritmadır. Her turda bir eylem seçer, sonucu gözler ve kuralını günceller. Soru artık “denge nedir?” değil, “bu güncelleme kuralı uzun vadede nereye gider?” sorusudur.

13.1.1Bir oyunla başlangıç: çok kollu haydut

Bölümün açılış oyunu bir kumar makinesidir. Makinenin üç kolu vardır. Her kol, gizli bir olasılıkla 1 puan verir, yoksa 0 verir. Bir kolu çekince yalnızca o kolun sonucu görülür; öteki kolların o turda ne vereceği öğrenilemez. Amaç, belirli sayıda çekişte toplam ödülü en büyük yapmaktır. İngilizcede tek kollu kumar makinesine “tek kollu haydut” denir; bu yüzden birden çok kolu olan probleme çok kollu haydut (multi-armed bandit) adı verilir.

Şekil 13.1'de sekiz çekişten sonraki durum görülür. Kol 1'in gözlenen ortalaması 2/3 ≈ 0,67 ile en yüksektir. Kol 3 ise tek denemede başarısız olmuştur. İki makul düşünce çatışır. Birincisine göre en iyi görünen kol Kol 1'dir ve kalan çekişler ona harcanmalıdır. İkincisine göre Kol 3 hakkında neredeyse hiçbir şey bilinmemektedir; gerçek olasılığı yüksek olsa bile tek bir başarısız deneme şaşırtıcı değildir. Kol 3'ü yeniden denemek bilgi kazandırır, ama bu çekiş o anki en iyi tahminden vazgeçmek demektir.

Bu gerilimin adı keşif–sömürü ikilemidir (exploration–exploitation). Keşif, az bilinen seçenekleri bilgi toplamak için denemektir. Sömürü, o ana kadar en iyi görünen seçeneği kullanmaktır. Yalnızca sömüren bir oyuncu yanlış kola takılabilir; yalnızca keşfeden bir oyuncu ise öğrendiğini hiç kullanmaz. Örneğin yüz çekişlik bir oyunda kaç çekişin keşfe ayrılacağı sorusunun tek bir doğru cevabı yoktur; cevap kolların ne kadar farklı olduğuna ve oyunun ne kadar süreceğine bağlıdır. Bölümün ortasında bu soruya iki algoritmayla (ε-açgözlü ve UCB1) sayısal cevaplar verilir ve açılıştaki durum yeniden ele alınır.

13.1.2Neden öğrenme ve adaptasyon?

Önce iki terimi ayıralım. Öğrenme, geçmiş deneyimden bir strateji geliştirmektir. Adaptasyon (uyum), rakip ya da çevre değişince stratejiyi güncellemektir. İkisi çoğu zaman birlikte görülür: bir teklif algoritması dünkü açık artırmalardan öğrenir, bugün rakipler değişince yeniden uyum sağlar.

Şekil 13.2 bu bölümdeki bütün algoritmaların ortak iskeletini gösterir. Algoritmalar yalnız iki noktada ayrılır: neyi gözledikleri ve gözlemi nasıl kullandıkları. Bu iskeletin neden gerekli olduğunu üç gözlem açıklar.

1. Denge hesaplamak zor olabilir. Genel oyunlarda karışık Nash dengesini bulmak PPAD-tam bir problemdir. PPAD-tam, büyük oyunlarda hızlı (çok terimli zamanlı) bir çözüm yolu bilinmeyen bir problem sınıfıdır. Bilgisayarlar bile dengeyi hızlı bulamıyorsa, oyuncuların dengeyi kafadan hesapladığını varsaymak zordur. O hâlde oyuncular dengeyi nasıl “bulur”?
2. Oyuncular oyunu bilmiyor olabilir. Kazanç matrisi çoğu zaman bilinmez. Bir reklamveren, rakiplerinin değerlemelerini görmez; bir sürücü, öteki sürücülerin rota seçimlerini görmez. Oyuncu yalnızca oynayıp sonucu görür.
3. Asıl soru basit kuralların gücüdür. Basit, yerel güncelleme kuralları uzun vadede dengeye, ya da en azından iyi bir performansa götürür mü? Bu bölüm bu soruya sınıf sınıf cevap verir: bazı kurallar bazı oyunlarda dengeye gider, bazıları döner, bazıları dengeye gitmese bile “pişmanlıksız” olur.

Örnekler günlük hayattan tanıdıktır. Satranç ve poker yapay zekâları kendilerine karşı milyonlarca oyun oynayarak öğrenir. Reklam açık artırmalarındaki teklif algoritmaları her gün sonuçlara bakıp tekliflerini ayarlar. Navigasyon uygulamaları trafiğe göre rota değiştirir; her sürücünün rotası öteki sürücülerin trafiğini etkilediği için bu da bir oyundur.

13.1.3Öğrenme modellerine genel bakış

Bölümde altı öğrenme modeli incelenir. Tablo 13.1 bunları iki soruya göre karşılaştırır: oyuncu neyi gözler ve nasıl günceller?

Tablo yukarıdan aşağı okunduğunda bir eğilim görülür. İlk iki modelde oyuncu rakibi izler: rakibin ne oynadığını bilir ve buna göre en iyi tepkiyi hesaplar. Bunun için oyuncunun kendi kazanç tablosunu bilmesi gerekir. Hedge'de oyuncu rakibi değil, kendi eylemlerinin kazancını izler; rakibin ne yaptığını bilmesine gerek kalmaz. Haydut ve Q-öğrenmede bilgi daha da azalır: yalnızca seçilen eylemin ödülü görülür. Son satırda ise bakış bireyden nüfusa kayar; tek bir oyuncunun “düşünmesi” yoktur, başarılı davranış çoğalır.

Modeller arasındaki bir başka fark, tam geri bildirim ile kısmi geri bildirim ayrımıdır. Tam geri bildirimde oyuncu, oynamadığı eylemlerin de o turda ne kazandıracağını öğrenir. Örneğin bir yatırımcı hangi hisseyi alırsa alsın akşam bütün hisselerin getirisini görür. Kısmi geri bildirimde yalnızca seçilen eylemin sonucu görülür. Örneğin bir hekim bir hastaya bir ilacı verdiğinde öteki ilacın o hastada ne yapacağını hiçbir zaman öğrenemez. Hedge tam geri bildirim için, haydut algoritmaları kısmi geri bildirim için tasarlanmıştır; keşif gereksinimi bu farktan doğar.

13.2En iyi tepki ve kurgusal oyun

En basit öğrenme kuralları, Nash dengesinin tanımından doğrudan çıkar. Nash dengesi, her oyuncunun ötekilerin seçimine en iyi tepki verdiği profildir. O hâlde oyuncular sırayla en iyi tepki verirse, bir noktada herkesin en iyi tepki verdiği bir profile, yani dengeye varılabilir. Bu bölümde bu fikrin ne zaman işlediği, ne zaman döngüye girdiği ve döngünün geçmişi hatırlayarak nasıl kırılabildiği incelenir.

Bir ön bilgiyi hatırlatalım. Oyuncu i'nin, ötekilerin s_−i seçimine en iyi tepkisi (best response), kazancını en yüksek yapan stratejidir: BR_i(s_−i) = argmax_si u_i(s_i, s_−i). İki kişilik bir matris oyununda satır oyuncusunun en iyi tepkisi, rakibin sütununda ilk sayıların en büyüğünü veren satırdır; sütun oyuncusunun en iyi tepkisi, rakibin satırında ikinci sayıların en büyüğünü veren sütundur. Bir profil, iki oyuncu da birbirine en iyi tepki veriyorsa Nash dengesidir.

13.2.1En iyi tepki dinamiği adım adım

Dinamik durduğu anda her oyuncu ötekilerin eylemine en iyi tepki vermektedir; bu, Nash dengesinin tanımıdır. Demek ki en iyi tepki dinamiği durursa bir saf Nash dengesinde durur. Asıl soru, dinamiğin durup durmadığıdır. Önce durduğu bir örneğe bakalım.

Şekil 13.3'te okların her biri tek bir oyuncunun değişimidir. Dikey oklar satır oyuncusunun (yalnız satır değişir, sütun sabit), yatay oklar sütun oyuncusunun hamlesidir. Örnek iki önemli gözlem verir. Birincisi, dinamik bir dengede durdu; her adımda yalnızca bir oyuncunun yerel bir hesap yapması yetti, kimse dengeyi “çözmedi”. İkincisi, hangi dengeye varıldığı başlangıca bağlıdır. Birden çok denge olan oyunlarda öğrenme kuralı, bir denge seçim mekanizması gibi çalışır: (B, Z)'den başlayan nüfus (A, X)'e, (C, Y)'den başlayan nüfus (B, Y)'ye yerleşir.

13.2.2En iyi tepki dinamiği ne zaman yakınsar?

Her oyunda dinamik durmaz. En basit karşı örnek Yazı-Tura Eşleştirme oyunudur. İki oyuncu aynı anda bir madeni paranın Yazı (Y) ya da Tura (T) yüzünü gösterir. Yüzler aynıysa Eşleştiren kazanır (1 alır, rakip −1); farklıysa Ayrıştıran kazanır.

Şekil 13.4'te görüldüğü gibi her adımda bir oyuncu mutlu, öteki mutsuzdur. Oyunun saf Nash dengesi yoktur; dört hücrenin her birinde kaybeden oyuncunun sapma isteği vardır. Bu yüzden dinamik hiçbir hücrede duramaz. Oyunun tek dengesi karışıktır: iki oyuncu da Y ve T'yi ½ olasılıkla oynar. En iyi tepki dinamiği ise yalnızca saf eylemler arasında atlar; hiçbir zaman “yarı yarıya” bir davranış üretmez, bu yüzden karışık dengeye de varamaz.

Hangi oyunlarda dinamiğin durduğu sorusunun iyi bilinen bir cevabı vardır: potansiyel oyunlar (potential games).

Potansiyel fonksiyonu, bütün oyuncuların bencil hesaplarını tek bir “ortak puan tablosunda” toplar. Bir oyuncunun kârlı sapması, ortak puanı da aynı miktarda artırır. Tıkanıklık oyunları, yani her sürücünün bir yol seçtiği ve yolun maliyetinin onu kullanan sürücü sayısına bağlı olduğu trafik oyunları, potansiyel oyunların en önemli örneğidir (Monderer ve Shapley, 1996).

İspattan bir yan sonuç çıkar: Yazı-Tura Eşleştirme potansiyel oyun olamaz. Olsaydı, döngüdeki dört adımın her biri Φ'yi artırırdı ve dört adım sonra aynı profile dönüldüğünde Φ başladığı değerden büyük olurdu; bu bir çelişkidir. Döngüye giren bir dinamik, potansiyel bulunmadığının kanıtıdır.

Saf dengesi olmayan oyunlar için çare, yalnız son eyleme değil, rakibin bütün geçmişine tepki vermektir. Bu fikir kurgusal oyunu doğurur.

13.2.3Kurgusal oyun: Yazı-Tura Eşleştirme

Adındaki “kurgu”, oyuncunun rakibi hakkında yaptığı basitleştirici varsayımdır: rakip sanki sabit bir zarla oynuyormuş, zarın olasılıkları da geçmiş frekanslar kadarmış gibi davranılır. Örneğin rakip yedi turun beşinde T oynadıysa, onun P(Y) = 2/7, P(T) = 5/7 ile oynadığı varsayılır. En iyi tepki dinamiğinden farkı, tek bir son gözlem yerine bütün geçmişin kullanılmasıdır. Bu yüzden kurgusal oyunun inancı yavaş değişir: bir tek yeni gözlem, uzun bir geçmişin içinde küçük bir ağırlık taşır.

Yazı-Tura Eşleştirme'de bu kural çok sade bir hâl alır. Eşleştiren aynı yüzü istediği için, rakibin geçmişinde hangi yüz çoğunluktaysa onu oynar. Ayrıştıran farklı yüz istediği için, rakibin geçmişindeki çoğunluğun tersini oynar. Eşitlik olursa ikisi de Y oynar. İlk turda geçmiş olmadığı için ikisi de keyfî olarak Y oynar.

Kural on tur boyunca uygulandığında Tablo 13.4 elde edilir. Sütunları okurken dikkat edilecek nokta şudur: “geçmiş” sütunları o turdan önceki turları sayar, “oran” sütunları ise o turu da içerir.

Tablonun ilk birkaç satırı ayrıntılı okunmaya değer.

• t = 1: Geçmiş yoktur; iki oyuncu da keyfî olarak Y oynar.
• t = 2: Eşleştiren rakip geçmişinde 1 / 0 görür; çoğunluk Y'dir, Y oynar. Ayrıştıran da rakip geçmişinde 1 / 0 görür; çoğunluğun tersi olan T'yi oynar.
• t = 3: Eşleştiren 1 / 1 görür; eşitlikte Y oynar. Ayrıştıran 2 / 0 görür ve T oynar.
• t = 4: Eşleştiren 1 / 2 görür; çoğunluk artık T'dir ve Eşleştiren T'ye geçer. Ayrıştıran 3 / 0 görür, T'de kalır. Eşleştiren'in Y oranı 3/4 = 0,75'e düşer.
• t = 7: Ayrıştıran 3 / 3 görür; eşitlikte Y'ye geçer. Böylece Eşleştiren'in T'ye kaymasına üç tur gecikmeyle cevap verir.

Eylemler hâlâ döner: önce (Y, Y), sonra (Y, T), (T, T) ve (T, Y). Ancak en iyi tepki dinamiğinden önemli bir fark vardır. Her aşama birkaç tur sürer, çünkü inancın tersine dönmesi için geçmişteki çoğunluğun değişmesi gerekir. Oranlar ise sıçramaz, yavaş yavaş değişir: on turun sonunda Eşleştiren'in Y oranı 0,30, Ayrıştıran'ınki 0,50'dir.

13.2.4Kod izleme: fictitious()

Aşağıdaki fonksiyon, Yazı-Tura Eşleştirme'de kurgusal oyunu T tur oynatır. Eylemler sayıyla kodlanır: 0 = Y, 1 = T.

def fictitious(T):
    ne, na = [0, 0], [0, 0]   # Y/T sayaçları
    a, b = 0, 0               # 1. tur: ikisi de Y
    for t in range(1, T + 1):
        ne[a] += 1            # eşleştirenin geçmişi
        na[b] += 1            # ayrıştıranın geçmişi
        # eşleştiren: ayrıştıranın çoğunluğunu eşle
        a = 0 if na[0] >= na[1] else 1
        # ayrıştıran: eşleştirenin çoğunluğundan ayrış
        b = 1 if ne[0] > ne[1] else 0
    return ne, na

Kodun parçaları şöyledir.

• ne ve na sayaç listeleridir. ne[0] Eşleştiren'in o ana kadar kaç kez Y, ne[1] kaç kez T oynadığını tutar; na aynı bilgiyi Ayrıştıran için tutar.
• a ve b bu turda oynanacak eylemlerdir; ilk turda ikisi de 0 (Y) olarak başlatılır.
• Döngünün başında bu turun eylemleri sayaçlara eklenir; yani tur oynanmış olur.
• Ardından bir sonraki turun eylemleri hesaplanır. Eşleştiren, Ayrıştıran'ın Y sayısı T sayısından küçük değilse (eşitlik dahil) Y oynar: a = 0 if na[0] >= na[1] else 1.
• Ayrıştıran, Eşleştiren'in Y sayısı T sayısından kesin büyükse T oynar, yoksa Y: b = 1 if ne[0] > ne[1] else 0. Eşitlikte koşul yanlış olur ve Y seçilir; bu, tablodaki “eşitlikte Y” kuralıdır.

Çağrı fictitious(6) olsun. Tablo 13.5 her turun sonunda sayaçların durumunu ve bir sonraki turun kararını gösterir.

İzlemenin kritik anları 2. ve 3. turlardır. 2. tur sonunda Ayrıştıran'ın sayaçları 1 / 1 eşittir; Eşleştiren eşitlikte Y oynamayı sürdürür. 3. tur sonunda Ayrıştıran'ın sayaçları 1 / 2 olur ve Eşleştiren T'ye geçer. Ayrıştıran ise 6. tur sonuna kadar Eşleştiren'in geçmişinde Y çoğunluğunu görür ve T oynamaya devam eder. Fonksiyon ne = [3, 3], na = [1, 5] döndürür. Y oranları 3/6 = 0,50 ve 1/6 ≈ 0,17'dir; bunlar Tablo 13.4'ün 6. satırıyla aynıdır.

13.2.5Uzun vade: frekanslar dengeye yakınsar

Kurgusal oyun dört yüz tur boyunca sürdürüldüğünde eylemler döngüler hâlinde değişmeye devam eder: (Y, Y) → (Y, T) → (T, T) → (T, Y) → (Y, Y) … Ancak her döngü bir öncekinden uzundur. Geçmiş büyüdükçe çoğunluğu tersine çevirmek için daha çok tur gerekir. Frekanslar ise karışık dengeye, yani ½'ye yaklaşır: dört yüz turda Eşleştiren'in Y oranı 0,472, Ayrıştıran'ınki 0,492'dir.

Şekil 13.6'da salınımların neden söndüğü sezilebilir. Bir oyuncunun frekansı ½'den uzaklaştığında, rakibin en iyi tepkisi onu cezalandıracak yöne döner ve bu sapma bir süre sonra düzelir. Örneğin Eşleştiren'in Y oranı ½'nin üstündeyken Ayrıştıran T oynar; Eşleştiren de sonunda T'ye geçer ve kendi Y oranını düşürür. Geçmiş uzadıkça tek bir turun frekansa etkisi 1/t kadar küçülür, bu yüzden salınımın genliği de küçülür.

Bu davranış her oyunda görülmez. Kurgusal oyunda frekansların dengeye yakınsaması şu oyun sınıflarında kanıtlanmıştır:

• İki kişilik sıfır toplamlı oyunlar (Robinson, 1951). Yazı-Tura Eşleştirme bu sınıftadır.
• 2×2 oyunlar, yani iki oyuncunun ikişer stratejisi olan oyunlar (Miyasawa, 1961).
• Potansiyel oyunlar (Monderer ve Shapley, 1996).

Buna karşılık Shapley (1964), 3×3'lük genel toplamlı bir oyun kurdu. Bu oyunda eylemler giderek uzayan döngülerle döner ve frekanslar hiçbir dengeye yaklaşmaz. Shapley örneği, “her oyunda öğrenme dengeye götürür” beklentisinin yanlış olduğunu gösteren klasik sonuçtur.

13.3Pişmanlık ve Hedge

En iyi tepki dinamiği ve kurgusal oyun, oyuncunun kazanç tablosunu bildiğini ve rakibin eylemlerini gözlediğini varsayar. Bu bölümde varsayım zayıflatılır. Oyuncu rakibi modellemez; yalnızca her turdan sonra kendi eylemlerinin ne kazandırdığını (ya da kazandıracağını) görür. Rakip bir insan, bir algoritma ya da kötü niyetli bir düşman olabilir. Bu koşullarda “iyi oynamak” ne demektir? Cevap, pişmanlık kavramıdır.

13.3.1Dışsal pişmanlık

Gündelik dilde pişmanlık, geriye bakınca “keşke şunu yapsaydım” demektir. Öğrenme kuramındaki tanım bu duygunun sayısal hâlidir. Oyun bittikten sonra geriye bakılır ve şu soru sorulur: baştan sona tek bir eylemi hiç değiştirmeden oynasaydım, en iyi durumda ne kazanırdım? Bu sayı ile gerçekte kazanılan arasındaki fark pişmanlıktır.

Tanımın üç ayrıntısı önemlidir. Birincisi, karşılaştırma sabit bir eylemle yapılır; her turda sonradan en iyisini seçen “kâhinle” yapılmaz. Kâhinle karşılaştırma hiçbir algoritmanın kazanamayacağı bir yarış olurdu. İkincisi, en iyi sabit eylem ancak oyun bittikten sonra bilinir; algoritma oyun sırasında bunu bilmez. Üçüncüsü, pişmanlıksızlık ortalama bir ölçüttür. R_T büyüyebilir, ama T'den yavaş büyümelidir. Örneğin R_T = 2√T ise R_T/T = 2/√T sıfıra gider; tur başına kayıp zamanla yok olur. R_T = T/2 ise tur başına kayıp ½'de takılı kalır.

13.3.2“Lideri izle” neden başarısız olur?

Pişmanlığı küçültmek için akla gelen ilk kural şudur: o ana kadar toplam kazancı en büyük olan eylemi oyna. Bu kurala lideri izle (follow the leader) denir. Kurgusal oyuna çok benzer; geçmişe en iyi tepkidir. Ne yazık ki kötü seçilmiş bir kazanç dizisine karşı bu kural felakettir. Tablo 13.6 bunun bir örneğidir; eşitlikte A seçilir.

Dizinin hilesi, ilk turdaki 0,5'lik küçük farktır. Bu fark liderin her turda “bir adım geride” kalmasını sağlar: kazançlar 1 ve 0 arasında gidip geldiği için bir önceki turda öne geçen eylem, bu tur 0 verir. Dizi uzatıldıkça algoritmanın toplamı 0,5'te kalır, en iyi sabit eylemin toplamı ise yaklaşık T/2 olur. Pişmanlık doğrusal büyür: R_T/T → 1/2, sıfıra gitmez. Lideri izle pişmanlıksız değildir.

Sorunun kaynağı kuralın deterministik olmasıdır. Kuralı bilen bir rakip, algoritmanın hangi eylemi seçeceğini önceden hesaplayabilir ve o eyleme 0, ötekine 1 kazanç verebilir. Bu durumda algoritma her tur 0 alır. İki eylemin toplam kazancı her turda 1 olduğu için T turda iki eylemin toplamları T eder ve bunlardan büyük olanı en az T/2'dir. Demek ki her deterministik algoritmanın kötü durumda pişmanlığı en az T/2'dir. Pişmanlıksız olmanın tek yolu rastgele oynamaktır: rakip olasılıkları bilse bile hangi eylemin çıkacağını bilemez.

13.3.3Çarpımsal ağırlıklar (Hedge)

Lideri izlemenin iki zayıflığı vardır: kesin seçim yapar ve küçük bir farka tam güvenir. Çarpımsal ağırlıklar (multiplicative weights) algoritması, ya da yaygın adıyla Hedge, iki zayıflığı birden giderir. Liderin seçilme olasılığı yüksektir ama kesin değildir; fark küçükse olasılıklar da birbirine yakın kalır.

Güncelleme kuralı çarpımsaldır: kazancı 1 olan eylemin ağırlığı e^η katına çıkar, kazancı 0 olan eylemin ağırlığı değişmez. Örneğin η = ln 2 seçilirse e^η = 2 olur ve kazancı 1 olan eylemin ağırlığı tam iki katına çıkar. η = 0,5 için çarpan e^0,5 ≈ 1,65'tir.

Güncellemeler üst üste uygulandığında ağırlık, eylemin toplam kazancının üstel bir fonksiyonu olur. G_i, i eyleminin o ana kadarki toplam kazancı ise w_i = e^η·G_i'dir, çünkü e^η·g₁ · e^η·g₂ · … = e^{η·(g₁ + g₂ + …)}'dir. Bu gösterim Hedge'in “yumuşak” bir lideri izle olduğunu açıkça gösterir. Lider en büyük G_i'ye sahip olduğu için en büyük olasılığı alır. Ama iki eylemin toplamları arasındaki fark Δ ise olasılıklarının oranı e^η·Δ'dır; küçük fark küçük üstünlük demektir. η çok büyürse oran sonsuza gider ve Hedge lideri izlemeye dönüşür; η sıfıra yaklaşırsa bütün olasılıklar eşitlenir ve Hedge rastgele oynamaya dönüşür.

Sınırdaki ln n, n'nin doğal logaritmasıdır; n = 3 için ln 3 ≈ 1,1'dir. Logaritma çok yavaş büyür: eylem sayısı bin olsa bile ln 1000 ≈ 6,9'dur. Bu, Hedge'in çok sayıda eylem arasında bile hızlı öğrenebildiğini gösterir.

Sınırın iki terimi η'nın iki ayrı etkisini ölçer. İlk terim (ln n)/η, öğrenmenin yavaşlığının bedelidir: η küçükse algoritma en iyi eylemi geç fark eder. İkinci terim ηT, aşırı tepkinin bedelidir: η büyükse algoritma her dalgalanmaya fazla tepki verir ve lideri izle gibi sömürülebilir hâle gelir. En iyi η, iki terimin toplamını en küçük yapan değerdir. Toplam f(η) = (ln n)/η + ηT'nin türevi f′(η) = −(ln n)/η² + T'dir. Türevi sıfıra eşitlemek η² = (ln n)/T, yani η = √(ln n / T) verir. Bu değer yerine konunca iki terim de √(T ln n)'ye eşit olur:

(ln n)/√(ln n / T) = √(T ln n) ve √(ln n / T) · T = √(T ln n),

toplamları da 2√(T ln n)'dir.

Hedge'in lideri izleyi sömüren diziye karşı ne yaptığına bakmak sınırın somut anlamını gösterir. Tablo 13.6'daki altı turluk dizi η = 0,5 ile Hedge'e verilsin. 1. turda olasılıklar eşittir ve beklenen kazanç 0,5 · 0,5 = 0,25'tir. 2. turda A'nın ağırlığı e^0,25 ≈ 1,28, B'ninki 1'dir; p(A) = 1,28/2,28 ≈ 0,56 ve beklenen kazanç 0,44 · 1 ≈ 0,44'tür. Sonraki turlarda olasılıklar 0,56 ile 0,44 arasında gidip gelir ve her tur yaklaşık 0,44 kazanılır. Altı tur sonunda Hedge'in beklenen toplamı yaklaşık 2,44, pişmanlığı 3 − 2,44 ≈ 0,56'dır. Lideri izle aynı dizide 2,5 pişmanlık biriktirmişti. Hedge küçük farka tam güvenmediği için rakibin hilesi işe yaramaz.

Bölümün geri kalanında üç gözlem tekrar tekrar karşımıza çıkar:

• Rastgelelik şart. Lideri izle deterministik olduğu için rakip onu sömürür; Hedge karışık oynar.
• η bir ayar düğmesidir. Büyük η hızlı tepki verir ama gürültüye duyarlıdır; küçük η yavaş ama kararlıdır.
• Oyunlarda denge. Herkes pişmanlıksız oynarsa zaman ortalaması kaba korelasyonlu dengeye, sıfır toplamlı oyunlarda minimaks stratejisine yaklaşır.

13.3.4Kod izleme: hedge()

Aşağıdaki fonksiyon, her turun kazanç vektörünü içeren G listesi ve öğrenme oranı eta ile Hedge'i çalıştırır ve algoritmanın toplam beklenen kazancını döndürür.

import math
def hedge(G, eta):
    w = [1.0] * len(G[0])
    top = 0.0
    for g in G:                       # her tur
        W = sum(w)
        p = [x / W for x in w]
        top += sum(pi * gi for pi, gi in zip(p, g))
        w = [x*math.exp(eta*gi) for x, gi in zip(w, g)]
    return top

• w ağırlık listesidir; eylem sayısı kadar 1,0 ile başlar.
• Her turda önce ağırlıkların toplamı W hesaplanır, sonra her ağırlık W'ye bölünerek olasılıklar p bulunur.
• top, beklenen kazançların toplamıdır. Bu turun beklenen kazancı Σ p_i · g_i'dir; zip(p, g) iki listeyi eleman eleman eşleştirir.
• Son satır güncellemedir: her ağırlık e^η·g_i ile çarpılır.

Üç uzman (eylem) A, B, C olsun ve η = 0,5 seçilsin. İlk iki turda kazançlar g = [1, 0, 0,5], sonraki üç turda g = [0, 1, 0,5]'tir. Yani ilk iki tur A iyi, sonraki üç tur B iyidir; C her zaman ortadadır. Kullanılan çarpanlar: kazanç 1 için e^0,5 ≈ 1,65, kazanç 0,5 için e^0,25 ≈ 1,28, kazanç 0 için 1.

Şekil 13.7 Hedge'in ağırlıkları nasıl “hatırladığını” gösterir. Son ağırlıklar yalnızca toplam kazançlara bağlıdır: w_i = e^{0,5 · G_i}. Sıralama da toplam kazançların sıralamasıyla aynıdır: B (3) > C (2,5) > A (2). Kazançların hangi sırayla geldiği ağırlıkları değiştirmez; yalnızca algoritmanın yol boyunca ne kazandığını değiştirir.

13.3.5Rakip de öğrenirse

Şimdiye kadar kazanç dizisi dışarıdan verildi. Oyunlarda ise kazançları rakibin davranışı belirler ve rakip de öğrenebilir. Bu farkı görmek için Taş-Kağıt-Makas oyununda iki senaryo karşılaştırılır. Kazanan 1, berabere kalan ½, kaybeden 0 alır; böylece kazançlar [0, 1] aralığındadır. Oyuncu 1 Hedge ile öğrenir ve η = 0,1'dir. Her turda iki oyuncu da eylemlerinin beklenen kazancıyla günceller.

Senaryo 1: sabit rakip. Rakip her turda Taş'ı 0,5, Kağıt'ı 0,3, Makas'ı 0,2 olasılıkla oynar. Oyuncu 1'in her eyleminin beklenen kazancı hesaplanabilir.

Sabit rakibe karşı Hedge en iyi tepkiye gider. Bu, pişmanlıksızlığın doğal bir sonucudur: rakip değişmiyorsa en iyi sabit eylem en iyi tepkidir ve pişmanlığı küçük tutmanın tek yolu onu giderek daha sık oynamaktır.

Senaryo 2: öğrenen rakip. Şimdi rakip de Hedge kullanır ve iki oyuncu aynı anda günceller. Oyuncu 1 (0,5; 0,3; 0,2) olasılıklarıyla, oyuncu 2 eşit olasılıklarla başlar. Oyuncu 1 Kağıt'a kaydıkça oyuncu 2 için Makas değerlenir; oyuncu 2 Makas'a kaydıkça oyuncu 1 için Taş değerlenir; ve böyle sürer. Hedef sürekli kayar.

Tablo 13.8 iki farklı davranış gösterir. O turdaki olasılık (son yineleme) dönmeye devam eder: 0,19'dan 0,46'ya çıkar, 0,14'e iner. Bin turda bile durulmaz. Zaman ortalaması ise ⅓'e, yani oyunun tek Nash dengesi olan (⅓, ⅓, ⅓)'ün Taş bileşenine yaklaşır. Öğrenen bir rakibe karşı “hedefe varmak” anlamsızdır, çünkü hedef rakibin davranışıyla birlikte hareket eder. Kararlı olan şey ortalamadır.

13.3.6Hedge kendine karşı

Aynı olgu iki eylemli bir oyunda daha net görülür. Yazı-Tura Eşleştirme'de iki oyuncu da Hedge (η = 0,1) kullansın. Eşleştiren'in başlangıç ağırlıkları (Y, T) = (0,8; 0,2), yani P(Y) = 0,8; Ayrıştıran'ınkiler (0,5; 0,5)'tir. Kazanan 1, kaybeden 0 alır ve her turda iki oyuncu da eylemlerinin beklenen kazancıyla aynı anda günceller.

Şekil 13.8'de mavi eğri dengeye oturmaz; 0,1 ile 0,9 arasında giderek büyüyen salınımlar yapar. Mekanizma kurgusal oyundakine benzer. Eşleştiren Y'ye ağırlık verince Ayrıştıran için T değerlenir; Ayrıştıran T'ye kayınca Eşleştiren için T değerlenir; ve döngü sürer. Kırmızı eğri ise, yani başlangıçtan bu yana P(Y) değerlerinin ortalaması, minimaks stratejisi olan ½'ye yaklaşır: 600 turda 0,498'dir.

Bu gözlemin kuramsal bir karşılığı vardır. İki kişilik sıfır toplamlı bir oyunda iki oyuncu da pişmanlıksız bir algoritma kullanırsa, ortalama stratejileri minimaks stratejilerine, ortalama kazanç da oyunun değerine yaklaşır. von Neumann'ın minimaks teoreminin, yani sıfır toplamlı oyunlarda “maks-min = min-maks” eşitliğinin, öğrenme yoluyla yapılan ispatı bu gözleme dayanır. İspatın fikri şudur: iki oyuncunun da pişmanlığı sıfıra gidiyorsa, ikisi de ortalamada rakibinin ortalama stratejisine karşı en iyi sabit eylem kadar kazanır; bu iki ifade birleştirilince maks-min ile min-maks arasındaki fark sıfıra sıkışır.

13.3.7Pişmanlıktan dengeye

Sıfır toplamlı oyunlar dışında pişmanlıksız öğrenmenin zaman ortalaması nereye gider? Cevap, Nash dengesinden daha geniş iki denge kavramıdır. Bu kavramları anlatmanın en kolay yolu bir öneri makinesi düşünmektir. Makine her turda bir olasılık dağılımından bir eylem profili çeker ve her oyuncuya yalnızca kendi eylemini söyler. Kavşaktaki trafik ışığı böyle bir makinedir: bir sürücüye “geç”, ötekine “dur” der.

İki tanım arasındaki fark sapma anındadır. CE'de oyuncu öneriyi gördükten sonra karar verir; bu yüzden “Kır önerisi gelince Düz git” gibi öneriye bağlı sapmalar da hesaba katılır. CCE'de oyuncu, öneriyi görmeden önce bütünüyle makineden ayrılıp sabit bir eyleme geçmeyi düşünür. CE'nin koşulları her öneri için ayrı ayrı sağlandığından, ortalamada da sağlanır; bu yüzden her CE bir CCE'dir. Tersi doğru değildir: CCE daha zayıf, yani daha geniş bir kavramdır.

Şekil 13.9'daki iç içe yapı şöyle okunur. Her saf Nash dengesi bir karışık Nash dengesidir (olasılıkları 0 ya da 1 olan). Her karışık Nash dengesi bir CE'dir: oyuncular bağımsız zarlar attığında, önerisini gören oyuncu ötekiler hakkında yeni bir şey öğrenmez ve dengede zaten en iyi tepki vermektedir. Her CE de bir CCE'dir. Dışa doğru gidildikçe kavramlar genişler ama hesaplanmaları kolaylaşır: CE ve CCE doğrusal programlamayla hızlı bulunur, karışık Nash dengesi ise PPAD-tamdır.

İç pişmanlık (internal / swap regret), “a oynadığım her turda onun yerine a′ oynasaydım ne kazanırdım?” sorusunu her (a, a′) çifti için ayrı ayrı sorar. Bu, öneriye bağlı sapmanın öğrenme dilindeki karşılığıdır: “makine a dediğinde a′ oyna”. Dışsal pişmanlık bütün turları tek bir sabit eylemle karşılaştırdığı için daha kaba bir ölçüttür ve daha kaba bir dengeye götürür.

13.4Çok kollu haydut

Hedge her turdan sonra bütün eylemlerin kazancını görür. Bu bölümün başında anlatılan kumar makinesinde ise yalnızca çekilen kolun sonucu görülür. Bu küçük fark büyük bir sonuç doğurur: bilgi artık bedava değildir. Bir kol hakkında bilgi toplamanın tek yolu onu çekmektir; o kol kötüyse bu çekiş ödülden kayıptır. Çok kollu haydut problemi, bu bilgi–ödül alışverişinin en sade modelidir.

13.4.1Problem, pişmanlık ve keşif–sömürü ikilemi

Bu pişmanlık tanımı Hedge'deki dışsal pişmanlıkla aynı fikri taşır: en iyi sabit seçenekle (burada en iyi kolla) karşılaştırma. Farkı, gerçekleşen ödüllerin değil ortalamaların kullanılmasıdır. Bu sayede şans faktörü ayıklanır: kötü kolu çekip şans eseri 1 almak pişmanlığı azaltmaz, çünkü hesapta o kolun ortalaması kullanılır. Her tur, çekilen kolun en iyi koldan ne kadar geride olduğu, yani μ* − μ_at kadar pişmanlık ekler.

Problemin bütün zorluğu keşif ve sömürü ikileminde toplanır. Keşif, yeni ya da az denenmiş kollar hakkında bilgi toplar. Sömürü, o ana kadar en iyi görüneni kullanır. Yalnızca sömüren bir algoritma, şanssız bir başlangıçtan sonra yanlış kola takılabilir ve hiçbir zaman kurtulamaz. Yalnızca keşfeden bir algoritma ise bütün kolları eşit çeker ve öğrendiğini hiç kullanmaz; ödülü boşa harcar.

Haydut algoritmaları, her kol için iki sayı tutar: kolun kaç kez çekildiği N_i ve gözlenen ödüllerin ortalaması Q_i. Ortalama, her yeni ödül geldiğinde baştan hesaplanmaz; artımlı ortalama formülüyle güncellenir:

Q ← Q + (r − Q)/N

Burada N, yeni ödül de sayıldıktan sonraki çekiş sayısıdır. Formülün doğruluğu kısa bir hesapla görülür. Önceki N − 1 ödülün ortalaması Q ise toplamları (N − 1)Q'dur. Yeni ödül eklenince yeni ortalama ((N − 1)Q + r)/N = (NQ − Q + r)/N = Q + (r − Q)/N olur. Formülün yorumu da açıktır: tahmin, “sürpriz” r − Q yönünde 1/N kadar kayar. Çok çekilmiş bir kolun tahmini tek bir gözlemle az değişir.

Şekil 13.10 bölümün ikinci algoritmasının temel fikrini önceden gösterir. Az denenen kolun tahmini belirsizdir, bu yüzden güven aralığı geniştir. Aralığın üst ucu, yani “bu kolun olabileceği en iyi değer”, bu kolu yeniden denemeye değer kılar. Tahmini düşük olsa bile kol 1'in üst ucu 1,09'dur ve kol 2'nin 1,18'ine yakındır.

Haydut problemi oyun kuramının da ötesinde geniş bir uygulama alanına sahiptir: hangi reklamın ya da haberin gösterileceğine karar veren öneri sistemleri, web sitelerinde iki tasarımın karşılaştırıldığı A/B testleri, hangi tedavinin daha çok hastaya verileceğinin denemeler sırasında ayarlandığı klinik deneyler ve bir ürünün farklı fiyatlarla denendiği fiyat deneme.

13.4.2Kod izleme: ε-açgözlü

En basit haydut algoritması ε-açgözlüdür (ε-greedy). Her turda küçük bir ε olasılıkla rastgele bir kol çeker (keşif); geri kalan 1 − ε olasılıkla en büyük Q'lu kolu çeker (sömürü). “Açgözlü” adı, sömürü adımının o anki en iyi tahmine körü körüne güvenmesinden gelir.

def egreedy(mu, T, eps, rng):
    N, Q = [0] * len(mu), [0.0] * len(mu)
    for t in range(1, T + 1):
        if rng.random() < eps:           # keşif
            a = rng.randrange(len(mu))
        else:                            # sömürü
            a = Q.index(max(Q))
        r = 1 if rng.random() < mu[a] else 0
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]
    return N, Q

• mu, kolların gerçek ortalamalarıdır. Algoritma bu listeyi yalnızca ödül üretmek için kullanır; karar verirken mu'ya bakmaz.
• rng.random() 0 ile 1 arasında bir rastgele sayı üretir. Sayı eps'ten küçükse keşif yapılır ve rng.randrange(len(mu)) ile rastgele bir kol seçilir.
• Sömürüde Q.index(max(Q)) en büyük tahmini veren kolu bulur. Eşitlik varsa listedeki ilk kol seçilir.
• Ödül, kolun ortalamasıyla belirlenen bir para atışıdır: yeni bir rastgele sayı mu[a]'dan küçükse ödül 1, değilse 0'dır.
• Son iki satır sayaç ve artımlı ortalama güncellemesidir.

Çağrı egreedy([0.3, 0.5, 0.7], 8, 0.2, random.Random(11)) olsun. Kodda kollar 0'dan numaralanır: kol 0, 1, 2, açılış oyunundaki Kol 1, 2, 3'e karşılık gelir. Rastgele sayı üreteci 11 tohumuyla başlatıldığı için çağrı her çalıştırıldığında aynı sonucu verir; aşağıdaki izleme bu yüzden tekrarlanabilir.

İzleme ε-açgözlünün iki yüzünü birden gösterir. Olumsuz yüzü: ilk üç tur kol 0'a takıldı, çünkü hepsi 0 ödül verdi ve eşitlik ilk kolu seçtirdi. Keşif olmasaydı algoritma sonsuza kadar kol 0'da kalabilirdi; kol 0 bir kez 1 verse bile tahmini öteki kolların 0'ından büyük olur ve sömürü onu seçmeye devam ederdi. Olumlu yüzü: tek bir keşif en iyi kolu buldu. Şekil 13.11'de bir eksiklik de görülür: kol 1 hiç denenmedi. Sekiz turda bu önemli değildir, ama ε-açgözlünün keşfi kör bir rastgeleliktir; az bilinen kolları özellikle aramaz.

13.4.3Kod izleme: UCB1

ε-açgözlünün keşfi “kör”dür: keşif turunda her kol eşit olasılıkla seçilir, en iyi olduğu zaten bilinen kol da, hiç denenmemiş kol da. UCB1 (Upper Confidence Bound, üst güven sınırı) keşfi yönlendirir. Her kolun bir puanı vardır:

UCB_i = Q_i + √(2 ln t / N_i)

Burada t şu anki tur numarası, N_i kolun çekilme sayısıdır. Her turda puanı en büyük kol çekilir. Hiç çekilmemiş bir kolun puanı sonsuz sayılır; bu yüzden ilk turlarda her kol bir kez denenir.

Puanın iki terimi vardır. İlk terim Q_i sömürüdür: iyi görünen kol yüksek puan alır. İkinci terim √(2 ln t / N_i) güven payıdır ve keşfi temsil eder. Pay, N_i büyüdükçe küçülür: çok çekilmiş kolun tahminine güvenilir. Pay, t büyüdükçe çok yavaş (logaritmik olarak) büyür: uzun süre çekilmeyen bir kolun payı yavaş yavaş artar ve sonunda kol yeniden denenir. Bu fikre belirsizlik karşısında iyimserlik denir: her kol, verilerle çelişmeyen en iyimser değeriyle değerlendirilir. Kötü bir kol iyimser değerlendirmeyle seçilirse kısa sürede gerçek yüzünü gösterir ve payı küçülür; iyi bir kol ise iyimser değerlendirmeyi hak eder.

def ucb(mu, T, rng):
    K = len(mu)
    N, Q = [0] * K, [0.0] * K
    for t in range(1, T + 1):
        b = [math.inf if n == 0 else
             math.sqrt(2*math.log(t)/n) for n in N]
        a = max(range(K), key=lambda i: Q[i] + b[i])
        r = 1 if rng.random() < mu[a] else 0
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]
    return N, Q

• b, her kolun güven payıdır. math.inf, hiç çekilmemiş kolun sonsuz payıdır.
• max(range(K), key=lambda i: Q[i] + b[i]), Q + b puanı en büyük olan kolu seçer; eşitlikte küçük indisli kol kazanır.
• Ödül ve güncelleme ε-açgözlüdeki gibidir.

Çağrı ucb([0.3, 0.5, 0.7], 8, random.Random(3)) olsun. Tablo 13.10 her turdaki payları, puanları ve seçimi verir.

İki izlemeyi karşılaştırmak öğreticidir. ε-açgözlü kol 1'i hiç denemedi; UCB1 ise her kolu denedi ve tahmini düşük kolu bile, uzun süre çekilmeyince yeniden ziyaret etti. Sekiz turda UCB1 daha çok keşif yaptığı için daha fazla “kayıp” turu vardır: pişmanlığı 8 · 0,7 − (2 · 0,3 + 2 · 0,5 + 4 · 0,7) = 5,6 − 4,4 = 1,2'dir. Kısa vadede iki algoritma aynı yerdedir; fark uzun vadede ortaya çıkar.

13.4.4Karşılaştırma: 5000 tur, 100 tekrar

Sekiz turluk izlemeler algoritmaların nasıl çalıştığını gösterir, ama hangisinin daha iyi olduğunu göstermez. Ödüller rastgele olduğu için tek bir deney yanıltıcıdır. Karşılaştırma şöyle yapılır: kollar yine μ = (0,3; 0,5; 0,7)'dir; her algoritma 5000 tur çalıştırılır; deney 0'dan 99'a kadar 100 farklı tohumla tekrarlanır ve birikimli pişmanlıkların ortalaması alınır. ε-açgözlü bu karşılaştırmada ε = 0,1 ile çalışır.

Şekil 13.13 üç farklı büyüme hızı gösterir.

• Yalnız sömürü (ε = 0): bütün tahminler 0 başladığı için ilk tur kol 0'dır. Kol 0 bir kez 1 verirse tahmini pozitif olur ve öteki kollar hiç denenmez; hep 0 verirse de eşitlikte yine kol 0 seçilir. Her seferinde kol 0'a takılır. Her tur 0,7 − 0,3 = 0,4 pişmanlık ekler: R_T = 0,4 · T, doğrusal.
• ε-açgözlü: en iyi kolu bulduktan sonra bile turların %10'unda keşif yapar. Keşif turunda kollar eşit olasılıkla seçilir ve ortalama kayıp (0,4 + 0,2 + 0)/3 = 0,2'dir. Demek ki her tur yaklaşık 0,1 · 0,2 = 0,02 pişmanlık ekler; 5000 turda bu yaklaşık 100 eder. Başlangıçtaki öğrenme kayıplarıyla birlikte ortalama 118'dir. Pişmanlık doğrusal büyür, ama eğimi küçüktür.
• UCB1: başta daha çok keşif yapar. Pişmanlığı yaklaşık 270. ile 2.370. tur arasında ε-açgözlününkinden yüksektir. Sonra daha düşük kalır, çünkü UCB1'in pişmanlığı logaritmik, yani çok yavaş büyür (Auer, Cesa-Bianchi ve Fischer, 2002). Kötü bir kolun güven payı √(2 ln t / N) olduğundan, o kolun yeniden denenmesi için N'nin ancak ln t ile orantılı büyümesi gerekir; kötü kollara harcanan çekiş sayısı da bu yüzden yalnızca ln t kadar artar.

Logaritmik büyümenin ne kadar yavaş olduğu sayılarla görülebilir: ln 1000 ≈ 6,9, ln 1.000.000 ≈ 13,8'dir. Tur sayısı bin katına çıkınca logaritma yalnızca iki katına çıkar. Doğrusal pişmanlıkta ise tur sayısı bin katına çıkınca pişmanlık da bin katına çıkar. Uzun oyunlarda bu fark belirleyicidir.

ε bir ayar parametresidir ve bu bölümde üç farklı değer kullanılmıştır: kısa izlemede keşif görünsün diye 0,2, uzun karşılaştırmada 0,1, Çok Kollu Haydut oyununda 0,15. Küçük ε daha az keşif, ama yanlış bir başlangıçtan sonra daha geç düzeltme demektir. Sabit ε'la logaritmik pişmanlık elde edilemez; bunun için ε'un zamanla küçültülmesi gerekir.

13.4.5Oyuna dönüş: keşfin bedeli

Açılıştaki oyuna kuramın cevabıyla dönülebilir. Kollar μ = (0,3; 0,5; 0,7) iken 100 turda farklı stratejilerin beklenen ödülü ve pişmanlığı Tablo 13.11'de verilmiştir.

Tablo, keşfin bir bedeli olduğunu açıkça gösterir. En iyi kolu bilmek 3 puan değerindedir; ε-açgözlü bu 3 puanı, en iyi kolu bulduktan sonra da keşfe devam ettiği için kaybeder. UCB1 keşfi az denenen kollara yönelttiği için bu bedeli zamanla küçültür; pişmanlığı logaritmik büyür.

Açılıştaki soru. Şekil 13.1'deki durumda Kol 3'ün tek başarısız çekişi çok az bilgi verir. UCB1 burada sıradaki turu (t = 9) şöyle değerlendirir: 2 ln 9 ≈ 4,39'dur.

• Kol 1 (Q = 0,67, N = 3): 0,67 + √(4,39/3) = 0,67 + 1,21 ≈ 1,88.
• Kol 2 (Q = 0,25, N = 4): 0,25 + √(4,39/4) = 0,25 + 1,05 ≈ 1,30.
• Kol 3 (Q = 0, N = 1): 0 + √4,39 ≈ 2,10.

UCB1 Kol 3'ü seçer. Tek bir başarısızlık, bir kolu bir kenara atmak için yeterli kanıt değildir.

İnsanlar nasıl karar verir? Dört kollu bir haydut deneyinde insan deneklerin seçimleri, belirsizliğe bonus veren UCB benzeri keşiften çok, değer farkına göre olasılıklı seçimle açıklandı (Daw vd., 2006). Bu seçim kuralına softmax seçimi denir: bir kolun seçilme olasılığı, tahmini değerinin üstel fonksiyonuyla orantılıdır. Bu kural, Hedge'deki p_i ∝ e^η·G_i ile aynı biçimdedir.

13.5Pekiştirmeli öğrenme

Haydut probleminde her tur birbirinden bağımsızdır: bugün hangi kol çekilirse çekilsin, yarın makine aynı makinedir. Pek çok gerçek problemde ise bugünkü eylem yarının durumunu değiştirir. Satrançta bir hamle tahtayı değiştirir; bir robotun adımı onun konumunu değiştirir. Bu bölüm, eylemlerin gelecekteki durumu da etkilediği öğrenme problemlerini ele alır.

13.5.1Hayduttan pekiştirmeli öğrenmeye: Q-öğrenme

Haydut, tek durumlu bir problemdir. Pekiştirmeli öğrenmede (reinforcement learning, RL) ise eylem, ödülün yanında bir sonraki durumu da belirler. Durum, ajanın bulunduğu konumdur: tahtadaki dizilim, bir labirentteki hücre ya da bir robotun eklem açıları. Bir eylemin değeri artık yalnızca hemen aldığı ödülle ölçülemez; vardığı durumun gelecekte sağlayacağı ödüller de hesaba katılmalıdır. Hedefe tek adım uzaklıktaki bir durum, ödül vermese bile değerlidir.

Q-öğrenme (Q-learning; Watkins, 1989), her durum–eylem çifti için bir değer tahmini tutar: Q(s, a), “s durumunda a eylemini yapar, sonra en iyi biçimde devam edersem toplam ne kazanırım?” sorusunun cevabıdır. Ajan s durumunda a eylemini yapıp r ödülünü alarak s′ durumuna geçtiğinde tahmini şöyle günceller:

Formülün yapısı haydutun artımlı ortalamasıyla aynıdır: “yeni tahmin = eski tahmin + adım × (hedef − eski tahmin)”. Fark hedeftedir. Haydutta hedef yalnızca gözlenen ödüldü. Q-öğrenmede hedef, gözlenen ödül ile varılan durumun en iyi değerinin iskontolu toplamıdır. max_a′ Q(s′, a′) terimi, “s′'ne vardıktan sonra en iyi eylemi yaparsam” varsayımını taşır. Bu, Q-öğrenmenin kendi tahminlerini kullanarak öğrenmesi demektir: hedefin bir kısmı da bir tahmindir.

γ'nın anlamı bir örnekle netleşir. γ = 0,9 ise bir adım sonra gelecek 1 puan bugün 0,9, iki adım sonra gelecek 1 puan 0,9² = 0,81 değerindedir. γ sıfıra yakınsa ajan yalnızca hemen gelen ödüle bakar (miyop davranır); 1'e yakınsa uzak geleceği de önemser.

Çoklu ajan ortamında Q-öğrenmenin önemli bir zayıflığı ortaya çıkar. Tek ajanlı Q-öğrenmenin yakınsama kanıtı, geçişlerin ve ödüllerin zamanla değişmediği, yani durağan bir ortam varsayar. Çoklu ajan ortamında ise bir ajanın gördüğü sonuçlar öteki ajanların davranışına bağlıdır. Öteki ajanlar da öğrendikçe oyunun kuralları ajanın gözünde sürekli değişir: dün iyi olan bir eylem bugün kötü olabilir. Ortam durağan değildir (non-stationary) ve tek ajanlı yakınsama garantileri geçerliliğini yitirir. Bu sorunu yönetmenin bir yolu kendine karşı oyundur (AlphaZero): ajan kendi kopyalarına karşı oynar; böylece rakip de ajanla birlikte gelişir.

13.5.2Kod izleme: q_learn()

Ortam dört hücreli bir koridordur: s₀, s₁, s₂, s₃. Her hücrede iki eylem vardır: sol ve sağ. s₃ hedeftir; oraya varan geçiş 1 ödül verir ve epizot (bir deneme) biter. Öteki geçişlerin ödülü 0'dır. Fonksiyon, önceden kaydedilmiş epizotları (her biri (s, a, r, s′) dörtlülerinin listesi) sırayla işler.

def q_learn(episodes, alpha, gamma):
    Q = [[0.0, 0.0] for s in range(4)]  # [sol, sağ]
    for ep in episodes:
        for s, a, r, s2 in ep:
            best = 0 if s2 == 3 else max(Q[s2])
            hedef = r + gamma * best
            Q[s][a] += alpha * (hedef - Q[s][a])
    return Q

• Q, dört satırlı bir tablodur; her satırda [sol, sağ] eylemlerinin değeri tutulur. Eylem 0 sol, 1 sağdır.
• best, varılan durumun en iyi değeridir. Hedefe varılmışsa (s2 == 3) epizot biter ve gelecek yoktur; değer 0 alınır.
• hedef, r + γ · best'tir; son satır Q-öğrenme güncellemesidir.

Çağrı q_learn(ep, 0.5, 0.9) olsun. ep üç epizottan oluşur. İlk ikisinde ajan s₀'dan başlayıp üç kez sağa gider. Üçüncüsünde s₁'de bir kez sola gider, sonra yeniden sağa ilerler.

Şekil 13.14 Q-öğrenmenin temel davranışını özetler: ödül hedeften geriye doğru yayılır. Q(s2,sağ) = 0,875 → Q(s1,sağ) = 0,450 → Q(s0,sağ) = 0,152. Her hücrede Q(sağ) > Q(sol) olduğundan, her durumda en büyük Q'lu eylemi seçen açgözlü politika “hep sağa” der. Ajan bu politikayı ödülü yalnızca son adımda gördüğü hâlde öğrenmiştir.

Aynı epizotlar sonsuza kadar tekrarlansaydı değerler nereye giderdi? Hep sağa gidildiğinde Q(s2,sağ)'nin hedefi her seferinde 1'dir, dolayısıyla Q(s2,sağ) → 1. Q(s1,sağ)'nin hedefi 0,9 · Q(s2,sağ)'dir ve 0,9'a gider. Q(s0,sağ) da 0,9² = 0,81'e gider. Değerler, hedefe uzaklıkla γ'nın kuvvetleri biçiminde azalır: uzaktaki ödül iskonto edilir.

13.5.3Q-öğrenmenin ötesi: yöntemler ve kilometre taşları

Bu bölümdeki algoritmalar, geniş bir ailenin en sade üyeleridir. Ailenin birkaç önemli üyesi şunlardır.

• Thompson örneklemesi (Thompson sampling; Thompson, 1933): haydut için Bayesçi bir yöntemdir. Her kol için “ortalaması şu olabilir” biçiminde bir olasılık dağılımı tutar; bu dağılım gözlemlerle güncellenmiş bir son olasılık dağılımıdır. Her turda her kolun dağılımından bir tahmin çekilir ve en büyük tahmini veren kol çekilir. Belirsiz bir kol bazen yüksek bir tahmin verdiği için kendiliğinden keşfedilir; UCB1'deki iyimserliğin olasılıklı bir karşılığıdır.
• Kazan-kal, kaybet-değiş (Win-Stay Lose-Shift, WSLS; Nowak ve Sigmund, 1993): Mahkûmun İkilemi için bir kuraldır. 3 ya da 5 puan alındıysa aynı hamle tekrarlanır; 0 ya da 1 alındıysa hamle değiştirilir. Tek bir hatadan sonra iki turda işbirliğine döner.
• EXP3: yalnızca çekilen kolun ödülünü gören Hedge'dir; çekişmeli (adversarial) haydut için tasarlanmıştır. Ödülleri kötü niyetli bir rakip seçse bile pişmanlığı T'den yavaş büyür (Auer, Cesa-Bianchi, Freund ve Schapire, 2002).
• SARSA ve DQN: Q-öğrenmenin akrabalarıdır. DQN, Q tablosu yerine bir sinir ağı kullanır; bu sayede tabloya sığmayacak kadar çok durumu olan problemlerde (örneğin ekran görüntüsünden Atari oyunları) çalışır (Mnih vd., 2015).
• CFR (counterfactual regret minimization, karşı-olgusal pişmanlık minimizasyonu): pişmanlığa dayalı bir poker yöntemidir. Oyunun her karar noktasında ayrı bir pişmanlık tutar ve bunları küçültür (Zinkevich vd., 2007).

Oyunlar pekiştirmeli öğrenme için iyi bir laboratuvardır: kurallar açıktır, ödül nettir (kazanmak ya da kaybetmek), oyun milyonlarca kez tekrarlanabilir. Tablo 13.13 iki yaklaşımın öne çıktığını gösterir. Tam bilgili oyunlarda (tavla, satranç, Go) kendine karşı oyun başarılı oldu. Eksik bilgili oyunlarda, özellikle pokerde, rakibin kartları görülmediği için pişmanlık tabanlı yöntemler öne çıktı. Pokerdeki başarı bu bölümün kuramıyla doğrudan bağlantılıdır: CFR, iki oyunculu sıfır toplamlı bir oyunda pişmanlığı küçülttüğü için zaman ortalaması minimaks stratejisine yaklaşır.

13.6Evrimsel dinamik

Şimdiye kadarki bütün modellerde öğrenen bir birey vardı: sayaç tutan, ağırlık güncelleyen, tahmin yapan bir oyuncu. Evrimsel oyun kuramında birey hiçbir şey öğrenmez. Her birey doğuştan tek bir stratejiye sahiptir ve onu ömrü boyunca oynar. Değişen, nüfusun bileşimidir: başarılı stratejiyi taşıyan bireyler daha çok yavru bırakır ve o strateji yayılır. Rasyonellik yoktur, seçilim vardır. Şaşırtıcı olan, bu “akılsız” sürecin çoğu zaman Nash dengesinin öngördüğü yere varmasıdır.

13.6.1Replikatör dinamiği ve ESS

Model şöyledir. Büyük bir nüfusta bireyler rastgele ikili eşleşir ve aralarında bir oyun oynar. Her birey tek bir strateji oynar ve onu yavrularına aktarır. Bir stratejinin başarısı, onu oynayan bireyin nüfustan rastgele seçilen bir rakibe karşı ortalama kazancıyla ölçülür.

Formül, yavru sayısının uygunlukla orantılı olduğu varsayımından çıkar. Nüfusta i stratejisini oynayan n_i birey olsun ve her biri f_i yavru bıraksın. Yeni nesilde n_i f_i birey i'yi oynar. Yeni pay, bunun toplam yavru sayısına oranıdır: n_i f_i / Σ_j n_j f_j. Pay ve paydayı toplam nüfus n'ye bölmek x_i f_i / Σ_j x_j f_j = x_i f_i / f̄ verir.

Formülün yorumu tek cümledir: ortalamanın üstünde kazanan strateji yayılır. f_i > f̄ ise f_i/f̄ > 1 ve pay artar; f_i < f̄ ise pay azalır. Paylar her zaman toplamı 1 olan bir dağılım olarak kalır. Formülün anlamlı olması için uygunlukların pozitif olması gerekir: negatif bir uygunluk negatif yavru sayısı demek olurdu. Bu yüzden derste her kazanca sabit bir taban eklenir (burada 3). Tabanın eklenmesi stratejilerin sıralamasını ve dinlenme noktalarını değiştirmez; yalnızca dinamiğin hızını etkiler. (Sürekli zamanlı sürümde ẋ_i = x_i(f_i − f̄) yazılır; bu derste kesikli biçim yeterlidir.)

Evrimsel bakışın denge kavramı evrimsel kararlı stratejidir (evolutionarily stable strategy, ESS; Maynard Smith ve Price, 1973).

Koşulun iki parçası mutantın neden yayılamadığını açıklar. Mutantlar azken hemen her eşleşmeleri yerleşik x'lerle olur. İlk koşul, mutantın bu eşleşmelerde yerleşiklerden kötü kazandığını söyler; mutant hemen geriler. İlk koşulda eşitlik varsa belirleyici olan seyrek mutant–mutant eşleşmeleridir: ikinci koşul, mutantla karşılaşınca yerleşiğin mutanttan iyi kazandığını söyler. Her ESS bir simetrik Nash dengesidir (ilk koşulun eşitsizliği ≥ olarak her zaman sağlanır); ama her Nash dengesi ESS değildir.

Örnek oyun Şahin–Güvercin'dir. Bireyler değeri V = 4 olan bir kaynak için karşılaşır. Şahin her zaman kavga eder; Güvercin gösteriş yapar ama kavga başlarsa çekilir. Kavga etmenin maliyeti C = 6'dır.

• İki şahin kavga eder: biri kazanır (V), biri yaralanır (−C); ortalama (V − C)/2 = (4 − 6)/2 = −1.
• Şahin güvercine karşı kaynağı alır: V = 4; güvercin 0 alır.
• İki güvercin kaynağı paylaşır: V/2 = 2.

Şekil 13.15'teki oyunda saf strateji ESS değildir. Bütün nüfus güvercinse, bir şahin mutant her eşleşmede 4 alır, güvercinler ise 2 alır; şahinler yayılır. Bütün nüfus şahinse, bir güvercin mutant 0 alır, şahinler ise −1 alır; güvercinler yayılır. İki uçta da azınlıkta olan strateji avantajlıdır. Bu yüzden nüfus bir karışımda dengelenmelidir.

13.6.2Şahin–Güvercin adım adım

Şahin payı x, güvercin payı 1 − x olsun. Bir şahin, rakibi x olasılıkla şahin, 1 − x olasılıkla güvercin olan bir eşleşmeye girer. Taban 3 eklenmiş uygunluklar:

f_Ş = 3 + (−1) · x + 4 · (1 − x) = 7 − 5x, f_G = 3 + 0 · x + 2 · (1 − x) = 5 − 2x

Nüfus ortalaması f̄ = x · f_Ş + (1 − x) · f_G, yeni şahin payı x′ = x · f_Ş / f̄'dir.

Tablo 13.14 iki eğilimi birlikte gösterir. Şahin payı her nesil artar, çünkü her satırda f_Ş > f̄'dır. Ama şahinlerin avantajı giderek küçülür: f_Ş 6,50'den 5,00'e, f_Ş − f_G farkı 1,70'ten 0,80'e iner. Şahinler çoğaldıkça birbirleriyle daha sık karşılaşır ve pahalı kavgalara girer. Artış yavaşlar; nüfus bir dinlenme noktasına yaklaşır.

13.6.3Her başlangıçtan ESS'ye

Dinlenme noktası, iki stratejinin eşit kazandığı paydır; o noktada f_Ş = f_G = f̄ olur ve pay değişmez:

7 − 5x = 5 − 2x ⇒ 2 = 3x ⇒ x* = 2/3

Genel olarak (taban eklenmeden) (V − C)/2 · x + V(1 − x) = (V/2)(1 − x) denklemi x* = V/C verir; burada 4/6 = 2/3'tür. Bu değer, oyunun simetrik karışık Nash dengesiyle aynıdır: karışık dengede bir oyuncunun iki stratejisi arasında kayıtsız olması gerekir, bu da tam olarak f_Ş = f_G koşuludur.

Dinlenme noktası kararlıdır. x < 2/3 iken 7 − 5x > 5 − 2x, yani şahinler ortalamanın üstünde kazanır ve artar. x > 2/3 iken eşitsizlik tersine döner ve şahinler azalır. Her iki yönden de nüfus 2/3'e itilir.

Şekil 13.16 bu oyunda her iç başlangıcın ESS'ye gittiğini gösterir. Her oyun bu kadar uysal değildir. Taş-Kağıt-Makas'ta replikatör dinamiği dengenin etrafında döner: taşlar çoğalınca kağıtlar avantaj kazanır, kağıtlar çoğalınca makaslar, makaslar çoğalınca taşlar; nüfus bir yere yerleşmez. Geyik Avı'nda ise dinamik başlangıca göre iki saf dengeden birine gider: işbirlikçiler (geyik avcıları) başta yeterince çoksa geyik dengesi, azsa tavşan dengesi oluşur.

13.7Tekrarlanan oyunlar

Mahkûmun İkilemi tek seferlik bir oyun olarak oyun kuramının en karamsar sonuçlarından birini verir: iki oyuncu da ihanet eder ve ikisi de işbirliğinden kötü durumda kalır. Oysa gerçek hayatta aynı kişilerle, aynı firmalarla, aynı komşularla tekrar tekrar karşılaşırız. Bu bölümde tekrarın işbirliğini nasıl mümkün kıldığı, hangi stratejilerin başarılı olduğu ve öğrenen bir nüfusta işbirliğinin nasıl yayıldığı incelenir.

13.7.1Tekrarlanan Mahkûmun İkilemi ve kinci tetik

Bu bölümde Mahkûmun İkilemi puanlarla yazılır ve yüksek puan iyidir. S (sessiz kalmak) işbirliği, İ ihanettir.

Şekil 13.17'deki dört sayının adları vardır: cazibe 5 (rakip işbirliği yaparken ihanet etmek), karşılıklı işbirliği 3, karşılıklı ihanet 1, enayi 0 (rakip ihanet ederken işbirliği yapmak). Sıralama cazibe 5 > karşılıklı işbirliği 3 > karşılıklı ihanet 1 > enayi 0'dır. İhanet baskın stratejidir: rakip S oynarsa İ 5, S 3 verir; rakip İ oynarsa İ 1, S 0 verir.

Sonlu ve bilinen sayıda tekrar sonucu değiştirmez. Oyunun tam 10 tur süreceğini iki oyuncu da biliyorsa, son tur bir tek seferlik oyundur ve iki taraf da ihanet eder. 9. turda oyuncular son turun ne olacağını bilir; 9. turdaki davranış 10. turu etkilemez, o hâlde 9. tur da tek seferlik oyun gibidir ve ihanet edilir. Bu geriye doğru çıkarım ilk tura kadar sürer: her turda ihanet.

Durum, oyunun ne zaman biteceği bilinmediğinde değişir. Oyun her turdan sonra δ olasılıkla bir tur daha sürsün (ve 1 − δ olasılıkla bitsin). δ'ya iskonto faktörü denir; bir sonraki turun bugünkü değerini ölçer. Bu duruma geleceğin gölgesi de denir: gelecek ne kadar olasıysa, bugünkü davranışın üzerine o kadar uzun bir gölge düşer. Oyunun beklenen süresi 1/(1 − δ) turdur; örneğin δ = 0,9 için ortalama 10 tur.

İki oyuncu da kinci tetik oynarken birinin sapmaya değip değmeyeceği hesaplanabilir. Hesapta geometrik seri kullanılır. S = a + aδ + aδ² + … toplamında her terim bir öncekinin δ katıdır; bu yüzden S = a + δS yazılabilir ve S = a/(1 − δ) bulunur (0 ≤ δ < 1 iken).

Bu sonuç çok daha genel bir olgunun özel hâlidir. Halk teoremi (folk theorem) şunu söyler: δ yeterince büyükse, her oyuncuya ihanetle garantileyebileceğinden (burada 1'den) fazlasını veren pek çok ortalama kazanç, tekrarlanan oyunun bir dengesinde sürdürülebilir. Adı, sonucun kimin tarafından ilk kanıtlandığının bilinmemesinden, “halk arasında” bilinmesinden gelir. Teoremin iyi ve kötü bir yüzü vardır. İyi yüzü: işbirliği mümkündür. Kötü yüzü: çok sayıda denge vardır ve kuram hangisinin oynanacağını söylemez.

13.7.2İşbirliği hangi δ'da sürer?

Eşiğin cazibeye nasıl bağlı olduğu, cazibeyi değiştirerek görülebilir. Uymak 3/(1 − δ), sapmak cazibe + δ/(1 − δ) değerindedir; uymak ≥ sapmak ancak ve ancak δ ≥ δ* = (cazibe − 3)/(cazibe − 1).

Şekil 13.18'deki grafikte iki eğri δ = 0'da 3 ve cazibe değerinden başlar. Sapma eğrisi daha yüksekten başlar ama daha yavaş yükselir, çünkü sapan oyuncu gelecekte her tur 3 yerine 1 alır. Gelecek ne kadar değerliyse (δ büyükse) kinci tetik tehdidi o kadar caydırıcıdır. Cazibe arttıkça işbirliği için gereken eşik de yükselir: cazibe 4 iken δ* = 1/3, cazibe 9 iken δ* = 6/8 = 0,75'tir. İhanetin anlık kazancı büyüdükçe, onu caydırmak için geleceğin daha olası olması gerekir.

13.7.3On turluk maçlar

Kinci tetik işbirliğini korur ama çok serttir: tek bir ihanet sonsuza kadar cezalandırılır. Daha yumuşak ve çok ünlü bir strateji Tit-for-Tat'tır (TFT, “kısasa kısas”): ilk turda işbirliği yap, sonra rakibin son hamlesini tekrarla. Karşılaştırma için beş strateji tanımlanır:

• Hep İşbirliği (Hep-S) ve Hep İhanet (Hep-İ): rakibe bakmadan hep aynı hamle.
• Tit-for-Tat (TFT): S ile başla, sonra rakibin son hamlesini kopyala.
• Kinci (Grim): S ile başla; rakip bir kez ihanet ederse hep İ.
• Şüpheci TFT (ŞTFT): İ ile başla, sonra rakibin son hamlesini kopyala.

Şekil 13.19'daki maçlar puanlarıyla birlikte okunmalıdır.

1. TFT – Hep İşbirliği: TFT işbirliği yapana işbirliğiyle karşılık verir. Her tur (S, S): iki taraf da 10 · 3 = 30.
2. TFT – Hep İhanet: İlk tur TFT S, rakip İ: TFT 0, rakip 5. Sonraki dokuz tur TFT rakibin İ'sini kopyalar ve (İ, İ) sürer: her tur 1'er. TFT 0 + 9 = 9, rakip 5 + 9 = 14. TFT ilk turda sömürülür, sonra hep ihanet eder.
3. TFT – Şüpheci TFT: Şüpheci TFT ihanetle başlar. İki TFT birbirini “yankılar”: TFT rakibin İ'sini kopyalarken rakip TFT'nin S'sini kopyalar; S/İ dönüşümlü sürer. Her oyuncu beş tur 5, beş tur 0 alır: ikisi de 25.
4. Kinci – Şüpheci TFT: 1. tur Kinci S, ŞTFT İ: 0 – 5. 2. tur Kinci affetmez ve İ oynar, ŞTFT Kinci'nin S'sini kopyalar: 5 – 0. Sonraki sekiz tur ikisi de İ: 8'er. Toplam 13 – 13.
5. Hep İhanet – Hep İşbirliği: Saf işbirlikçi tamamen sömürülür: 10 · 5 = 50'ye 0.

Bu maçlardan dikkat çekici bir özellik çıkar: TFT bir maçı asla kazanamaz. TFT hiçbir zaman ilk ihaneti yapmaz ve rakibin her ihanetine en fazla bir ihanetle cevap verir; bu yüzden bir maçta rakibinden fazla puan toplayamaz. En iyi durumda berabere kalır. Yine de, birazdan görüleceği gibi, turnuvayı kazanır.

13.7.4Kod izleme: match()

Maçları oynatan kod kısadır. PAY sözlüğü, iki hamlenin birleşimini (örneğin "Sİ") iki oyuncunun puanlarına eşler. Stratejiler, kendi geçmişini ve rakibin geçmişini alan küçük fonksiyonlardır.

PAY = {"SS": (3, 3), "Sİ": (0, 5),
       "İS": (5, 0), "İİ": (1, 1)}
tft = lambda ben, rakip: rakip[-1] if rakip else "S"
stft = lambda ben, rakip: rakip[-1] if rakip else "İ"
def match(s1, s2, T):
    h1, h2, p1, p2 = [], [], 0, 0
    for t in range(T):
        a, b = s1(h1, h2), s2(h2, h1)
        u, v = PAY[a + b]
        h1.append(a); h2.append(b)
        p1, p2 = p1 + u, p2 + v
    return p1, p2

• tft: rakibin geçmişi boş değilse rakibin son hamlesini (rakip[-1]) döndürür, boşsa "S". stft aynı kuraldır ama boş geçmişte "İ" döndürür.
• match: her turda iki strateji kendi bakış açısından çağrılır. Birinci oyuncu s1(h1, h2), ikinci oyuncu s2(h2, h1) ile çağrılır; böylece her strateji önce kendi, sonra rakibin geçmişini alır.
• PAY[a + b], iki hamle harfini birleştirip puan çiftini bulur. Hamleler geçmişlere eklenir ve puanlar toplanır.

Fonksiyon (15, 15) döndürür. Şekil 13.20 bir yankı döngüsünü gösterir: tek bir ilk ihanet, iki kopyalayıcı strateji arasında sonsuza kadar süren bir “Sİ / İS” dönüşümü başlatır. Tur başına ortalama puan (0 + 5)/2 = 2,5'tir; karşılıklı işbirliğinde 3 olurdu. Döngüyü kırabilecek tek şey, iki stratejiden birinin bir kez “affetmesi”dir; TFT ve ŞTFT bunu yapmaz.

13.7.5Mini Axelrod turnuvası

Beş strateji, kendi ikizi dahil herkesle on turluk birer maç yapsın. Tablo 13.16 her satırdaki stratejinin, sütundaki rakibe karşı on turda topladığı puanı verir.

Sıralama: Tit-for-Tat (124), Hep İşbirliği (117), Kinci (112), Hep İhanet (98), Şüpheci TFT (90). TFT birinci, hiçbir maçı kazanmadan. Hep İhanet ise her maçı kazanır ya da berabere bitirir, ama sondan ikinci olur. Açıklama, puanların nereden geldiğindedir. Hep İhanet tek tek maçları kazanır ama kazandığı maçlarda az puan toplar: işbirlikçilerle karşılaşınca bir kez sömürür, sonra karşılıklı ihanete düşer ve tur başına 1 alır. TFT ise işbirlikçilerle uzun karşılıklı işbirliği kurar ve tur başına 3 toplar. Turnuva, rakibi yenmeyi değil, toplam puanı ödüllendirir.

Turnuva tablosu evrimsel bir hikâyeye de dönüştürülebilir. Beş strateji nüfusun beşte birer payına sahip olsun ve her stratejinin uygunluğu, nüfustan rastgele seçilen bir rakibe karşı ortalama puanı olsun: TFT 124/5 = 24,8, Hep-S 23,4, Kinci 22,4, Hep-İ 19,6, ŞTFT 18,0. Nüfus ortalaması f̄ = 541/25 = 21,64'tür. Replikatör kuralıyla bir nesil sonra paylar TFT 0,2 · 24,8/21,64 ≈ 0,229, Hep-S ≈ 0,216, Kinci ≈ 0,207, Hep-İ ≈ 0,181, ŞTFT ≈ 0,166 olur. Ortalamanın üstünde kazanan üç “iyi niyetli” strateji yayılır; ihanetle başlayanlar geriler.

13.7.6Axelrod turnuvaları ve dersleri

Mini turnuva gerçek bir deneyin küçük bir kopyasıdır. Siyaset bilimci Robert Axelrod, 1980'de iki bilgisayar turnuvası düzenledi. Oyun kuramcıları, matematikçiler ve bilgisayar programcıları tekrarlanan Mahkûmun İkilemi için program gönderdi: ilk turnuvaya 14, ikincisine 62 program katıldı. İkisini de Anatol Rapoport'un dört satırlık Tit-for-Tat programı kazandı. İkinci turnuvanın katılımcıları ilk turnuvanın sonuçlarını biliyordu ve TFT'yi yenmeye çalıştı; yine de başaramadılar (Axelrod, 1984).

Axelrod başarılı stratejilerin dört ortak özelliğini sıraladı:

• İyi niyetli: İlk ihaneti yapan olma. Mini turnuvada iyi niyetli üç strateji (TFT, Hep-S, Kinci) ilk üç sırayı aldı.
• Misilleme yapan: İhanet cezasız kalmasın. Hep İşbirliği misilleme yapmadığı için Hep İhanet karşısında 0 aldı.
• Affedici: Rakip işbirliğine dönerse sen de dön. Kinci affetmediği için Şüpheci TFT'ye karşı yalnız 13 aldı; TFT 25 aldı.
• Anlaşılır: Rakip kuralını kolayca öğrenebilsin. TFT'nin kuralı birkaç turda anlaşılır; rakip ona karşı işbirliğinin en iyisi olduğunu çabuk öğrenir.

TFT'nin zayıf noktası gürültüdür, yani bir oyuncunun yanlışlıkla istemediği hamleyi yapma olasılığıdır. Gürültülü bir ortamda iki TFT, tek bir hatadan sonra sonsuz bir misilleme döngüsüne girer.

Şekil 13.21'deki maçta ilk üç tur (S, S)'dir: 9'ar puan. 4. turda A yanlışlıkla İ oynar: A 5, B 0 alır. 5. turda B, A'nın İ'sini kopyalar; A ise B'nin S'sini kopyalar: A 0, B 5. Bundan sonra iki oyuncu sırayla birbirine ihanet eder. 4.–10. turlar arasındaki yedi turda A dört kez (4, 6, 8, 10), B üç kez (5, 7, 9) 5 alır. Toplamlar 9 + 20 = 29 ve 9 + 15 = 24'tür; iki oyuncunun toplamı 60'tan 53'e düşer. Hatayı yapan A bile, uzun bir maçta karşılıklı işbirliğinin tur başına 3'ünü kaybeder. Çare olarak cömert TFT (generous Tit-for-Tat) önerilir: rakibin ihanetini bazen (belli bir olasılıkla) affeder ve yankı döngüsünü kırar; gürültülü ortamda TFT'den daha iyi sonuç verir. Kazan-kal, kaybet-değiş (WSLS) de tek hatadan iki turda işbirliğine döner.

Son bir ders: başarı ortama bağlıdır. Hiçbir strateji her rakip havuzunda en iyi değildir. Rakip havuzu değişirse sıralama değişir. Örneğin havuz yalnızca Hep İhanet'lerden oluşsaydı en iyi strateji Hep İhanet olurdu; TFT her maçta ilk turda sömürülürdü. Axelrod bu yüzden evrimsel turnuvalar da düzenledi: her nesilde stratejiler önceki turnuva başarılarıyla orantılı olarak çoğalır (replikatör dinamiği). Bu turnuvalarda saldırgan stratejiler önce, sömürecek saf işbirlikçiler varken çoğalır; kurbanları azalınca kendileri de geriler ve TFT gibi iyi niyetli, misilleme yapan stratejiler nüfusa yerleşir.

13.8Tartışma: öğrenme, insan ve etik

Bölümün sonuçları üç tartışma sorusu etrafında toplanabilir.

Öğrenme her zaman optimuma götürür mü? Hayır. Bölüm boyunca birçok karşı örnek görüldü. En iyi tepki dinamiği Yazı-Tura'da döner; kurgusal oyun Shapley'nin 3×3 örneğinde yakınsamaz; iki Hedge oyuncusunun son yinelemesi salınmaya devam eder. Çevre ve rakipler de değişir: öğrenen rakip hedefi kaydırır. Yanlış bir model de kötü bir yakınsamaya yol açar: yalnızca sömüren bir haydut algoritması yanlış kola takılır. Bu yüzden öğrenme kuramında güvenilir hedef çoğu zaman “dengeye varmak” değil, pişmanlıksızlıktır: rakip ne yaparsa yapsın, geriye bakınca hiçbir sabit stratejinin çok daha iyi olmayacağı garantisi.

İnsanlar algoritmalar gibi mi öğrenir? Kısmen. Benzerlikler açıktır: insanlar da deneme-yanılmayla öğrenir ve geçmiş deneyimlerine göre davranışlarını değiştirir. Farklar da vardır: insanlar risk algısı, duygular ve sosyal normlarla hareket eder; algoritmalar ise tanımlı bir ödülü izler. Haydut deneyindeki bulgu (Daw vd., 2006), insanların keşif davranışının UCB gibi bir algoritmadan çok softmax seçimine benzediğini göstermiştir.

Uyarlanabilir sistemlerde etik riskler nelerdir? Öğrenen sistemler veriyi olduğu gibi öğrenir. Verideki önyargı, sistemin kararlarına taşınır (veri önyargısı). Tıklama sayısını en büyük yapmayı öğrenen bir öneri sistemi, kullanıcıyı manipüle eden içerikleri öne çıkarabilir (tıklama tuzağı). Kullanıcı davranışından öğrenmek mahremiyet sorunları doğurur. Daha incelikli bir risk de algoritmik fiyat koordinasyonudur: aynı pazarda fiyat belirleyen öğrenen botlar, açıkça anlaşmadan yüksek fiyatlarda “örtük bir anlaşmaya” varabilir. Bu, tekrarlanan Mahkûmun İkilemi'ndeki işbirliğinin tüketici aleyhine çalışan bir hâlidir: kinci tetik benzeri cezalandırma stratejilerini öğrenen botlar, rakibin indirimini fiyat savaşıyla cezalandırarak yüksek fiyatı korur.

13.9Özet

• En iyi tepki dinamiğinde oyuncular sırayla rakibin son eylemine en iyi tepki verir. Dinamik durursa bir saf Nash dengesinde durur; hangi dengeye varıldığı başlangıca bağlıdır. Sonlu potansiyel oyunlarda her kârlı sapma ortak potansiyeli artırdığı için dinamik mutlaka durur. Yazı-Tura Eşleştirme gibi saf dengesi olmayan oyunlarda döner.
• Kurgusal oyunda oyuncu rakibin bütün geçmişinin frekanslarına en iyi tepki verir. Yazı-Tura'da eylemler giderek uzayan döngülerle döner, frekanslar ise (½, ½)'ye yaklaşır (400 turda 0,472 ve 0,492). Yakınsama sıfır toplamlı (Robinson), 2×2 (Miyasawa) ve potansiyel oyunlarda garantilidir; Shapley'nin 3×3 örneğinde yoktur.
• Dışsal pişmanlık, geriye dönük en iyi sabit eylemle algoritma arasındaki toplam farktır: R_T = max_i Σ g_t(i) − Σ g_t(a_t). R_T/T → 0 ise algoritma pişmanlıksızdır. Lideri izle gibi deterministik kurallar sömürülür (pişmanlık ≈ T/2).
• Hedge ağırlıkları w_i ← w_i · e^η·g_t(i) ile günceller ve ağırlıklarla orantılı olasılıkla oynar. R_T ≤ (ln n)/η + ηT; η = √(ln n / T) ile R_T ≤ 2√(T ln n).
• Sabit rakibe karşı Hedge en iyi tepkiye gider; öğrenen rakibe karşı son yineleme döner ama zaman ortalaması dengeye yaklaşır. Herkes pişmanlıksız oynarsa zaman ortalaması kaba korelasyonlu dengeye (CCE), iç pişmanlık küçültülürse korelasyonlu dengeye (CE), sıfır toplamlı oyunlarda minimaksa yaklaşır.
• Çok kollu haydutta yalnızca çekilen kolun ödülü görülür ve keşif–sömürü ikilemi doğar. ε-açgözlü ε olasılıkla rastgele keşfeder; sabit ε ile pişmanlığı doğrusal büyür. UCB1, Q + √(2 ln t / N) puanı en büyük kolu seçer; keşfi az denenen kollara yöneltir ve pişmanlığı logaritmik büyür (5000 turda 84'e 118).
• Q-öğrenme Q(s, a) ← Q(s, a) + α[r + γ · max Q(s′, ·) − Q(s, a)] ile durum–eylem değerlerini günceller; ödül hedeften geriye yayılır. Çoklu ajan ortamında ortam durağan olmadığı için tek ajanlı garantiler geçerliliğini yitirir.
• Replikatör dinamiğinde ortalamanın üstünde kazanan strateji yayılır: x_i′ = x_i f_i / f̄. Şahin–Güvercin'de her iç başlangıç ESS x* = V/C'ye gider; bu, simetrik karışık Nash dengesidir.
• Tekrarlanan Mahkûmun İkilemi'nde kinci tetik işbirliğini δ ≥ (cazibe − 3)/(cazibe − 1) iken korur (puanlar 5, 3, 1, 0 ile δ ≥ 1/2). Mini Axelrod turnuvasında Tit-for-Tat hiçbir maçı kazanmadan birinci olur; başarılı stratejiler iyi niyetli, misilleme yapan, affedici ve anlaşılırdır. Gürültüde cömert TFT ve WSLS daha iyidir.

13.10Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• en iyi tepki dinamiği best-response dynamics
• potansiyel oyun potential game
• kurgusal oyun fictitious play
• dışsal pişmanlık external regret
• iç pişmanlık internal / swap regret
• lideri izle follow the leader
• çarpımsal ağırlıklar (Hedge) multiplicative weights
• öğrenme oranı learning rate
• korelasyonlu denge correlated equilibrium
• kaba korelasyonlu denge coarse correlated equilibrium
• çok kollu haydut multi-armed bandit
• keşif–sömürü exploration–exploitation
• ε-açgözlü ε-greedy
• üst güven sınırı (UCB) upper confidence bound
• Thompson örneklemesi Thompson sampling
• EXP3 (çekişmeli haydut) adversarial bandit
• pekiştirmeli öğrenme reinforcement learning
• Q-öğrenme Q-learning
• iskonto faktörü discount factor
• durağan olmayan non-stationary
• karşı-olgusal pişmanlık minimizasyonu (CFR) counterfactual regret minimization
• replikatör dinamiği replicator dynamics
• uygunluk fitness
• evrimsel kararlı strateji (ESS) evolutionarily stable strategy
• kinci tetik stratejisi grim trigger strategy
• halk teoremi folk theorem
• Tit-for-Tat Tit-for-Tat
• şüpheci / cömert TFT suspicious / generous Tit-for-Tat
• kazan-kal, kaybet-değiş win-stay lose-shift

13.11Kendini Dene

1. Hücrelerde (u₁, u₂): (Üst, Sol) = (2, 1), (Üst, Sağ) = (0, 0), (Alt, Sol) = (0, 0), (Alt, Sağ) = (1, 2). Önce satır, sonra sütun oyuncusu hareket eden en iyi tepki dinamiği (Üst, Sağ)'dan başlarsa nerede durur? (Alt, Sol)'dan başlarsa? Bu oyun potansiyel oyun mudur?

   Cevap

   (Üst, Sağ)'dan: satır oyuncusu Sağ'a karşı Üst 0, Alt 1 görür ve Alt'a geçer: (Alt, Sağ). Sütun oyuncusu Alt'a karşı Sol 0, Sağ 2 görür; Sağ'da kalır. Dinamik (Alt, Sağ)'da durur. (Alt, Sol)'dan: satır oyuncusu Sol'a karşı Üst 2, Alt 0 görür ve Üst'e geçer: (Üst, Sol). Sütun oyuncusu Üst'e karşı Sol 1, Sağ 0 görür; kalır. Dinamik (Üst, Sol)'da durur. Varılan denge başlangıca bağlıdır. Oyun potansiyel oyundur: Φ(Üst, Sol) = 2, Φ(Üst, Sağ) = 1, Φ(Alt, Sol) = 0, Φ(Alt, Sağ) = 2 seçilirse her tek taraflı değişimde değişen oyuncunun kazanç farkı Φ farkına eşittir. Örneğin Sağ sütununda satır oyuncusu Üst'ten Alt'a geçince kazancı 0'dan 1'e, Φ 1'den 2'ye çıkar; Üst satırında sütun oyuncusu Sağ'dan Sol'a geçince kazancı 0'dan 1'e, Φ 1'den 2'ye çıkar.

2. İki eylemli Hedge'de η = ln 3, başlangıç ağırlıkları 1. Üç turun kazançları (1, 0), (0, 1), (1, 0)'dır. Her turun olasılıklarını, algoritmanın toplam beklenen kazancını ve dışsal pişmanlığı bulun.

   Cevap

   e^{ln 3} = 3: kazancı 1 olan eylemin ağırlığı üç katına çıkar. Tur 1: w = (1, 1), p = (½, ½), beklenen kazanç 0,5; güncelleme w = (3, 1). Tur 2: p = (3/4, 1/4), kazanç ¼ · 1 = 0,25; w = (3, 3). Tur 3: p = (½, ½), kazanç 0,5; son ağırlıklar (9, 3). Toplam 0,5 + 0,25 + 0,5 = 1,25. Sabit eylemler: A = 2, B = 1. Pişmanlık 2 − 1,25 = 0,75. 2. turda A'ya fazla güvenildi ve kazanan B çıktı.

3. Dört eylemli (n = 4) bir problemde Hedge 400 tur oynanacaktır. Sınırı en küçük yapan η, pişmanlık sınırı ve tur başına pişmanlık sınırı nedir? Tur sayısı dört katına çıkarsa (1600 tur) bu sayılar nasıl değişir?

   Cevap

   ln 4 ≈ 1,386. η = √(1,386/400) ≈ 0,059. Sınır 2√(400 · 1,386) = 2√554,5 ≈ 47,1; tur başına 47,1/400 ≈ 0,118. 1600 turda η yarıya iner (≈ 0,029), toplam sınır √4 = 2 katına çıkar (≈ 94,2), tur başına sınır yarıya iner (≈ 0,059).

4. İki kollu bir haydutta gerçek ortalamalar μ = (0,6; 0,4)'tür. İlk beş turda kol 0 dört kez çekilmiş (Q = 0,8), kol 1 bir kez çekilmiş (Q = 0,5). (a) t = 6'da UCB1 hangi kolu seçer? (b) Seçimden sonra çekiş sayıları N = (4, 2) olursa altı turun pişmanlığı kaçtır?

   Cevap

   (a) 2 ln 6 ≈ 3,58. Kol 0: 0,8 + √(3,58/4) = 0,8 + 0,95 ≈ 1,75. Kol 1: 0,5 + √3,58 = 0,5 + 1,89 ≈ 2,39. UCB1 kol 1'i seçer: tahmini düşük ama belirsizliği büyüktür. (b) R = 6 · 0,6 − (4 · 0,6 + 2 · 0,4) = 3,6 − 3,2 = 0,4. Pişmanlık gerçek ortalamalarla hesaplanır; gözlenen Q değerleri kullanılmaz.

5. Q-öğrenmede Q(s, a) = 0,5, r = 2, γ = 0,5, max Q(s′, ·) = 3, α = 0,2'dir. Hedef ve yeni Q(s, a) nedir? s′ bir hedef durum olsaydı (epizot bitseydi) sonuç ne olurdu?

   Cevap

   Hedef 2 + 0,5 · 3 = 3,5. Yeni değer 0,5 + 0,2 · (3,5 − 0,5) = 0,5 + 0,6 = 1,1. s′ hedef olsaydı gelecek değer 0 alınırdı: hedef 2, yeni değer 0,5 + 0,2 · 1,5 = 0,8.

6. Şahin–Güvercin'de V = 2, C = 8, taban 3'tür. Şahin payı x iken uygunlukları yazın, ESS'yi bulun ve x = 0,5'ten bir nesil sonraki şahin payını hesaplayın.

   Cevap

   Kazançlar: ŞŞ (2 − 8)/2 = −3, ŞG 2, GŞ 0, GG 1. f_Ş = 3 − 3x + 2(1 − x) = 5 − 5x, f_G = 3 + 1 · (1 − x) = 4 − x. Dinlenme noktası 5 − 5x = 4 − x ⇒ x* = 1/4 = V/C. x = 0,5'te f_Ş = 2,5, f_G = 3,5, f̄ = 3; x′ = 0,5 · 2,5/3 ≈ 0,417. Şahinler ortalamanın altında kazandığı için azalır ve 0,25'e doğru iner. Kavga pahalı olduğunda şahin payı küçüktür.

7. Bir tekrarlanan Mahkûmun İkilemi'nde puanlar cazibe 7, karşılıklı işbirliği 4, karşılıklı ihanet 2, enayi 0'dır. Kinci tetikle işbirliğinin sürmesi için gereken en küçük δ'yı türetin.

   Cevap

   Uymak 4/(1 − δ), sapmak 7 + 2δ/(1 − δ). (1 − δ) ile çarpınca 4 ≥ 7(1 − δ) + 2δ = 7 − 5δ, yani 5δ ≥ 3 ve δ ≥ 3/5. Genel kural: δ* = (cazibe − işbirliği)/(cazibe − ihanet) = (7 − 4)/(7 − 2). Karşılıklı ihanetin puanı yükseldiği için ceza daha hafiftir; eşik buna göre ayarlanır.

8. Kazan-kal, kaybet-değiş (WSLS; ilk turda S, 3 ya da 5 aldıysa aynı hamle, 0 ya da 1 aldıysa değiştir) altı tur boyunca Hep İhanet'e karşı oynuyor. Hamle dizisi ve puanlar nedir? TFT aynı maçta ne alırdı?

   Cevap

   Tur 1: WSLS S, rakip İ: 0 – 5; WSLS 0 aldığı için değiştirir. Tur 2: İ – İ: 1 – 1; 1 aldığı için yine değiştirir. Dizi S İ S İ S İ olur: WSLS 0 + 1 + 0 + 1 + 0 + 1 = 3, Hep İhanet 5 + 1 + 5 + 1 + 5 + 1 = 18. TFT ilk turdan sonra hep ihanet ederdi: 0 + 5 · 1 = 5'e 5 + 5 = 10. WSLS gürültüye karşı TFT'den güçlüdür ama koşulsuz ihanetçiye karşı her iki turda bir sömürülür.

13.12İleri okuma

• T. Roughgarden, Twenty Lectures on Algorithmic Game Theory (2016), Ders 16–18: pişmanlıksız öğrenme, Hedge'in pişmanlık sınırının ispatı, korelasyonlu dengeler ve minimaks teoreminin öğrenmeyle ispatı bilgisayar bilimi bakışıyla anlatılır.
• T. Lattimore ve C. Szepesvári, Bandit Algorithms (2020): ε-açgözlü, UCB, Thompson örneklemesi ve EXP3 algoritmalarının ayrıntılı analizini veren kapsamlı bir kaynaktır.
• R. Axelrod, The Evolution of Cooperation (1984): bilgisayar turnuvalarının hikâyesini, Tit-for-Tat'ın başarısını ve evrimsel turnuvaları matematik bilgisi gerektirmeden anlatır.
• D. Easley ve J. Kleinberg, Networks, Crowds, and Markets (2010), Bölüm 7: evrimsel oyun kuramını, ESS'yi ve Şahin–Güvercin benzeri örnekleri giriş düzeyinde sunar.

13.13Kaynaklar

1. P. Auer, N. Cesa-Bianchi, P. Fischer, “Finite-time analysis of the multiarmed bandit problem”, Machine Learning 47, 2002.
2. P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, “The nonstochastic multiarmed bandit problem”, SIAM Journal on Computing 32(1), 2002.
3. R. Axelrod, The Evolution of Cooperation, Basic Books, 1984.
4. A. Blum, Y. Mansour, “From external to internal regret”, JMLR 8, 2007.
5. N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games, Cambridge, 2006.
6. N. D. Daw, J. P. O’Doherty, P. Dayan, B. Seymour, R. J. Dolan, “Cortical substrates for exploratory decisions in humans”, Nature 441, 2006.
7. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge, 2010 (Bölüm 7: evrimsel oyun kuramı).
8. D. Foster, R. Vohra, “Calibrated learning and correlated equilibrium”, Games and Economic Behavior 21, 1997.
9. D. Fudenberg, D. Levine, The Theory of Learning in Games, MIT Press, 1998.
10. S. Hart, A. Mas-Colell, “A simple adaptive procedure leading to correlated equilibrium”, Econometrica 68(5), 2000.
11. J. Hofbauer, K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge, 1998.
12. A. R. Karlin, Y. Peres, Game Theory, Alive, AMS, 2017 (Bölüm 7: evrimsel denge; Bölüm 18: uyarlanabilir karar verme).
13. T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge, 2020.
14. J. Maynard Smith, G. R. Price, “The logic of animal conflict”, Nature 246, 1973.
15. K. Miyasawa, “On the convergence of the learning process in a 2×2 non-zero-sum two-person game”, Princeton Research Memo 33, 1961.
16. V. Mnih vd., “Human-level control through deep reinforcement learning”, Nature 518, 2015.
17. D. Monderer, L. S. Shapley, “Potential games”, Games and Economic Behavior 14(1), 1996.
18. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge, 2007 (Bölüm 4: öğrenme, pişmanlık ve denge).
19. M. Nowak, K. Sigmund, “A strategy of win-stay, lose-shift that outperforms tit-for-tat in the Prisoner’s Dilemma game”, Nature 364, 1993.
20. J. Robinson, “An iterative method of solving a game”, Annals of Mathematics 54(2), 1951.
21. T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge, 2016 (Ders 16–18).
22. L. S. Shapley, “Some topics in two-person games”, Advances in Game Theory, 1964.
23. W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples”, Biometrika 25, 1933.
24. C. Watkins, Learning from Delayed Rewards, doktora tezi, Cambridge Üniversitesi, 1989.
25. C. Watkins, P. Dayan, “Q-learning”, Machine Learning 8, 1992.
26. M. Zinkevich, M. Johanson, M. Bowling, C. Piccione, “Regret minimization in games with incomplete information”, NeurIPS, 2007.

Ders sayfası: Roughgarden CS364A · Araç: Nashpy (kurgusal oyun, replikatör dinamiği) · © Sercan Külcü. Tüm hakları saklıdır.