Değer Fonksiyonları ve Eylem Değeri

Önceki derste çizelgede tutulan sayı anlık ödüldü: bir durumda bir eylemin o dönem ne getirdiği. Bu sayı bir ziyaretin bütün etkisini yakalayamaz. Onarılan abone birkaç dönem daha temiz kalır, ihmal edilen abone birkaç dönem sonra daha pahalıya patlar, ve ekibi bugün hangi aboneye gönderdiğimiz yarın hangi seçeneklerin elimizde olacağını belirler. İlk derste getiri otuz dönemin indirimli toplamı olarak tanımlanmıştı; çizelgede duran sayı ise tek bir dönemi tutuyordu.

Bu ders çizelgedeki sayıyı anlık ödülden getiriye çevirir. Bunu yaparken ortamın kötüleşme olasılıklarını ya da ödül çizelgesini kullanmaz — o bilgilerin hiçbiri elde yokmuş gibi davranır ve yalnız yaşanmış dörtlülerden çalışır. Sonra da kursun üçüncü sayısını çizelgenin üzerinde okur: 9.000 adımın sonunda hücrelerin kaçı hâlâ boştur.

• PO26. Kurgu, ufuk, indirim katsayısı, ölçü ve tohum 01–03’ten aynen sürer. 243 durum, 6 eylem, 30 dönemlik bölüm, indirim katsayısı 0,9, 300 bölümlük ölçüm.
• PO27. Öğrenme model gerektirmez. Kötüleşme olasılıkları da ödül çizelgesi de bilinmiyor sayılır; elde yalnız yaşanmış (durum, eylem, ödül, ardıl durum) dörtlüleri vardır.
• PO28. Bir durumun değeri, o durumdan başlayarak politikanın toplayacağı indirimli ödüllerin beklenen toplamıdır. Ödül tek dönemliktir, değer bütün geleceği taşır.
• PO29. Güncelleme zaman farkı biçimindedir: $r + \gamma V(s') - V(s)$ hesaplanır ve adım boyu 0,1 ile çizelgeye eklenir. Bölümün bitmesi beklenmez, her adımda güncelleme yapılır.
• PO30. İz bir kez toplanır, çizelge iz üzerinde 40 kez süpürülür. Veri bütçesi 9.000 adımda sabittir; süpürme sayısı hesap bütçesidir ve yeni veri getirmez.
• PO31. Değer sonsuz ufka göre tanımlıdır, oysa ölçüm 30 dönemde kesilir. İki sayı arasındaki fark, indirim katsayısının otuzuncu kuvveti olan 0,0424’lük kuyruktan gelir.
• PO32. Eylem değeri, bir durum-eylem çiftinin değeridir; hedefte ardıl durumun en iyi eylem değeri kullanılır, böylece çizelge veriyi toplayan politikadan daha iyisini arar.
• PO33. Çizelgenin ilk değeri 0,0’dır. Hiç güncellenmemiş bir hücre bu değerde kalır ve açgözlü seçim onu da aday sayar; boş hücre yokluk değil, sıfır olarak okunur.
• PO34. Ölçü üç sayıdır: 1.458 hücrenin kaçı güncellendi, kaçı hiç güncellenmedi, ve dolanların kaçı beşten az örnekle doldu.

Durumun Değeri

# ortam.py — KURGUDUR. Saha ziyareti planlamasi onceki uc 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 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(kesif, n=300, tohum=TOHUM + 11):
    """Davranis politikasi: kesif orani kadar ayrim gozetmeden, kalani kural."""
    r = uretec(tohum)
    iz = []
    for k in range(n):
        o = Ortam(TOHUM + 1000 * k)
        s = o.durum()
        for _ in range(UFUK):
            a = int(r() * EYLEM) if r() < kesif else kural(s, o)
            s2, odul = o.adim(a)
            iz.append((s, a, odul, s2))
            s = s2
    return iz


IZ = iz_topla(0.00)
BAS = [Ortam(TOHUM + 1000 * k).durum() for k in range(300)]
V = {}
for s, a, r, s2 in IZ:
    V.setdefault(s, 0.0)
    V.setdefault(s2, 0.0)
print(f"iz {len(IZ)} adim, cizelgede {len(V)} durum")
print(f"{'supurme':>8}{'V(s0) ortalamasi':>19}{'en buyuk guncelleme':>21}")
for tur in range(1, 41):
    enb = 0.0
    for s, a, r, s2 in IZ:
        d = 0.1 * (r + INDIRIM * V[s2] - V[s])
        V[s] += d
        enb = max(enb, abs(d))
    if tur in (1, 2, 5, 10, 20, 40):
        print(f"{tur:>8}{statistics.mean(V[s] for s in BAS):>19.3f}{enb:>21.4f}")
sirali = sorted(V.items(), key=lambda kv: -kv[1])
print("en yuksek uc durum: " + ", ".join(f"{s} {v:.3f}" for s, v in sirali[:3]))
print("en dusuk uc durum:  " + ", ".join(f"{s} {v:.3f}" for s, v in sirali[-3:]))

iz 9000 adim, cizelgede 103 durum
 supurme   V(s0) ortalamasi  en buyuk guncelleme
       1             12.632               2.4467
       2             15.944               2.3325
       5             19.119               1.8443
      10             20.608               1.4240
      20             21.345               1.2717
      40             21.562               1.2700
en yuksek uc durum: (1, 0, 1, 0, 2) 29.060, (1, 0, 1, 2, 1) 29.030, (0, 0, 2, 1, 2) 28.964
en dusuk uc durum:  (1, 2, 0, 0, 0) 17.801, (0, 2, 0, 0, 1) 16.573, (0, 2, 0, 1, 0) 16.075

Güncellemenin tamamı tek satırdadır: $V(s) \leftarrow V(s) + \alpha\,[\,r + \gamma V(s') - V(s)\,]$. Köşeli parantez içindeki nicelik zaman farkıdır: bir yanda o adımda gerçekten alınan ödül ve ardıl durumun mevcut kestirimi, öbür yanda o anki durumun mevcut kestirimi. İki kestirim ardışık zamanlara aittir ve aralarındaki tutarsızlık, çizelgeyi düzeltmek için kullanılır. Ortamın kötüleşme olasılıkları hiçbir yerde geçmiyor; kod yalnız yaşanmış dörtlüleri okuyor. Öğrenmenin model gerektirmemesi budur.

Sayı adım adım yerine oturuyor. İlk süpürmede başlangıç durumlarının ortalama değeri 12,632, çünkü bilgi henüz geriye doğru bir adım yayılmıştır. Onuncu süpürmede 20,608, kırkıncıda 21,562. Bağımsız ölçüm elimizde: aynı kuralın 300 bölümde ölçülen 30 dönemlik getirisi 20,621. İki sayı aynı değil ve olmaması gerekiyor. Değer sonsuz ufka göre tanımlıdır, ölçüm ise 30 dönemde kesiliyor; kesilen kuyruğun ağırlığı $\gamma^{30} = 0{,}0424$. Kuyruk hesaba katıldığında $20{,}621 / (1 - 0{,}0424) = 21{,}534$ çıkıyor, öğrenilen 21,562 ile arasındaki fark 0,028. Çizelge, hiçbir olasılığı bilmeden, ölçülen getiriyi kendi başına yeniden üretti.

Sağdaki sütun sıfıra inmiyor ve inmemesi gerekiyor. Adım boyu sabit 0,1 olduğu için çizelge donmaz; aynı hücreye gelen ödüller $-2$, 1 ve 7 arasında değiştikçe kestirim ortalamanın çevresinde salınır. En büyük güncelleme 1,2700’de duruyor, yani çizelge bir noktaya yerleşmiş ama titreşimi sürüyor.

Alt iki satır değerin ne söylediğini gösteriyor. En yüksek durum $(1, 0, 1, 0, 2)$: A3 ile A5 bekletilmiş, ikisi de hızlı kötüleşen aboneler, üstelik A5 altı dönemi geçmiş. Bu durumda ekibi bekleyen iş çoktur ve değeri 29,060. En düşük durum $(0, 2, 0, 1, 0)$: en uzun bekleyen abone A2, onun kötüleşme olasılığı ise 0,05, yani beklemesi neredeyse bir şey ifade etmiyor — kural yine de ekibi oraya gönderir. Değeri 16,075, ve en düşük üç durumun üçünde de en uzun bekleyen A2’dir. Aradaki 12,985’lik açıklık, aynı politikanın hangi durumda başladığına göre ne kadar farklı bir gelecek gördüğünü ölçüyor.

Eylemin Değeri

# eylem_degeri.py — Ayni iz, ayni zaman farki bicimi; degisen, cizelgenin
# durum yerine durum-eylem ciftiyle anahtarlanmasi ve hedefteki en iyi eylem.
def q_supur(iz, tur=40, ab=0.1, ilk=0.0):
    Q, N = {}, {}
    for s, a, r, s2 in iz:
        for x in (s, s2):
            Q.setdefault(x, [ilk] * EYLEM)
            N.setdefault(x, [0] * EYLEM)
        N[s][a] += 1
    for _ in range(tur):
        for s, a, r, s2 in iz:
            Q[s][a] += ab * (r + INDIRIM * max(Q[s2]) - Q[s][a])
    return Q, N


def acgozlu(Q, ilk=0.0):
    def pol(s, o):
        q = Q.get(s, [ilk] * EYLEM)
        return max(range(EYLEM), key=lambda i: q[i])
    return pol


Q, N = q_supur(IZ)
dolu = [(s, i) for s in N for i in range(EYLEM) if N[s][i] > 0]
print(f"guncellenen hucre {len(dolu)}/1458, hic guncellenmeyen {1458 - len(dolu)}")
print(f"cizelgeden okunan politikanin getirisi "
      f"{statistics.mean(kosum(acgozlu(Q))):.3f}")
ornek = sorted(N, key=lambda s: -sum(N[s]))[0]
print(f"ornek durum {ornek}: " + ", ".join(
    f"{ETIKET[i]} {Q[ornek][i]:.3f} (n={N[ornek][i]})" for i in range(EYLEM)))

guncellenen hucre 103/1458, hic guncellenmeyen 1355
cizelgeden okunan politikanin getirisi 20.621
ornek durum (0, 0, 1, 1, 0): A1 0.000 (n=0), A2 0.000 (n=0), A3 23.183 (n=1057), A4 0.000 (n=0), A5 0.000 (n=0), cikma 0.000 (n=0)

Değer fonksiyonu bir durumun ne kadar iyi olduğunu söyler ama hangi eylemin seçileceğini söylemez; onu söyleyebilmek için ortamın hangi eylemin nereye götürdüğünü bilmesi gerekirdi ve o bilgi elde yok. Eylem değeri bu açığı kapatır: çizelge durumla değil durum-eylem çiftiyle anahtarlanır, ve seçim doğrudan satırın en büyüğünden okunur. Hedefteki $\max$ ise çizelgeyi veriyi toplayan politikadan daha iyisini aramaya zorlar: ardıl durumda o politikanın yapacağı değil, en iyi görünen eylemin değeri kullanılır.

Örnek satır bütün dersin özetidir. Durum $(0, 0, 1, 1, 0)$ 1.057 kez yaşanmış ve altı hücresinden yalnız biri dolu: A3 için 23,183. Öteki beşi 0,000 ve yanlarındaki örnek sayısı sıfır. Bu sıfırlar “bu eylem kötüdür” demiyor, “bu eylem hiç denenmedi” diyor — ama çizelge ikisini birbirinden ayırmıyor, çünkü ilk değer neyse boş hücrede o durur.

Getiri satırı sonucu kapatıyor: çizelgeden okunan politika 20,621 alıyor, yani onu üreten kuralın sayısının tam olarak kendisini. Şaşırtıcı değil, kaçınılmazdır. Kural belirleyicidir, gördüğü her durumda tek bir eylem seçer, dolayısıyla 1.458 hücrenin yalnız 103’ü güncellenir ve her durumda tek dolu hücre otomatik olarak en büyüğü olur. Kendi verisiyle beslenen bir çizelge, kendisini üreten politikadan başkasını öneremez. Kursun ilk dersinde 103 sayısı bir gözlem olarak basılmıştı; burada doğrudan bir tavana dönüşüyor.

Çizelgenin Boş Kalan Yeri

# kapsama.py — Davranis politikasina kesif eklendikce cizelgenin kac hucresi
# doluyor, ve dolan hucrelerin kaci ince kaliyor.
print(f"{'kesif':>6}{'guncellenen':>13}{'hic bos':>9}{'ince (<5)':>11}"
      f"{'durum':>8}{'getiri':>9}")
for kesif in (0.00, 0.05, 0.20, 0.40, 1.00):
    iz = iz_topla(kesif)
    Qk, Nk = q_supur(iz)
    d = [(s, i) for s in Nk for i in range(EYLEM) if Nk[s][i] > 0]
    ince = sum(1 for s, i in d if Nk[s][i] < 5)
    print(f"{kesif:>6.2f}{len(d):>13}{1458 - len(d):>9}{ince:>11}"
          f"{len(Nk):>8}{statistics.mean(kosum(acgozlu(Qk))):>9.3f}")

 kesif  guncellenen  hic bos  ince (<5)   durum   getiri
  0.00          103     1355         47     103   20.621
  0.05          222     1236        122     114   15.176
  0.20          488      970        307     165   24.317
  0.40          749      709        437     196   21.703
  1.00         1237      221        468     235   24.419

Davranışa keşif eklendikçe çizelgenin dolu kısmı büyüyor: 103’ten 1.237’ye. Hiç boş kalan hücre 1.355’ten 221’e iniyor. Getiri sütunu ise tek yönlü ilerlemiyor — 20,621, sonra 15,176, sonra 24,317, sonra 21,703, sonra 24,419. Kapsama artıyor, sonuç düzenli iyileşmiyor.

Karşılaştırma tabanları birinci dersten sürüyor: rastgele politika 10,432, el kuralı 20,621. Beş satırın beşi de rastgelenin üstünde ama yalnız üçü el kuralını geçiyor, ve 0,05 satırı 15,176 ile kuralın altına düşüyor. Kuralın verisine biraz keşif katmak sonucu doğrudan bozabiliyor.

Cevap dördüncü sütunda. Beşten az örnekle dolan hücre sayısı 47’den 468’e çıkıyor; keşif oranı 0,20’de dolu 488 hücrenin 307’si, yani 0,629’u ince. İnce bir hücrenin taşıdığı sayı bir iki çekilişin ortalamasıdır, ve hedefteki $\max$ tam da bu sayıları öne çıkarır: yanlışlıkla yüksek çıkmış bir hücre hem kendi durumunda seçilir hem de kendisine komşu durumların hedefine sızar. Kapsama tek başına bir kalite ölçüsü değildir; kaç hücrenin dolduğu kadar, hücre başına kaç örnek düştüğü de yazılmalıdır.

Bu, kursun kuralının çizelge üzerindeki biçimidir. 24,317 sayısı 488 hücrede geçerlidir ve bunların 307’sinde beşten az gözleme dayanır; 970 hücre hakkında çizelgenin söylediği tek şey 0,000’dır ve bu bir bilgi değil, bir başlangıç değeridir. Topladığı veriyi yazmayan bir çizelge ölçülmemiş sayılır.

Özet

• Bir durumun değeri, o durumdan başlayarak politikanın toplayacağı indirimli ödüllerin beklenen toplamıdır; zaman farkı güncellemesi bu sayıyı ardışık iki kestirimin farkından öğrenir ve ortamın hiçbir olasılığını gerektirmez.
• 9.000 adımlık iz üzerinde 40 süpürmede başlangıç durumlarının ortalama değeri 12,632’den 21,562’ye çıkar; bağımsız ölçülen 30 dönemlik getiri 20,621 olup kuyruk düzeltmesiyle 21,534 eder, aradaki fark 0,028’dir.
• Sabit adım boyunda çizelge donmaz: ödül aynı hücrede $-2$ ile 7 arasında değiştiği için en büyük güncelleme 1,2700’de titreşmeye devam eder.
• Durum değerleri 29,060 ile 16,075 arasında dağılır; en yüksek durumda hızlı kötüleşen iki abone bekliyor, en düşükte kötüleşme olasılığı 0,05 olan tek abone.
• Kuralın kendi verisiyle beslenen eylem değeri çizelgesinin 1.458 hücresinden 103’ü güncellenir, 1.355’i hiç dokunulmaz, ve çizelgeden okunan politika tam olarak 20,621 verir: kendi verisiyle beslenen bir çizelge kendisini üreten politikadan başkasını öneremez.
• Keşif eklendikçe dolu hücre 103’ten 1.237’ye çıkar ama beşten az örnekli ince hücre de 47’den 468’e çıkar; getiri tek yönlü ilerlemez, çünkü hedefteki en iyi eylem seçimi ince hücrelerin gürültüsünü öne taşır.

Sonraki Adım

Dört derste çizelge her şeyi taşıdı: 243 durum, 1.458 hücre, hepsi bellekte, hepsi tek tek güncellenebilir. Bu, durum sayısının küçüklüğü sayesindedir ve o küçüklük bedava değildi. İkinci derste duruma tek bir geçmiş alanı eklendiğinde getiri 20,621’den 23,148’e çıkmıştı; aynı ekleme durum uzayını 243’ten 1.215’e, çizelgeyi 1.458 hücreden 7.290 hücreye taşır. Veri bütçesi 9.000 adımda kaldığına göre, bütün adımlar farklı hücrelere düşse bile hücre başına 1,23 örnek düşerdi — oysa bu derste 488 hücrenin 307’si beşten az örnekle zaten ince sayılmıştı. Abone sayısı beşten sekize çıksa durum uzayı 6.561, çizelge 59.049 hücre olurdu. Çizelge büyüdükçe dolmuyor, ve dolmayan çizelge sıfırlarla karar veriyor. Sonraki ders çizelgeyi bırakır: her hücreye ayrı bir sayı tutmak yerine, durumu girdi alıp değeri hesaplayan bir fonksiyon kullanılır, ve ilk işi benzer durumların birbirinden öğrenmesini sağlamak olur.