Karar Süreci Biçimselleştirmesi

Önceki ders döngüyü kurdu ve dört adı kullandı: durum, eylem, geçiş, ödül. Hiçbiri tanımlanmadı. Adların bir tanımı olduğunda ise tanım tek bir koşula dayanır, ve o koşul önceki dersin son satırında zaten zorlanıyordu: A1’in gecikme sınıfı 2 iken bulunan kademe temiz çıkmış ve ödül $-2$ olmuştu, oysa aynı sınıfla başka bir bölümde 7 çıkabilirdi.

Bu ders kurulumu biçimsel bir beşliye oturtur, beşlinin tanımlayıcı koşulunu yazar ve o koşulun kurguda tam tutmadığını ölçer. Sonra da bunun bedelini ödetir: koşul zayıfladığında politika ne kaybediyor, duruma bir geçmiş alanı eklenince ne kadarı geri geliyor.

• PO10. Kurgu 01’den aynen sürer. Beş abone, tek ekip, aynı kötüleşme olasılıkları, aynı ödül çizelgesi, aynı 30 dönemlik ufuk, aynı indirim katsayısı 0,9 ve aynı tohum. Kurgu olduğu yeniden yazılır: hiçbir sayı gerçek bir kayıttan gelmez.
• PO11. Karar süreci bir beşlidir: durum kümesi $S$, eylem kümesi $A$, geçiş, ödül ve indirim katsayısı $\gamma$. Kurguda $\lvert S \rvert = 243$, $\lvert A \rvert = 6$, $\gamma = 0{,}9$.
• PO12. Geçiş ve ödül birer dağılımdır, tek bir sayı değil. Aynı durumda aynı eylem, farklı ardıl durumlar ve farklı ödüller verebilir.
• PO13. Tanımlayıcı koşul: ardıl durumun ve ödülün dağılımı yalnız o anki duruma ve seçilen eyleme bağlıdır; daha eski durumlar, daha eski eylemler ve geçen süre hiçbir şey eklemez. Bu koşula geçmişten bağımsız geçiş denir.
• PO14. Koşul kurguda tam tutmaz ve bu ders bunu ölçer. Ortamın gizli kademe vektörü koşulu taşır; ajanın gördüğü gecikme sınıfı vektörü onun bir izdüşümüdür ve taşımaz.
• PO15. Sınama biçimi: aynı durum-eylem hücresindeki ödül örnekleri, durumun taşımadığı bir geçmiş alanına göre ikiye bölünür. Ortalamalar ayrışıyorsa koşul o hücrede bozulmuştur.
• PO16. Geçmiş alanı, en uzun süredir ziyaret edilmemiş abonenin numarasıdır. Eklendiğinde durum uzayı 243’ten 1.215’e çıkar.
• PO17. Üst referans gizli kademeyi doğrudan gören politikadır. Ulaşılabilir değildir; yalnız izdüşümün ne kadarını kaybettirdiğini sınırlamak için basılır. İz 600 bölüm, 18.000 adımdır.

Beşli

# ortam.py — KURGUDUR. Saha ziyareti planlamasi bir onceki dersten aynen surer:
# bir bolgedeki bes abone, her donem tek ekip, tohum 20260218.
import statistics
from collections import Counter, defaultdict

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 kural(s, o):
    """Gecikme sinifi en buyuk aboneyi ziyaret et; hepsi 0 ise ekip cikarma."""
    en = max(s)
    return ABONE if en == 0 else s.index(en)


def iz_topla(politika, n=600):
    """Her adimda ziyaret edilen abonenin TAM gecikmesini de kaydeder."""
    iz = []
    for k in range(n):
        o = Ortam(TOHUM + 1000 * k)
        s = o.durum()
        for _ in range(UFUK):
            a = politika(s, o)
            gec = o.g[a] if a < ABONE else -1
            s2, r = o.adim(a)
            iz.append((s, a, r, s2, gec))
            s = s2
    return iz


IZ = iz_topla(kural)
S, A = (0, 0, 1, 1, 0), 2
alt = [(r, s2, g) for s, a, r, s2, g in IZ if s == S and a == A]
print(f"durum kumesi {3 ** ABONE}, eylem kumesi {EYLEM}, ufuk {UFUK}, indirim {INDIRIM}")
print(f"iz {len(IZ)} adim; ornek hucre {S} eylem {ETIKET[A]}, {len(alt)} ornek")
print("ardil durum dagilimi (ilk dort):")
for s2, n in Counter(x[1] for x in alt).most_common(4):
    print(f"   {s2}  {n / len(alt):.4f}")
