Keşif ve Sömürü Dengesi

Önceki iki derste politika elle yazıldı. Kural ne yapacağını baştan biliyordu, hiçbir sayı veriden öğrenilmedi, dolayısıyla öğrenmenin bir bedeli de yoktu. Politika öğrenilmeye başlandığında ise kursun ilk dersinde sayılan bir kısıt doğrudan bir çelişkiye dönüşür: ajan bir adımda yalnız seçtiği eylemin sonucunu görür, seçmediği beş eylem hakkında hiçbir şey duymaz. Bir eylemin ne kadar iyi olduğunu öğrenmenin tek yolu onu denemektir, ve her deneme o dönemin getirisinden düşer.

Sömürü, kestirimi en yüksek olan eylemi seçmektir; o anki bilgiyi paraya çevirir. Keşif, kestirimi düşük ya da hiç olmayan bir eylemi seçmektir; bugünün getirisini bilgiye çevirir. Bu ders çelişkiyi bir düğme hâline getirir, düğmeyi süpürür ve iki yönü de sayar: kaç adım kaybedilerek kaç adım kazanılıyor.

• PO18. Kurgu, ufuk, indirim katsayısı ve tohum 01–02’den aynen sürer. Beş abone, tek ekip, aynı kötüleşme olasılıkları, 243 durum, 6 eylem, 30 dönemlik bölüm.
• PO19. Bu derste kestirim anlık ödülün ortalamasıdır. Her durum-eylem çifti için o çiftte görülen ödüllerin ortalaması tutulur; getiriye ve zaman farkına sonraki ders geçer.
• PO20. Keşif biçimi tek bir orandır. Olasılık $\varepsilon$ ile eylem ayrım gözetmeden seçilir, kalan durumlarda kestirimi en yüksek olan seçilir; eşitlik en küçük numarayla bozulur.
• PO21. Kaçırılan kazanç, keşif adımlarının anlık bedelidir: her adımda, açgözlü eylemin o adımda vereceği ödül ile gerçekten alınan ödül arasındaki fark biriktirilir. Sömürü adımlarında bu fark tam olarak sıfırdır, keşif adımlarında ise eksi de çıkabilir.
• PO22. Kestirimlerin ilk değeri bir tercihtir ve bu ders onu da ölçer. Karamsar ilk değer $-5{,}0$’tır ve olası bütün ödüllerin altındadır; iyimser ilk değer $0{,}0$’dır ve boşa giden bir ziyaretin ödülü olan $-2$’nin üstündedir.
• PO23. Eğitim 300 bölüm, yani 9.000 adımdır. Ardından çizelge dondurulur ve öğrenilen açgözlü politika, 01’deki aynı 300 bölüm tohumunda ölçülür; sayılar 10,432 ve 20,621 ile aynı ölçektedir.
• PO24. Süpürülen keşif oranları yedi adaydır: 0,00, 0,02, 0,05, 0,10, 0,20, 0,40 ve 1,00.
• PO25. Ölçüt üçlüdür ve hep yan yana basılır: dondurulmuş politikanın getirisi, biriken kaçırılan kazanç, ve hiç denenmeyen eylem sayısı. Eğitimde hiç görülmemiş bir durumla karşılaşıldığında bütün kestirimler eşittir ve en küçük numaralı eylem seçilir.

Hep Sömüren Ajan

# ortam.py — KURGUDUR. Saha ziyareti planlamasi onceki iki dersten aynen surer:
# bes abone, her donem tek ekip, tohum 20260218.
import statistics

TOHUM, M32 = 20260218, 0xFFFFFFFF
ABONE, KAZANC, MALIYET = 5, (0, 3, 9), 2
KOTULESME = (0.30, 0.05, 0.60, 0.15, 0.45)
ETIKET = ("A1", "A2", "A3", "A4", "A5", "cikma")
EYLEM, UFUK, INDIRIM = ABONE + 1, 30, 0.9