print("odul dagilimi:")
for r, n in sorted(Counter(x[0] for x in alt).items()):
    print(f"   {r:>5.1f}  {n / len(alt):.4f}")

durum kumesi 243, eylem kumesi 6, ufuk 30, indirim 0.9
iz 18000 adim; ornek hucre (0, 0, 1, 1, 0) eylem A3, 2113 ornek
ardil durum dagilimi (ilk dort):
   (1, 0, 0, 1, 0)  0.4307
   (0, 0, 0, 2, 1)  0.2239
   (0, 1, 0, 1, 0)  0.1770
   (0, 0, 0, 1, 1)  0.1046
odul dagilimi:
    -2.0  0.0516
     1.0  0.2347
     7.0  0.7137

Beşli beş nesneden kuruludur. Durum kümesi $S$: gecikme sınıfı vektörlerinin tamamı, 243 öge. Eylem kümesi $A$: altı öge. Geçiş: bir durum-eylem çiftine, ardıl durumlar üzerinde bir dağılım karşılık getirir. Ödül: aynı çifte, sayılar üzerinde bir dağılım karşılık getirir. İndirim katsayısı $\gamma = 0{,}9$: gelecekteki ödüllerin bugünkü ağırlığı.

Çıktı geçişin ve ödülün niçin birer dağılım olduğunu tek bir hücrede gösteriyor. Durum $(0, 0, 1, 1, 0)$ iken A3 ziyaret edildiğinde 2.113 örnek toplanmış ve ardıl durum en az dört ayrı değer almış: en sık geleni 0,4307 payla $(1, 0, 0, 1, 0)$. Fark A1’in ve A4’ün o dönem kötüleşip kötüleşmemesinden gelir, ve bu bir çekilişin sonucudur. Ödül de üç değere yayılıyor: 0,7137 payla 7, 0,2347 payla 1, 0,0516 payla $-2$. Ajanın yaptığı seçim aynı, sonucu üç ayrı sayı.

Üç ödül değerinin ne anlama geldiği kurgudan okunur: 7, arızalı bulunup onarılmış bir aboneyi, 1 şüpheli bulunmuşu, $-2$ temiz bulunmuşu gösterir. A3’ün dönem başına kötüleşme olasılığı 0,60’tır ve gecikme sınıfı 1, en az üç dönem geçtiği anlamına gelir; bu yüzden ziyaretlerin 0,7137’sinde arıza bulunur. Aynı sınıf A2 için okunsaydı payların yeri değişirdi, çünkü A2’nin olasılığı 0,05’tir. Ödül dağılımı eylemin kimliğine de, durumun içeriğine de bağlıdır.

Ardıl durumların listesi de kurgudan çıkar. A3 ziyaret edildiği için onun gecikmesi sıfırlanır ve sınıfı 0’a düşer; geri kalan dört abonenin gecikmesi bir artar. Bir artış sınıfı yalnız kova sınırında değiştirir, dolayısıyla ardıl durumların hangi bileşende ayrıldığı, o dönem hangi abonelerin kova sınırını geçtiğine bakar. Dört satırın toplamı 0,9362; kalan pay daha seyrek görülen ardıllara dağılmıştır.

Bu dağılımlar bir kusur değildir. Beşlinin tanımı ödülün sabit olmasını değil, dağılımının sabit olmasını ister. Kusur, dağılımın sabit olmadığı yerdedir.

Geçmişten Bağımsızlık

# gecmis.py — Sinama: ayni (durum, eylem) hucresindeki odul ornekleri, durumun
# tasimadigi bir gecmis alanina gore ikiye bolunuyor. Ortalamalar ayrisiyorsa
# odul o hucrede tek bir dagilima oturmuyor demektir.
hucre = defaultdict(list)
for s, a, r, s2, g in IZ:
    hucre[(s, a)].append((r, g))

print(f"{'durum':<17}{'eylem':<7}{'ornek':>7}{'ort odul':>10}"
      f"{'gecikme 3':>11}{'gecikme 4+':>12}{'fark':>8}")
for (s, a), v in sorted(hucre.items(), key=lambda kv: -len(kv[1]))[:5]:
    k = [r for r, g in v if g == 3]
    u = [r for r, g in v if g >= 4]
    print(f"{str(s):<17}{ETIKET[a]:<7}{len(v):>7}"
          f"{statistics.mean(r for r, _ in v):>10.3f}"
          f"{statistics.mean(k):>11.3f}{statistics.mean(u):>12.3f}"
          f"{statistics.mean(u) - statistics.mean(k):>8.3f}")

durum            eylem    ornek  ort odul  gecikme 3  gecikme 4+    fark
(0, 0, 1, 1, 0)  A3        2113     5.127      4.518       5.944   1.425
(1, 0, 0, 1, 0)  A1        1945     1.540      1.198       2.436   1.238
(0, 1, 0, 1, 0)  A2        1899    -1.455     -1.502      -1.341   0.162
(1, 0, 0, 0, 1)  A1        1659     1.204      1.132       2.154   1.022
(0, 1, 0, 0, 1)  A2        1613    -1.481     -1.530      -0.971   0.558

Sınamanın kurgusu şudur. Gecikme sınıfı 1, “son ziyaretten bu yana 3, 4 ya da 5 dönem geçti” demektir; üç değer tek bir sınıfa katlanır. Durum bu katlanmadan sonra elde kalandır, yani ajan gecikmenin 3 mü 5 mi olduğunu göremez. Ama ortam görür: kötüleşme her dönem yeniden çekilir, dolayısıyla 5 dönem beklemiş bir abonenin arızalı bulunma olasılığı 3 dönem beklemişten yüksektir.

Tablo bunu sayıya çeviriyor. En çok görülen hücrede — durum $(0, 0, 1, 1, 0)$, eylem A3, 2.113 örnek — ortalama ödül 5,127. Aynı hücre gecikmeye göre ikiye bölündüğünde 4,518 ile 5,944 çıkıyor: fark 1,425. Beş hücrenin beşinde de fark artı yönde, en küçüğü 0,162, en büyüğü 1,425. Durum ve eylem sabit tutulduğu hâlde ödülün ortalaması durumun taşımadığı bir geçmiş bilgisine göre kayıyor. Koşul bu kurguda tam tutmuyor, ve tutmadığı miktar ödül biriminden okunabiliyor.

Farkın hücreden hücreye değişmesi de okunmayı hak ediyor. En küçük iki fark, 0,162 ve 0,558, A2’ye gidilen hücrelerdedir; A2’nin kötüleşme olasılığı 0,05’tir, dolayısıyla bir dönem daha beklemek onun kademesini neredeyse hiç oynatmaz ve katlanan bilgi de neredeyse hiçbir şey taşımaz. En büyük fark A3’tedir, olasılığı 0,60 olan abonede. Yani izdüşümün ne kadar bilgi attığı sabit bir sayı değildir: durumun aynı kovası, hızlı kötüleşen bir abone için çok, yavaş kötüleşen için az saklar.

İki şey karıştırılmamalı. Ortamın kendisi geçmişten bağımsızdır: gizli kademe vektörü bir sonraki kademeyi ve ödülü belirlemek için yeterlidir, ondan öncesi hiçbir şey eklemez. Bozulan şey ortam değil, ajanın durum tanımıdır. Gecikme sınıfı vektörü gizli vektörün kaba bir izdüşümüdür ve izdüşüm alınırken atılan bilgi, atıldığı için yok olmaz — geçmişin içinde durur ve oradan ödülü oynatır. Bu, uygulamada karşılaşılan biçimin ta kendisidir: beşli genellikle ortamda tutar, ajanın eline geçen gözlemde tutmaz.

Durum Tanımının Bedeli

# tanim.py — Ayni kural, uc durum tanimi. Kuralin metni degismiyor; degisen,
# kuralin okuyabildigi alan.
def kural_gecmisli(s, o):
    """Gecmis alani: en uzun suredir ziyaret edilmemis abonenin numarasi."""
    en = max(s)
    if en == 0:
        return ABONE
    aday = [i for i in range(ABONE) if s[i] == en]
    uzun = max(range(ABONE), key=lambda i: o.g[i])
    return uzun if uzun in aday else aday[0]


def gizli_politika(s, o):
    """Ulasilamaz ust referans: ortamin gizli kademe vektorunu dogrudan okur."""
    en = max(o.d)
    return ABONE if en == 0 else o.d.index(en)


print(f"{'durum tanimi':<34}{'uzay':>7}{'getiri':>9}")
for ad, pol, uzay in (("gecikme sinifi", kural, 243),
                      ("gecikme sinifi + gecmis alani", kural_gecmisli, 1215),
                      ("gizli kademe (ust referans)", gizli_politika, 243)):
    print(f"{ad:<34}{uzay:>7}{statistics.mean(kosum(pol)):>9.3f}")

durum tanimi                         uzay   getiri
gecikme sinifi                        243   20.621
gecikme sinifi + gecmis alani        1215   23.148
gizli kademe (ust referans)           243   29.053