def uretec(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def sonraki():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return sonraki


class Ortam:
    def __init__(self, tohum):
        self.r = uretec(tohum)
        self.d, self.g = [0] * ABONE, [0] * ABONE
        for i in range(ABONE):
            self.g[i] = int(self.r() * 6)
            for _ in range(self.g[i]):
                if self.d[i] < 2 and self.r() < KOTULESME[i]:
                    self.d[i] += 1

    def durum(self):
        return tuple(min(2, x // 3) for x in self.g)

    def adim(self, a):
        odul = 0.0
        if a < ABONE:
            odul = KAZANC[self.d[a]] - MALIYET
            self.d[a] = 0
            self.g[a] = 0
        for i in range(ABONE):
            if i != a:
                self.g[i] += 1
                if self.d[i] < 2 and self.r() < KOTULESME[i]:
                    self.d[i] += 1
        return self.durum(), odul


def kosum(politika, n=300):
    G = []
    for k in range(n):
        o = Ortam(TOHUM + 1000 * k)
        s, g, c = o.durum(), 0.0, 1.0
        for _ in range(UFUK):
            s, r = o.adim(politika(s, o))
            g, c = g + c * r, c * INDIRIM
        G.append(g)
    return G


def egit(kesif, ilk, n_bolum=300, tohum=TOHUM + 11):
    """Her durum-eylem cifti icin ANLIK odulun ortalamasi tutulur."""
    r = uretec(tohum)
    Q, N, kacan, kesif_adim = {}, {}, 0.0, 0
    for k in range(n_bolum):
        o = Ortam(TOHUM + 1000 * k)
        s = o.durum()
        for _ in range(UFUK):
            q = Q.setdefault(s, [ilk] * EYLEM)
            n = N.setdefault(s, [0] * EYLEM)
            ac = max(range(EYLEM), key=lambda i: q[i])
            a = int(r() * EYLEM) if r() < kesif else ac
            beklenen = KAZANC[o.d[ac]] - MALIYET if ac < ABONE else 0.0
            s2, odul = o.adim(a)
            kacan += beklenen - odul
            kesif_adim += (a != ac)
            n[a] += 1
            q[a] += (odul - q[a]) / n[a]
            s = s2
    return Q, N, kacan, kesif_adim


def dondur(Q, ilk):
    """Ogrenme biter, cizelge donar; politika artik acgozludur."""
    def pol(s, o):
        q = Q.get(s, [ilk] * EYLEM)
        return max(range(EYLEM), key=lambda i: q[i])
    return pol


ILK = -5.0
Q0, N0, kacan0, kesif0 = egit(0.00, ILK)
denenen = [sum(N0[s][a] for s in N0) for a in range(EYLEM)]
print(f"kesif orani 0.00, kestirimlerin ilk degeri {ILK}")
print(f"  ogrenilen politikanin getirisi {statistics.mean(kosum(dondur(Q0, ILK))):.3f}")
print(f"  biriken kacirilan kazanc {kacan0:.1f}; kesif adimi {kesif0}")
print(f"  gorulen durum {len(N0)}/243; denenen durum-eylem cifti "
      f"{sum(1 for v in N0.values() for x in v if x > 0)}/1458")
print("  eylem basina deneme sayisi: "
      + ", ".join(f"{ETIKET[a]}={denenen[a]}" for a in range(EYLEM)))

kesif orani 0.00, kestirimlerin ilk degeri -5.0
  ogrenilen politikanin getirisi -16.492
  biriken kacirilan kazanc 0.0; kesif adimi 0
  gorulen durum 95/243; denenen durum-eylem cifti 95/1458
  eylem basina deneme sayisi: A1=9000, A2=0, A3=0, A4=0, A5=0, cikma=0

Hiç keşif yapmayan ajanın 9.000 adımı tek bir eylemde geçiyor. Nedeni tek satırda okunur: başlangıçta bütün kestirimler $-5{,}0$’tır, eşitlik en küçük numarayla bozulur, ilk eylem A1 olur ve A1’in gerçek ödülü ne çıkarsa çıksın $-5{,}0$’ın üstündedir. Kestirim yükselir, A1 artık tek başına en yüksektir ve bir daha hiçbir şey onu geçemez, çünkü öteki beş eylem hiç denenmediği için kestirimleri $-5{,}0$’ta durur. A2, A3, A4, A5 ve ekip çıkarmama seçeneği hiç denenmiyor: altı eylemden beşi.

Sonuç getiride görünüyor. Politika $-16{,}492$ alıyor; hiç ekip çıkarmamanın 0,000’ının ve rastgele eylemin 10,432’sinin çok altında. Ajan her dönem A1’e gidiyor, A1 çoğunlukla bir dönem önce onarıldığı için temiz bulunuyor ve her ziyaret 2 birim yazıyor. Sayı da bunu doğruluyor: otuz dönem boyunca kesintisiz $-2$ almanın indirimli toplamı $-19{,}152$’dir, ölçülen $-16{,}492$ ise aradaki payı A1’in arada bir kötüleşip 1 ya da 7 vermesinden alıyor. Toplanan veri de daralıyor: 243 durumun 95’i görülüyor ve 1.458 çiftin yalnız 95’i deneniyor. Bu 95 çift, 95 durumun her birinde tek bir eylem demektir — hep aynı eylem.

Kaçırılan kazanç ise tam olarak 0,0. Bu bir başarı değil, ölçünün tanımıdır: kaçırılan kazanç keşif adımlarının anlık bedelini sayar, keşif adımı da hiç yoktur. Bir sistemin kaçırılan kazancının sıfır olması, o sistemin iyi olduğunu değil, hiçbir şey öğrenmediğini söyler. İki sayı ancak yan yana anlam taşır.

Keşif Oranının Süpürülmesi

# supurme.py — Yedi kesif orani, ayni butce (300 bolum, 9.000 adim), ayni
# ufuk, ayni karamsar ilk deger. Ogrenilen politika sonra dondurulup olculur.
print(f"{'kesif':>6}{'getiri':>9}{'kacan':>10}{'kesif adimi':>13}"
      f"{'durum':>8}{'cift':>7}{'hic denenmeyen eylem':>22}")
for kesif in (0.00, 0.02, 0.05, 0.10, 0.20, 0.40, 1.00):
    Q, N, kacan, ka = egit(kesif, ILK)
    say = [sum(N[s][a] for s in N) for a in range(EYLEM)]
    hic = [ETIKET[a] for a in range(EYLEM) if say[a] == 0]
    cift = sum(1 for v in N.values() for x in v if x > 0)
    print(f"{kesif:>6.2f}{statistics.mean(kosum(dondur(Q, ILK))):>9.3f}{kacan:>10.1f}"
          f"{ka:>13}{len(N):>8}{cift:>7}{(','.join(hic) if hic else '-'):>22}")

 kesif   getiri     kacan  kesif adimi   durum   cift  hic denenmeyen eylem
  0.00  -16.492       0.0            0      95     95     A2,A3,A4,A5,cikma
  0.02   16.716     -76.0          150     127    237                     -
  0.05   22.210     402.0          364     143    335                     -
  0.10   23.606    1210.0          748     176    472                     -
  0.20   25.659    3545.0         1500     185    578                     -
  0.40   25.997    8358.0         2945     217    839                     -
  1.00   23.000   33811.0         7494     235   1237                     -

Getiri sütunu tek tepeli bir eğri çiziyor. Sıfır keşifte $-16{,}492$, 0,40’ta en yüksek değeri 25,997, 1,00’de yeniden 23,000. İki uç iki ayrı nedenle kötüdür. Solda ajan öğrenmez, çünkü denemez. Sağda ajan her adımı ayrım gözetmeden seçtiği için topladığı veri iyi ama davranışı kötüdür; yine de dondurulan çizelge 23,000 verir, yani kötü davranışla iyi veri toplanabilir — bir sonraki kursun temel gerilimi burada tohum hâlinde duruyor.

Asıl okuma iki sütun arasındadır. 0,20 oranı 25,659 getiri veriyor ve bedeli 3.545 kaçırılan kazanç. 0,40 oranı yalnız 0,338 daha fazla getiri veriyor ama bedeli 8.358, yani iki kattan fazla. Keşifle satın alınan getiri azalarak artıyor; her ek keşif adımı bir öncekinden daha az bilgi getiriyor, oysa bedeli aynı kalıyor. 1,00’e gidildiğinde 33.811 kaçırılan kazanç ödenip getiri düşüyor.

0,02 satırındaki eksi işaret bir hata değil, ölçünün kendisidir. 150 keşif adımının toplam bedeli $-76{,}0$: keşif adımları ortalamada açgözlü eylemden daha iyi ödül getirmiş. Bunun nedeni açgözlü eylemin o aşamada A1’e kilitlenmiş olmasıdır; A1’e gitmek çoğunlukla $-2$ yazarken ayrım gözetmeden seçilen eylem sık sık daha iyisini bulmuştur. Kötü bir politika sömürülürken keşfin bedeli eksiye düşer. Bedel ancak sömürülen politika gerçekten iyiyken artıya geçer, ve tablodaki artış tam olarak bunu izliyor.

Denenen çift sütunu bir uyarı da taşıyor. En cömert keşifte bile 1.458 çiftin 1.237’si deneniyor, yani 221’i hiç denenmiyor, ve görülen durum 235’te kalıyor. Dondurulan politika kalan 8 durumla karşılaşırsa bütün kestirimleri eşit bulur ve en küçük numaralı eylemi seçer. Bu, öğrenilen sayının nerede geçerli olduğunu da tanımlıyor: çizelgenin dolu olduğu bölge kadar.

Sağdaki iki sütun kursun üçüncü sayısını taşıyor. Keşif oranı arttıkça görülen durum 95’ten 235’e, denenen çift 95’ten 1.237’ye çıkıyor. Keşif bir bedel ödemekten ibaret değil; topladığı veriyi genişletiyor ve genişleyen veri, dondurulan çizelgenin daha çok hücresinde bir sayı bulunmasını sağlıyor. Ayar değişkeni araması bu ölçünün dışındadır ve tekrarlanmaz: M27/K03’ün model değerlendirme konusunda kurulan aday süpürmesinde aday sayısı artırıldığında ödenen şey hesaplama bütçesiydi, veri baştan sona sabit duruyordu ve arama bittikten sonra hiçbir kayıp kalmıyordu. Burada ödenen şey getirinin kendisidir: her keşif adımı gerçekten yaşanmış bir dönemdir, geri alınamaz, ve o dönemde toplanan veriyi de kalıcı olarak değiştirir.

Keşif Rastgelelikten Gelmek Zorunda Değil

# ilkdeger.py — Ayni supurme, iki ayri ilk deger. Karamsar ilk deger denenmemis
# eylemi kotu gosterir; iyimser ilk deger onu denemeye deger gosterir.
print(f"{'ilk deger':>10}{'kesif':>7}{'getiri':>9}{'kacan':>10}{'cift':>7}")
for ilk in (-5.0, 0.0):
    for kesif in (0.00, 0.05, 0.20):
        Q, N, kacan, ka = egit(kesif, ilk)
        cift = sum(1 for v in N.values() for x in v if x > 0)
        print(f"{ilk:>10.1f}{kesif:>7.2f}"
              f"{statistics.mean(kosum(dondur(Q, ilk))):>9.3f}{kacan:>10.1f}{cift:>7}")

 ilk deger  kesif   getiri     kacan   cift
      -5.0   0.00  -16.492       0.0     95
      -5.0   0.05   22.210     402.0    335
      -5.0   0.20   25.659    3545.0    578
       0.0   0.00   26.212       0.0    356
       0.0   0.05   26.155     772.0    496
       0.0   0.20   26.378    4147.0    636

Alt üç satır üstteki bütün tabloyu yeniden okutuyor. Keşif oranı yine 0,00 iken getiri $-16{,}492$ değil 26,212, kaçırılan kazanç yine tam 0,0, denenen çift 95 değil 356. Hiçbir rastgele adım atılmadan keşif olmuş.

Nedeni ilk değerdedir. Denenmemiş bir eylemin kestirimi $0{,}0$’dır; boşa giden bir ziyaretin gerçek ödülü $-2$’dir. Ajan bir eylemi deneyip $-2$ aldığında o eylemin kestirimi denenmemiş eylemlerin altına düşer ve açgözlü seçim kendiliğinden bir sonrakine kayar. Kestirim gerçeğin üstünde başladığı sürece açgözlülüğün kendisi keşif üretir; hayal kırıklığı sıradaki eylemi gündeme getirir. Karamsar ilk değerde ise tersi olur: ilk denenen eylem ne verirse versin denenmemişlerin üstüne çıkar ve kapı kapanır.

Bu, kaçırılan kazancı sıfır tutan bir keşif düzeneğidir, ama bedava değildir. İlk değerin gerçek ödüllerin üstünde olması gerekir, bu da ödüllerin ölçeği hakkında önceden bilgi ister; kurguda 0,0’ın işe yaraması, boşa ziyaretin $-2$ yazdığını bilmemizdendir. Ayrıca etkisi geçicidir: her hücre bir kez denendikten sonra iyimserlik tükenir ve ortam zamanla değişirse yeniden keşif gerekir. Oranla yapılan keşif ise kalıcıdır ve her adımda ödenir. Tablodaki 4.147 ile 0,0 farkı bu iki düzeneğin bedelini aynı birimde yan yana koyuyor.

Özet

• Sömürü kestirimi en yüksek eylemi seçer, keşif kestirimi belirsiz olanı dener; ajan bir adımda yalnız seçtiği eylemin sonucunu gördüğü için ikisi aynı anda yapılamaz.
• Karamsar ilk değerle hiç keşif yapmayan ajan 9.000 adımın tamamını A1’de geçirir, altı eylemden beşini hiç denemez, 243 durumun 95’ini görür ve $-16{,}492$ getiri alır.
• Kaçırılan kazancın 0,0 olması iyi bir işaret değildir: keşif adımı olmadığı için tanımı gereği sıfırdır ve getiriyle yan yana okunmadan bir şey söylemez.
• Keşif oranı 0,00’dan 1,00’a süpürüldüğünde getiri $-16{,}492$’den 25,997’ye çıkıp 23,000’e düşer; bedel 0,0’dan 33.811,0’a tırmanır. 0,20 oranı en iyi getirinin 0,338 altında kalırken bedelin yalnız 0,424’ünü öder.
• Düşük keşif oranında kaçırılan kazanç eksiye düşebilir ($-76{,}0$), çünkü sömürülen politika o aşamada kötüdür ve ayrım gözetmeden seçilen eylem ortalamada ondan iyi çıkar.
• Kestirimlerin ilk değeri de bir keşif düzeneğidir: iyimser başlangıçla hiç rastgele adım atmadan getiri 26,212’ye, denenen çift 95’ten 356’ya çıkar ve kaçırılan kazanç 0,0 kalır.

Sonraki Adım

Bu derste tutulan sayı anlık ödülün ortalamasıydı: bir durumda bir eylemin o dönem ne getirdiği. Oysa ilk derste getiri otuz dönemin indirimli toplamı olarak tanımlanmıştı ve bir ziyaretin asıl etkisi o dönemde bitmiyor — onarılan abone birkaç dönem daha temiz kalıyor, ihmal edilen abone birkaç dönem sonra daha pahalıya patlıyor. Anlık ödüle bakan bir kestirim bu zinciri hiç görmez, bu yüzden 26,378’de takılır. Sonraki ders çizelgede tutulan sayıyı anlık ödülden getiriye çevirir: bir durumun değeri, oradan sonra toplanabilecek indirimli ödüllerin toplamıdır, ve bu sayı ardışık iki kestirimin farkından adım adım öğrenilebilir. Ölçü yine toplanan veriden okunacak: çizelgenin kaç hücresi 9.000 adımın sonunda hiç güncellenmemiş kalıyor.