Üç satırın da okunacağı taban çizgisi önceki derstendir ve burada yeniden ölçülmez: rastgele eylem 10,432, hiç ekip çıkarmamak 0,000. Üç satır da bu tabanın üstündedir; aralarındaki fark tabanla aralarındaki farkın yanında küçüktür ve bu dersin ölçtüğü şey o küçük farktır.

Üç satırda kural aynıdır: gecikme sınıfı en büyük olan aboneye git. Değişen tek şey, kuralın eşitlik durumunda neye bakabildiğidir. İlk satırda sınıf eşitse abone numarası küçük olan seçilir, çünkü başka bilgi yoktur ve getiri 20,621’dir. İkinci satırda duruma tek bir alan eklenir — en uzun süredir ziyaret edilmemiş abonenin numarası — ve eşitlik o alana göre bozulur. Getiri 23,148 olur: +2,527, yani yüzde 12,3’lük bir artış, tek bir alan karşılığında.

Üçüncü satır kaybın büyüklüğünü sınırlıyor. Gizli kademeyi doğrudan okuyan politika 29,053 alıyor. İzdüşümün açtığı toplam açıklık $29{,}053 - 20{,}621 = 8{,}432$; geçmiş alanı bunun 2,527’sini, yani 0,300’ünü kapatıyor. Kalan 5,905 gecikmeden okunamaz, çünkü kötüleşme bir çekiliştir ve iki abone aynı gecikmeyle iki ayrı kademede olabilir.

Alanın bedeli sütununda yazılı. Durum uzayı 243’ten 1.215’e, beş katına çıkıyor. Bu ders bir el kuralı kullandığı için bedel görünmüyor; kural durumu okur ve çizelge tutmaz. Bir sonraki iki derste durum başına bir sayı öğrenilecek ve o zaman 243 ile 1.215 arasındaki fark doğrudan öğrenme hızına dönüşecek: her hücrenin dolması için o hücrenin ziyaret edilmesi gerekir. Durum tanımını zenginleştirmek bedava değildir; geçmişten bağımsızlığa yaklaşmak için ödenen bedel, her durumun daha seyrek görülmesidir.

Özet

• Karar süreci bir beşlidir: durum kümesi (243 öge), eylem kümesi (6 öge), geçiş, ödül ve indirim katsayısı (0,9). Geçiş ve ödül birer sayı değil, birer dağılımdır.
• Tek bir hücrede — durum $(0, 0, 1, 1, 0)$, eylem A3 — ardıl durum dört ayrı değere 0,4307, 0,2239, 0,1770 ve 0,1046 payla, ödül ise $-2$, 1 ve 7’ye 0,0516, 0,2347 ve 0,7137 payla dağılır.
• Tanımlayıcı koşul, ardıl durumun ve ödülün dağılımının yalnız o anki duruma ve eyleme bağlı olmasıdır; buna geçmişten bağımsız geçiş denir.
• Koşul kurguda tam tutmaz: aynı hücrede ortalama ödül gecikme 3 iken 4,518, gecikme 4 ve üzeriyken 5,944’tür; fark 1,425 ve beş hücrenin beşinde de aynı yöndedir.
• Bozulan ortam değil ajanın durum tanımıdır. Gizli kademe vektörü koşulu taşır, gecikme sınıfı vektörü onun kaba bir izdüşümüdür.
• Aynı kural 243 durumlu tanımda 20,621, geçmiş alanı eklenmiş 1.215 durumlu tanımda 23,148, gizli kademeyi gören üst referansta 29,053 alır; geçmiş alanı açıklığın 0,300’ünü kapatır.

Sonraki Adım

Bu iki derste politika elle yazıldı: kuralın ne yapacağı baştan belliydi ve hiçbir sayı veriden öğrenilmedi. Bir politikanın öğrenilmesi gerektiğinde ise yeni bir çelişki doğar. Öğrenmek için eylemlerin karşılığını görmek gerekir, karşılığını görmek için o eylemi denemek gerekir, ve her deneme o dönemin getirisinden düşer. Önceki derste görüldüğü gibi ajan bir adımda yalnız seçtiği eylemin sonucunu öğrenir; seçmediği beş eylem hakkında hiçbir şey duymaz. Sonraki ders bu çelişkiyi ölçer: bilinen en iyi eylemi tekrarlamak ile bilinmeyeni denemek arasındaki değiş tokuş, kaç adım kaybedilerek kaç adım kazanıldığı olarak sayılır — ve hiç keşif yapmayan bir ajanın hangi eylemi hiç denemediği yazılır.