28.7-dars: Reinforcement learning asoslari

            harakat a_t
     +-------------------------+
     |                         v
  +-------+               +---------+
  | AGENT |               |  MUHIT  |
  +-------+               +---------+
     ^                         |
     +-------------------------+
       holat s_{t+1}, mukofot r_{t+1}

t = 0, 1, 2, ...:
  agent holat s_t ni ko'radi -> siyosat bo'yicha harakat a_t tanlaydi
  muhit yangi holat s_{t+1} va mukofot r_{t+1} qaytaradi
  epizod terminal holatda tugaydi (yoki vaqt chegarasida kesiladi)

SUPERVISED:    (x, y) juftliklari tayyor; "to'g'ri javob" ma'lum
               model qarori keyingi x ga ta'sir qilmaydi
BANDIT 27.13-bob: bitta holat; harakat -> darhol mukofot
               to'g'ri javob ma'lum emas, faqat tanlangan harakat bahosi
               qaror keyingi vaziyatni o'zgartirmaydi
TO'LIQ RL:     harakat -> mukofot VA yangi holat
               mukofot kechikadi: qaysi qadam "aybdor" - noma'lum
               (kreditni taqsimlash muammosi - credit assignment)

MDP = (S, A, P, R, gamma)
  S               holatlar to'plami
  A               harakatlar to'plami
  P(s' | s, a)    o'tish ehtimoli
  R(s, a, s')     mukofot
  gamma in [0,1]  diskont koeffitsienti

MARKOV XOSSASI:
  P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ...)
  "kelajak faqat hozirgi holatga bog'liq, tarixga emas"

QAYTISH (return):
  G_t = r_{t+1} + gamma * r_{t+2} + gamma^2 * r_{t+3} + ...
      = r_{t+1} + gamma * G_{t+1}                      (rekursiya)

gamma = 0      faqat keyingi mukofot ("ochko'z", uzoqni ko'rmaydi)
gamma -> 1     uzoq kelajak ham deyarli to'liq hisobga olinadi
effektiv ufq   ~ 1 / (1 - gamma)   (0.9 -> 10 qadam, 0.99 -> 100 qadam)

NEGA DISKONT:
  1. matematik: cheksiz (davomiy) vazifada yig'indi chekli bo'ladi
  2. ma'no: kelajak noaniq; "bugungi so'm ertangi so'mdan qimmat"
  3. amaliy: kichik gamma - o'rganish tezroq va barqarorroq

HOLAT QIYMATI:   V^pi(s)    = E_pi[ G_t | s_t = s ]
                 "s dan boshlab pi bo'yicha yursam, o'rtacha qancha olaman"
HARAKAT QIYMATI: Q^pi(s, a) = E_pi[ G_t | s_t = s, a_t = a ]
                 "s da a ni qilib, keyin pi bo'yicha yursam"
bog'liqlik:      V^pi(s) = sum_a pi(a|s) * Q^pi(s, a)

BELLMAN TENGLAMASI (siyosat uchun) - "bir qadam + qolgani":
  V^pi(s) = sum_a pi(a|s) sum_s' P(s'|s,a) [ R + gamma * V^pi(s') ]

BELLMAN OPTIMALLIK TENGLAMASI:
  V*(s)    = max_a sum_s' P(s'|s,a) [ R + gamma * V*(s') ]
  Q*(s, a) = sum_s' P(s'|s,a) [ R + gamma * max_a' Q*(s', a') ]
  optimal siyosat: pi*(s) = argmax_a Q*(s, a)

SIYOSATNI BAHOLASH (policy evaluation):
  V^pi ni topish: chiziqli tizimni yechish yoki
  V <- sum_a pi(a|s) sum_s' P [R + gamma V]  ni takrorlash

POLICY ITERATION:
  pi = istalgan boshlang'ich siyosat
  takrorlash:
    1. V = baholash(pi)                        (aniq, chiziqli tizim)
    2. pi_yangi(s) = argmax_a sum_s' P [R + gamma V(s')]  (ochko'z yaxshilash)
    3. pi_yangi == pi bo'lsa - to'xtash (optimal)
  odatda juda kam iteratsiya (bizda 2-4), lekin har biri qimmat

VALUE ITERATION:
  V = 0
  takrorlash:
    V(s) <- max_a sum_s' P [R + gamma V(s')]   (Bellman optimallik qadami)
  max|V_yangi - V| < tol bo'lsa - to'xtash; pi = argmax
  ko'p (bizda 22-37), lekin arzon iteratsiya

YAQINLASHISH: Bellman operatori gamma-qisqartiruvchi ->
  xato har qadamda kamida gamma marta kamayadi

MONTE CARLO (MC):  epizod TUGAGANDAN keyin
  G_t ni hisoblash (haqiqiy qaytish)
  V(s_t) <- V(s_t) + alfa * (G_t - V(s_t))
  alfa = 1/N(s) -> oddiy o'rtacha
  + siljishsiz (G_t - V ning haqiqiy namunasi)
  - shovqinli (G_t butun epizod tasodifiyligini yig'adi)
  - epizod tugashini kutadi; davomiy vazifada ishlamaydi

TD(0) (temporal difference):  HAR QADAMDA
  maqsad = r_{t+1} + gamma * V(s_{t+1})    (bootstrap: o'z bahosidan)
  V(s_t) <- V(s_t) + alfa * (maqsad - V(s_t))
  delta_t = maqsad - V(s_t)  - "TD xatosi"
  + kam shovqin (faqat bitta qadam tasodifiyligi)
  + onlayn, davomiy vazifada ham ishlaydi
  - siljish bor: V(s_{t+1}) hali noto'g'ri bo'lsa, maqsad ham noto'g'ri
  - ma'lumot zanjir bo'ylab qadamma-qadam "orqaga oqadi"

SARSA (on-policy) - nomi (s, a, r, s', a') dan:
  a' = siyosat (eps-greedy) HAQIQATDA tanlagan keyingi harakat
  Q(s,a) <- Q(s,a) + alfa * [ r + gamma * Q(s', a') - Q(s,a) ]
  o'rganadi: "HOZIRGI siyosatim (izlanish bilan) qanchalik yaxshi"

Q-LEARNING (off-policy):
  Q(s,a) <- Q(s,a) + alfa * [ r + gamma * max_a' Q(s', a') - Q(s,a) ]
  o'rganadi: "OPTIMAL (ochko'z) siyosat qanchalik yaxshi",
  garchi agent o'zi eps-greedy yursa ham

FARQ JARLIK YOQASIDA (3-misol):
  Q-learning: rampa yonidagi eng qisqa yo'l (optimal, lekin eps-qadam
              bilan tez-tez yiqiladi - o'rganish PAYTIDA yomon)
  SARSA:      o'z tasodifiy qadamlarini hisobga olib, rampadan
              uzoqroq yo'l tanlaydi (xavfsiz, o'rganish paytida yaxshi)

EPSILON-GREEDY:  eps ehtimol bilan tasodifiy, aks holda argmax Q
  doimiy eps  -> abadiy eps/|A| "isrof", lekin doimiy izlanish
  eps = 0     -> birinchi topilgan yaxshi narsada qotib qoladi

EPSILON KAMAYISHI: eps_k = max(eps_min, 1 - k / K)
  boshida ko'p izlanish, oxirida foydalanish
  GLIE sharti (cheksiz izlanishda ochko'zga yaqinlashish):
  hamma (s, a) cheksiz ko'p sinalsa va eps -> 0, SARSA optimalga yaqinlashadi
  K kichik bo'lsa - uzoqdagi mukofot topilmay qoladi (4-misol)

OPTIMISTIK BOSHLASH: Q boshida katta (masalan +10)
  sinalmagan harakat "yaxshi ko'rinadi" -> agent uni o'zi sinaydi
  deterministik muhitda juda samarali; stoxastikda ehtiyot bo'ling

import gymnasium as gym

env = gym.make("CliffWalking-v0")          # bizning 3-misoldagi muhit
holat, info = env.reset(seed=0)
tugadi = kesildi = False
while not (tugadi or kesildi):
    harakat = env.action_space.sample()     # yoki agent siyosati
    holat, mukofot, tugadi, kesildi, info = env.step(harakat)
env.close()

# o'z muhitingizni ro'yxatdan o'tkazish uchun gym.Env dan meros olinadi:
# observation_space, action_space, reset(), step() yoziladi

reset(seed)  -> (holat, info)
step(a)      -> (holat, mukofot, tugadi, kesildi, info)
  tugadi (terminated): MDP ning terminal holati (maqsad, yiqilish)
                       -> keyingi qiymat 0 deb olinadi
  kesildi (truncated): vaqt chegarasi (masalan 100 qadam)
                       -> holat terminal EMAS, bootstrap davom etadi

import numpy as np

# Bellman: Q(s,a) = sum_s' P(s'|s,a) [r + gamma V(s')]
def q_hisobla(P, V, gamma):          # P[s][a] = [(p, s2, r, tugadi), ...]
    return np.array([[sum(p * (r + gamma * V[s2] * (not t)) for p, s2, r, t in P[s][a])
                      for a in range(len(P[s]))] for s in range(len(P))])

# value iteration
V = np.zeros(n_holat)
while True:
    V_yangi = q_hisobla(P, V, gamma).max(1)
    if np.max(np.abs(V_yangi - V)) < 1e-8:
        break
    V = V_yangi
pi = q_hisobla(P, V, gamma).argmax(1)

# TD(0) baholash
V[s] += alfa * (r + gamma * V[s2] * (not tugadi) - V[s])

# SARSA (on-policy) va Q-learning (off-policy)
Q[s, a] += alfa * (r + gamma * Q[s2, a2] * (not tugadi) - Q[s, a])
Q[s, a] += alfa * (r + gamma * Q[s2].max() * (not tugadi) - Q[s, a])

# eps-greedy, eps kamayishi
eps = max(0.05, 1.0 - k / (0.8 * epizodlar))
a = rng.integers(n_harakat) if rng.random() < eps else int(np.argmax(Q[s]))

RL = holat + harakat + kechikkan mukofot; qaror dunyoni o'zgartiradi
V, Q - kutilgan qaytish; Bellman: "bir qadam + qolgani"
gamma - vazifa ta'rifi; ufq ~ 1/(1-gamma)
model bor -> DP; model yo'q -> MC / TD / SARSA / Q-learning
SARSA - xavfsiz o'rganish; Q-learning - optimal ochko'z siyosat
izlanish: eps kamayishi, optimistik boshlash; bir necha urug'

"""Omborxona grid-world: MDP modeli, value iteration va policy iteration noldan."""

import numpy as np

XARITA = [
    "############",
    "#          #",
    "# ######## #",
    "#S~~~~~~~~G#",
    "#XXXXXXXXXX#",
    "############",
]
YONALISH = [(-1, 0), (0, 1), (1, 0), (0, -1)]      # 0 yuqori, 1 o'ng, 2 past, 3 chap
STRELKA = "^>v<"
QADAM = -0.1                                       # har qadam narxi (elektr, vaqt)


class Ombor:
    """Robot omborda yuk tushirish joyiga (G) boradi.

    '#' javon yoki devor, '~' ho'l pol, 'X' rampa chekkasi (yiqiladi: -20,
    epizod tugaydi), 'G' maqsad (+10, epizod tugaydi), har qadam -0.1.
    Sirpanish: s ehtimol bilan robot 4 tomondan tasodifiy biriga ketadi
    (oddiy polda s_pol, ho'l polda s_hol).
    """

    def __init__(self, xarita=XARITA, s_pol=0.0, s_hol=0.0):
        self.xarita = xarita
        self.h, self.w = len(xarita), len(xarita[0])
        self.s_pol, self.s_hol = s_pol, s_hol
        self.kataklar = [(r, c) for r in range(self.h) for c in range(self.w)
                         if xarita[r][c] != "#"]
        self.indeks = {k: i for i, k in enumerate(self.kataklar)}
        self.n_holat, self.n_harakat = len(self.kataklar), 4
        self.boshlanish = next(i for i, (r, c) in enumerate(self.kataklar)
                               if xarita[r][c] == "S")
        self.P = self._model()

    def belgi(self, s):
        r, c = self.kataklar[s]
        return self.xarita[r][c]

    def terminal(self, s):
        return self.belgi(s) in "GX"

    def siljish(self, s, d):
        r, c = self.kataklar[s]
        nr, nc = r + YONALISH[d][0], c + YONALISH[d][1]
        return s if self.xarita[nr][nc] == "#" else self.indeks[(nr, nc)]

    def _model(self):
        """P[s][a] = [(ehtimol, keyingi holat, mukofot, tugadi), ...]"""
        P = []
        for s in range(self.n_holat):
            qator = []
            for a in range(4):
                if self.terminal(s):
                    qator.append([(1.0, s, 0.0, True)])
                    continue
                sl = self.s_hol if self.belgi(s) == "~" else self.s_pol
                natija = {}
                for d, p in [(a, 1 - sl)] + [(d, sl / 4) for d in range(4)]:
                    if p > 0:
                        s2 = self.siljish(s, d)
                        natija[s2] = natija.get(s2, 0.0) + p
                otish = []
                for s2 in sorted(natija):
                    b = self.belgi(s2)
                    r = QADAM + (10.0 if b == "G" else -20.0 if b == "X" else 0.0)
                    otish.append((natija[s2], s2, r, b in "GX"))
                qator.append(otish)
            P.append(qator)
        return P

    # gymnasium uslubidagi interfeys (modelsiz algoritmlar shu orqali ishlaydi)
    def reset(self, seed=None):
        self.rng = np.random.default_rng(seed)
        self.s = self.boshlanish
        return self.s, {}

    def step(self, a):
        otish = self.P[self.s][a]
        i = self.rng.choice(len(otish), p=[o[0] for o in otish])
        _, self.s, r, tugadi = otish[i]
        return self.s, r, tugadi, False, {}


def q_hisobla(env, V, gamma):
    """Q(s,a) = sum_s' P(s'|s,a) * [r + gamma * V(s')]  (Bellman)."""
    Q = np.zeros((env.n_holat, 4))
    for s in range(env.n_holat):
        for a in range(4):
            Q[s, a] = sum(p * (r + gamma * V[s2] * (not t))
                          for p, s2, r, t in env.P[s][a])
    return Q


def value_iteration(env, gamma, tol=1e-8):
    V = np.zeros(env.n_holat)
    for k in range(1, 10_000):
        V_yangi = q_hisobla(env, V, gamma).max(1)
        farq = np.max(np.abs(V_yangi - V))
        V = V_yangi
        if farq < tol:
            break
    return V, q_hisobla(env, V, gamma).argmax(1), k


def baholash(env, pi, gamma, faqat_yiqilish=False):
    """V^pi = (I - gamma * P_pi)^-1 r_pi.  pi - [holat, harakat] ehtimollari.

    faqat_yiqilish=True: mukofot = X ga tushish, gamma = 1 -> P(yiqilish).
    """
    n = env.n_holat
    Pm, rv = np.zeros((n, n)), np.zeros(n)
    for s in range(n):
        for a in range(4):
            for p, s2, r, t in env.P[s][a]:
                w = pi[s, a] * p
                if faqat_yiqilish:
                    rv[s] += w * (env.belgi(s2) == "X" and not env.terminal(s))
                else:
                    rv[s] += w * r
                if not t:
                    Pm[s, s2] += w
    return np.linalg.solve(np.eye(n) - gamma * Pm, rv)


def one_hot(pi):
    m = np.zeros((len(pi), 4))
    m[np.arange(len(pi)), pi] = 1.0
    return m


def policy_iteration(env, gamma):
    pi = np.zeros(env.n_holat, dtype=int)          # boshida hamma "yuqori"
    for k in range(1, 100):
        V = baholash(env, one_hot(pi), gamma)       # 1) baholash (aniq)
        pi_yangi = q_hisobla(env, V, gamma).argmax(1)   # 2) ochko'z yaxshilash
        if np.array_equal(pi_yangi, pi):
            return V, pi, k
        pi = pi_yangi
    return V, pi, k


def chiz(env, pi):
    qatorlar = []
    for r in range(env.h):
        q = ""
        for c in range(env.w):
            b = env.xarita[r][c]
            q += b if b in "#GX" else STRELKA[pi[env.indeks[(r, c)]]]
        qatorlar.append("  " + q)
    return "\n".join(qatorlar)


def yol_uzunligi(env, pi, max_qadam=60):
    """Sirpanishsiz yurganda siyosat necha qadamda tugaydi."""
    s, n = env.boshlanish, 0
    while not env.terminal(s) and n < max_qadam:
        s, n = env.siljish(s, pi[s]), n + 1
    return n


def main() -> None:
    gamma = 0.95
    print("=== 1. Xarita va MDP modeli ===")
    print("\n".join("  " + q for q in XARITA))
    env = Ombor(s_pol=0.04, s_hol=0.2)
    s0 = env.boshlanish
    print(f"  holatlar: {env.n_holat}, harakatlar: 4, gamma = {gamma}")
    s1 = env.siljish(s0, 1)                         # S ning o'ng qo'shnisi (ho'l)
    print("  ho'l polda 'o'ngga' harakati:")
    for p, s2, r, t in env.P[s1][1]:
        print(f"    p={p:.2f} -> '{env.belgi(s2)}'  r={r:+.1f}  tugadi={t}")

    print("\n=== 2. Value iteration va policy iteration ===")
    V1, pi1, k1 = value_iteration(env, gamma)
    V2, pi2, k2 = policy_iteration(env, gamma)
    print(f"  value iteration:  {k1} ta Bellman qadami, V(S) = {V1[s0]:.3f}")
    print(f"  policy iteration: {k2} ta yaxshilash,    V(S) = {V2[s0]:.3f}")
    print(f"  siyosatlar bir xil: {np.array_equal(pi1, pi2)}, "
          f"max|V1 - V2| = {np.max(np.abs(V1 - V2)):.1e}")
    print(chiz(env, pi1))

    print("\n=== 3. Model noto'g'ri bo'lsa: quruq ombor siyosati ===")
    quruq = Ombor()
    _, piq, _ = value_iteration(quruq, gamma)
    print(chiz(quruq, piq))
    tasodifiy = np.full((env.n_holat, 4), 0.25)
    print("  sirpanchiq omborda aniq baholash:")
    print(f"  {'siyosat':<28} {'yo_l':>5} {'V(S)':>8} {'P(yiqilish)':>12}")
    for nom, pi in [("quruq ombor uchun optimal", one_hot(piq)),
                    ("sirpanchiq ombor uchun opt.", one_hot(pi1)),
                    ("tasodifiy (bazaviy)", tasodifiy)]:
        yol = yol_uzunligi(env, pi.argmax(1)) if nom[0] != "t" else "-"
        v = baholash(env, pi, gamma)[s0]
        py = baholash(env, pi, 1.0, faqat_yiqilish=True)[s0]
        print(f"  {nom:<28} {yol:>5} {v:>8.3f} {py:>12.3f}")

    print("\n=== 4. Ho'l pol qanchalik sirpanchiq bo'lsa, marshrut o'zgaradi ===")
    print(f"  {'s_hol':>6} {'yo_l':>5} {'V(S)':>8} {'P(yiqilish)':>12}")
    for s in [0.0, 0.01, 0.02, 0.03, 0.05, 0.2, 0.4]:
        e = Ombor(s_pol=0.04, s_hol=s)
        V, pi, _ = value_iteration(e, gamma)
        py = baholash(e, one_hot(pi), 1.0, faqat_yiqilish=True)[s0]
        print(f"  {s:>6.2f} {yol_uzunligi(e, pi):>5} {V[s0]:>8.3f} {py:>12.3f}")

    print("\n=== 5. Gamma va yaqinlashish tezligi ===")
    print(f"  {'gamma':>6} {'VI qadam':>9} {'PI yaxshilash':>14} {'V(S)':>8} {'yo_l':>5}")
    for g in [0.5, 0.8, 0.9, 0.95, 0.99]:
        V, pi, k = value_iteration(env, g)
        _, _, kp = policy_iteration(env, g)
        print(f"  {g:>6} {k:>9} {kp:>14} {V[s0]:>8.3f} {yol_uzunligi(env, pi):>5}")
    print("  ⭐ VI - ko'p arzon qadam; PI - kam, lekin qimmat qadam (tenglamalar)")


if __name__ == "__main__":
    main()

=== 1. Xarita va MDP modeli ===
  ############
  #          #
  # ######## #
  #S~~~~~~~~G#
  #XXXXXXXXXX#
  ############
  holatlar: 32, harakatlar: 4, gamma = 0.95
  ho'l polda 'o'ngga' harakati:
    p=0.05 -> 'S'  r=-0.1  tugadi=False
    p=0.05 -> '~'  r=-0.1  tugadi=False
    p=0.85 -> '~'  r=-0.1  tugadi=False
    p=0.05 -> 'X'  r=-20.1  tugadi=True

=== 2. Value iteration va policy iteration ===
  value iteration:  35 ta Bellman qadami, V(S) = 4.000
  policy iteration: 3 ta yaxshilash,    V(S) = 4.000
  siyosatlar bir xil: True, max|V1 - V2| = 3.3e-09
  ############
  #>>>>>>>>>v#
  #^########v#
  #^<<<>>>>>G#
  #XXXXXXXXXX#
  ############

=== 3. Model noto'g'ri bo'lsa: quruq ombor siyosati ===
  ############
  #>>>>>>>>>v#
  #v########v#
  #>>>>>>>>>G#
  #XXXXXXXXXX#
  ############
  sirpanchiq omborda aniq baholash:
  siyosat                       yo_l     V(S)  P(yiqilish)
  quruq ombor uchun optimal        9   -3.010        0.388
  sirpanchiq ombor uchun opt.     13    4.000        0.011
  tasodifiy (bazaviy)              -  -15.139        0.954

=== 4. Ho'l pol qanchalik sirpanchiq bo'lsa, marshrut o'zgaradi ===
   s_hol  yo_l     V(S)  P(yiqilish)
    0.00     9    5.618        0.010
    0.01     9    5.154        0.030
    0.02     9    4.695        0.049
    0.03     9    4.240        0.069
    0.05    13    4.015        0.011
    0.20    13    4.000        0.011
    0.40    13    3.981        0.012

=== 5. Gamma va yaqinlashish tezligi ===
   gamma  VI qadam  PI yaxshilash     V(S)  yo_l
     0.5        22              4   -0.404    13
     0.8        29              4   -0.069    13
     0.9        32              4    1.686    13
    0.95        35              3    4.000    13
    0.99        37              2    7.245    13
  ⭐ VI - ko'p arzon qadam; PI - kam, lekin qimmat qadam (tenglamalar)

"""Modelsiz baholash: Monte Carlo va TD(0) noldan, DP dagi aniq V bilan solishtirib."""

import random

import numpy as np

XARITA = [
    "############",
    "#          #",
    "# ######## #",
    "#S~~~~~~~~G#",
    "#XXXXXXXXXX#",
    "############",
]
YONALISH = [(-1, 0), (0, 1), (1, 0), (0, -1)]


class Ombor:
    """1-misoldagi ombor (qisqa nusxa): '~' ho'l pol, 'X' rampa, 'G' maqsad."""

    def __init__(self, s_pol=0.04, s_hol=0.2):
        self.kataklar = [(r, c) for r in range(len(XARITA))
                         for c in range(len(XARITA[0])) if XARITA[r][c] != "#"]
        idx = {k: i for i, k in enumerate(self.kataklar)}
        self.n_holat = len(self.kataklar)
        self.boshlanish = next(i for i, (r, c) in enumerate(self.kataklar)
                               if XARITA[r][c] == "S")
        self.terminal = [XARITA[r][c] in "GX" for r, c in self.kataklar]
        self.P = []
        for s, (r, c) in enumerate(self.kataklar):
            qator = []
            for a in range(4):
                sl = s_hol if XARITA[r][c] == "~" else s_pol
                natija = {}
                for d, p in [(a, 1 - sl)] + [(d, sl / 4) for d in range(4)]:
                    nr, nc = r + YONALISH[d][0], c + YONALISH[d][1]
                    s2 = s if XARITA[nr][nc] == "#" else idx[(nr, nc)]
                    natija[s2] = natija.get(s2, 0.0) + p
                otish = []
                for s2 in sorted(natija):
                    b = XARITA[self.kataklar[s2][0]][self.kataklar[s2][1]]
                    rew = -0.1 + (10.0 if b == "G" else -20.0 if b == "X" else 0.0)
                    otish.append((natija[s2], s2, rew, b in "GX"))
                qator.append(otish)
            self.P.append(qator)

    def reset(self, seed=None):
        self.rng = random.Random(seed)
        self.s = self.boshlanish
        return self.s, {}

    def step(self, a):
        u, jami = self.rng.random(), 0.0
        for p, s2, rew, tugadi in self.P[self.s][a]:
            jami += p
            if u < jami:
                break
        self.s = s2
        return s2, rew, tugadi, False, {}


def aniq_v(env, pi, gamma):
    """DP: V^pi = (I - gamma P_pi)^-1 r_pi (model ma'lum bo'lgandagi javob)."""
    n = env.n_holat
    Pm, rv = np.zeros((n, n)), np.zeros(n)
    for s in range(n):
        if env.terminal[s]:
            continue
        for a in range(4):
            for p, s2, rew, t in env.P[s][a]:
                rv[s] += pi[s, a] * p * rew
                if not t:
                    Pm[s, s2] += pi[s, a] * p
    return np.linalg.solve(np.eye(n) - gamma * Pm, rv)


def epizod(env, pi_kum, rng, seed):
    """Bitta epizod: [(holat, mukofot, keyingi holat, tugadi), ...]."""
    s, _ = env.reset(seed)
    tarix = []
    for _ in range(500):
        u = rng.random()
        a = next(i for i in range(4) if u < pi_kum[s][i])
        s2, rew, tugadi, kesildi, _ = env.step(a)
        tarix.append((s, rew, s2, tugadi))
        s = s2
        if tugadi or kesildi:
            break
    return tarix


def mc_yangila(V, N, tarix, gamma, alfa):
    """First-visit Monte Carlo: V(s) <- V(s) + alfa * (G - V(s))."""
    G, qaytish = 0.0, []
    for s, rew, _, _ in reversed(tarix):
        G = rew + gamma * G
        qaytish.append((s, G))
    korilgan = set()
    for s, G in reversed(qaytish):              # epizod boshidan oxiriga
        if s in korilgan:
            continue
        korilgan.add(s)
        N[s] += 1
        a = 1.0 / N[s] if alfa is None else alfa
        V[s] += a * (G - V[s])


def td_yangila(V, N, tarix, gamma, alfa):
    """TD(0): V(s) <- V(s) + alfa * (r + gamma V(s') - V(s)) - har qadamda."""
    for s, rew, s2, tugadi in tarix:
        maqsad = rew + (0.0 if tugadi else gamma * V[s2])
        N[s] += 1
        a = 1.0 / N[s] if alfa is None else alfa
        V[s] += a * (maqsad - V[s])


def main() -> None:
    gamma = 0.95
    env = Ombor()
    # baholanadigan siyosat: xavfsiz marshrut, lekin 20% hollarda tasodifiy harakat
    xavfsiz = {(1, c): 1 for c in range(1, 10)}
    xavfsiz.update({(1, 10): 2, (2, 10): 2, (2, 1): 0, (3, 1): 0})
    xavfsiz.update({(3, c): (3 if c < 5 else 1) for c in range(2, 10)})
    pi = np.full((env.n_holat, 4), 0.05)
    for s, k in enumerate(env.kataklar):
        pi[s, xavfsiz.get(k, 0)] += 0.8
    pi_kum = np.cumsum(pi, axis=1).tolist()
    for q in pi_kum:
        q[-1] = 1.0
    V_aniq = aniq_v(env, pi, gamma)
    s0 = env.boshlanish
    ichki = [s for s in range(env.n_holat) if not env.terminal[s]]
    # siyosat bo'yicha tashrif chastotasi mu(s): RMSE shu vazn bilan (VE)
    Pm = np.zeros((env.n_holat, env.n_holat))
    for s in ichki:
        for a in range(4):
            for p, s2, _, t in env.P[s][a]:
                if not t:
                    Pm[s, s2] += pi[s, a] * p
    e0 = np.zeros(env.n_holat)
    e0[s0] = 1.0
    mu = np.linalg.solve(np.eye(env.n_holat) - Pm.T, e0)
    w = mu / mu.sum()

    print("=== 1. Baholanadigan siyosat va aniq javob (DP) ===")
    print(f"  holatlar: {len(ichki)} ta (terminal emas), gamma = {gamma}")
    print(f"  bir epizodda kutilgan qadamlar soni: {mu.sum():.2f}")
    print(f"  aniq V(S) = {V_aniq[s0]:.3f}")
    rng = random.Random(0)
    qaytishlar = []
    for e in range(2000):
        G = 0.0
        for _, rew, _, _ in reversed(epizod(env, pi_kum, rng, 10_000 + e)):
            G = rew + gamma * G
        qaytishlar.append(G)
    q = np.array(qaytishlar)
    print(f"  S dan 2000 epizod qaytishi: o'rtacha {q.mean():.3f}, "
          f"std {q.std():.3f}, min {q.min():.2f}, max {q.max():.2f}")
    print("  (bitta epizod qaytishi - V(S) ning shovqinli bahosi)")

    print("\n=== 2. RMSE(V) epizodlar soniga qarab (10 urug' o'rtachasi) ===")
    usullar = {"MC (1/N)": ("mc", None), "MC alfa=0.05": ("mc", 0.05),
               "TD(0) 1/N": ("td", None),
               "TD(0) alfa=0.05": ("td", 0.05), "TD(0) alfa=0.2": ("td", 0.2)}
    nuqtalar = [10, 30, 100, 300, 1000]
    urug = list(range(10))
    xato = {nom: np.zeros((len(urug), len(nuqtalar))) for nom in usullar}
    xato_s0 = {nom: np.zeros(len(urug)) for nom in usullar}
    for i, u in enumerate(urug):
        # bir urug' ichida hamma usul AYNAN bir xil epizodlarni ko'radi
        rng = random.Random(u)
        epizodlar = [epizod(env, pi_kum, rng, 1000 * u + e)
                     for e in range(nuqtalar[-1])]
        for nom, (tur, alfa) in usullar.items():
            V, N = np.zeros(env.n_holat), np.zeros(env.n_holat)
            j = 0
            for e, tarix in enumerate(epizodlar, 1):
                if tur == "mc":
                    mc_yangila(V, N, tarix, gamma, alfa)
                else:
                    td_yangila(V, N, tarix, gamma, alfa)
                if e == nuqtalar[j]:
                    xato[nom][i, j] = np.sqrt(np.sum(w * (V - V_aniq) ** 2))
                    j = min(j + 1, len(nuqtalar) - 1)
            xato_s0[nom][i] = V[s0] - V_aniq[s0]
    print(f"  {'usul':<16}" + "".join(f"{n:>8}" for n in nuqtalar))
    for nom in usullar:
        print(f"  {nom:<16}" + "".join(f"{x:>8.3f}" for x in xato[nom].mean(0)))

    print("\n=== 3. 1000 epizoddan keyin V(S) xatosi (urug'lar bo'yicha) ===")
    print(f"  {'usul':<16} {'o_rtacha':>9} {'std':>7}")
    for nom in usullar:
        x = xato_s0[nom]
        print(f"  {nom:<16} {x.mean():>+9.3f} {x.std(ddof=1):>7.3f}")

    print("\n=== 4. Juftlashgan taqqoslash: 100 epizodda RMSE ===")
    j = nuqtalar.index(100)
    td_nomlar = [n for n in usullar if n.startswith("TD")]
    eng_td = min(td_nomlar, key=lambda n: xato[n][:, j].mean())
    d = xato[eng_td][:, j] - xato["MC (1/N)"][:, j]
    se = d.std(ddof=1) / np.sqrt(len(d))
    print(f"  eng yaxshi TD varianti: {eng_td}")
    print(f"  {eng_td} - MC (1/N): {d.mean():+.3f}, SE {se:.3f}, "
          f"sezilarli: {abs(d.mean()) > 2 * se}")
    if abs(d.mean()) > 2 * se:
        print(f"  bu muhitda 100 epizodda {'TD' if d.mean() < 0 else 'MC'} aniqroq")
    else:
        print("  100 epizodda farq sezilarli emas")
    print("  ⭐ MC: siljishsiz, lekin shovqinli; TD: bootstrap - kam shovqin, siljish bor")


if __name__ == "__main__":
    main()

=== 1. Baholanadigan siyosat va aniq javob (DP) ===
  holatlar: 21 ta (terminal emas), gamma = 0.95
  bir epizodda kutilgan qadamlar soni: 15.61
  aniq V(S) = 1.551
  S dan 2000 epizod qaytishi: o'rtacha 1.447, std 6.374, min -20.10, max 4.43
  (bitta epizod qaytishi - V(S) ning shovqinli bahosi)

=== 2. RMSE(V) epizodlar soniga qarab (10 urug' o'rtachasi) ===
  usul                  10      30     100     300    1000
  MC (1/N)           0.733   0.460   0.275   0.211   0.111
  MC alfa=0.05       4.093   1.617   0.302   0.323   0.420
  TD(0) 1/N          5.104   4.633   4.191   3.791   3.375
  TD(0) alfa=0.05    6.026   5.443   3.889   0.655   0.355
  TD(0) alfa=0.2     5.329   3.458   0.675   0.670   0.698

=== 3. 1000 epizoddan keyin V(S) xatosi (urug'lar bo'yicha) ===
  usul              o_rtacha     std
  MC (1/N)            -0.044   0.139
  MC alfa=0.05        -0.470   1.588
  TD(0) 1/N           -3.642   0.123
  TD(0) alfa=0.05     -0.447   1.478
  TD(0) alfa=0.2      -0.983   2.663

=== 4. Juftlashgan taqqoslash: 100 epizodda RMSE ===
  eng yaxshi TD varianti: TD(0) alfa=0.2
  TD(0) alfa=0.2 - MC (1/N): +0.400, SE 0.242, sezilarli: False
  100 epizodda farq sezilarli emas
  ⭐ MC: siljishsiz, lekin shovqinli; TD: bootstrap - kam shovqin, siljish bor

"""Rampa bo'yidagi yo'lak (cliff walking): Q-learning va SARSA noldan."""

import random

import numpy as np

H, W = 4, 12
START, MAQSAD = (3, 0), (3, 11)
YONALISH = [(-1, 0), (0, 1), (1, 0), (0, -1)]
STRELKA = "^>v<"


class Rampa:
    """4 x 12 maydon. Pastki qatorda S va G orasida rampa chekkasi:
    unga qadam qo'ysa -100 va robot S ga qaytariladi. Har qadam -1."""

    n_holat, n_harakat = H * W, 4

    def reset(self, seed=None):
        self.s = START[0] * W + START[1]
        return self.s, {}

    def step(self, a):
        r, c = divmod(self.s, W)
        r = min(max(r + YONALISH[a][0], 0), H - 1)
        c = min(max(c + YONALISH[a][1], 0), W - 1)
        if r == 3 and 0 < c < 11:                     # rampa chekkasi
            self.s = START[0] * W + START[1]
            return self.s, -100.0, False, False, {"yiqildi": True}
        self.s = r * W + c
        return self.s, -1.0, (r, c) == MAQSAD, False, {"yiqildi": False}


def eps_greedy(Q, s, eps, rng):
    if rng.random() < eps:
        return rng.randrange(4)
    q = Q[s]
    m = max(q)
    return rng.choice([a for a in range(4) if q[a] == m])   # teng bo'lsa tasodifiy


def orgat(algoritm, urug, epizodlar=500, alfa=0.5, gamma=1.0, eps=0.1,
          kamayish=False):
    """Q-learning yoki SARSA; har epizod mukofotlari yig'indisini qaytaradi.
    kamayish=True: eps chiziqli ravishda 0.1 dan 0 gacha tushadi."""
    rng = random.Random(urug)
    env = Rampa()
    Q = [[0.0] * 4 for _ in range(env.n_holat)]
    tarix, yiqilish = [], []
    eps0 = eps
    for k in range(epizodlar):
        if kamayish:
            eps = eps0 * (1 - k / epizodlar)
        s, _ = env.reset()
        a = eps_greedy(Q, s, eps, rng)
        jami, yiq = 0.0, 0
        for _ in range(1000):
            s2, r, tugadi, kesildi, info = env.step(a)
            jami += r
            yiq += info["yiqildi"]
            a2 = eps_greedy(Q, s2, eps, rng)
            if tugadi:
                maqsad = r
            elif algoritm == "Q-learning":
                maqsad = r + gamma * max(Q[s2])       # off-policy: eng yaxshi harakat
            else:
                maqsad = r + gamma * Q[s2][a2]        # on-policy: haqiqatda tanlangan
            Q[s][a] += alfa * (maqsad - Q[s][a])
            s, a = s2, a2
            if tugadi or kesildi:
                break
        tarix.append(jami)
        yiqilish.append(yiq)
    return np.array(Q), np.array(tarix), np.array(yiqilish)


def ochkoz_yol(Q, max_qadam=100):
    """Ochko'z (eps = 0) siyosat bilan yurish: (qaytish, yo'l kataklari)."""
    env = Rampa()
    s, _ = env.reset()
    jami, yol = 0.0, [s]
    for _ in range(max_qadam):
        s, r, tugadi, _, _ = env.step(int(np.argmax(Q[s])))
        jami += r
        yol.append(s)
        if tugadi:
            break
    return jami, yol


def chiz(Q, yol):
    satrlar = []
    for r in range(H):
        q = ""
        for c in range(W):
            s = r * W + c
            if (r, c) == START:
                q += "S"
            elif (r, c) == MAQSAD:
                q += "G"
            elif r == 3:
                q += "X"
            elif s in yol:
                q += STRELKA[int(np.argmax(Q[s]))]
            else:
                q += "-"
        satrlar.append("    " + q)
    return "\n".join(satrlar)


def tasodifiy_bazaviy(urug, epizodlar=200):
    rng = random.Random(urug)
    env = Rampa()
    natija = []
    for _ in range(epizodlar):
        env.reset()
        jami = 0.0
        for _ in range(1000):
            _, r, tugadi, _, _ = env.step(rng.randrange(4))
            jami += r
            if tugadi:
                break
        natija.append(jami)
    return np.mean(natija)


def main() -> None:
    urug = list(range(10))
    algoritmlar = ["Q-learning", "SARSA"]
    natija = {a: [orgat(a, u) for u in urug] for a in algoritmlar}

    print("=== 1. O'rgatish davomida o'rtacha mukofot (eps = 0.1, 10 urug') ===")
    oraliqlar = [(0, 50), (50, 100), (100, 200), (200, 300), (300, 500)]
    print(f"  {'epizodlar':<10}" + "".join(f"{a:>12}" for a in algoritmlar))
    for i, j in oraliqlar:
        qator = f"  {f'{i}-{j}':<10}"
        for a in algoritmlar:
            qator += f"{np.mean([t[i:j].mean() for _, t, _ in natija[a]]):>12.1f}"
        print(qator)
    print(f"  tasodifiy siyosat (bazaviy): "
          f"{np.mean([tasodifiy_bazaviy(u) for u in urug[:3]]):.1f}")

    print("\n=== 2. Oxirgi 200 epizod: juftlashgan farq urug'lar bo'yicha ===")
    q_m = np.array([t[300:].mean() for _, t, _ in natija["Q-learning"]])
    s_m = np.array([t[300:].mean() for _, t, _ in natija["SARSA"]])
    q_y = np.array([y[300:].mean() for _, _, y in natija["Q-learning"]])
    s_y = np.array([y[300:].mean() for _, _, y in natija["SARSA"]])
    d = s_m - q_m
    se = d.std(ddof=1) / np.sqrt(len(d))
    print(f"  o'rtacha mukofot: Q-learning {q_m.mean():.1f}, SARSA {s_m.mean():.1f}")
    print(f"  yiqilish / epizod: Q-learning {q_y.mean():.3f}, SARSA {s_y.mean():.3f}")
    print(f"  SARSA - Q-learning: {d.mean():+.1f}, SE {se:.1f}, "
          f"sezilarli: {abs(d.mean()) > 2 * se}")

    print("\n=== 3. Yakuniy ochko'z siyosat (eps = 0 bilan yurish) ===")
    for a in algoritmlar:
        yollar = [ochkoz_yol(Q) for Q, _, _ in natija[a]]
        yetdi = [len(y) - 1 for q, y in yollar if len(y) - 1 < 100]
        print(f"  {a:<11} G ga yetdi: {len(yetdi)}/10, qadamlar: "
              f"{sorted(yetdi)}")
    for a in algoritmlar:
        Q = natija[a][0][0]
        jami, yol = ochkoz_yol(Q)
        print(f"  {a} (urug' 0) yo'li, qaytish {jami:.0f}:")
        print(chiz(Q, set(yol)))

    print("\n=== 4. eps 0.1 dan 0 gacha kamaysa (10 urug') ===")
    print(f"  {'algoritm':<11} {'oxirgi 100 ep.':>15} {'G ga yetdi':>11} "
          f"{'qadamlar':>9}")
    kam = {}
    for a in algoritmlar:
        kam[a] = [orgat(a, u, kamayish=True) for u in urug]
        oxirgi = np.mean([t[400:].mean() for _, t, _ in kam[a]])
        yollar = [len(ochkoz_yol(Q)[1]) - 1 for Q, _, _ in kam[a]]
        yetdi = [n for n in yollar if n < 100]
        print(f"  {a:<11} {oxirgi:>15.1f} {len(yetdi):>8}/10 "
              f"{np.median(yetdi) if yetdi else float('nan'):>9.0f}")
    print(f"  optimal yo'l: 13 qadam (-13)")

    print("\n=== 5. Xulosa (natijadan) ===")
    if abs(d.mean()) > 2 * se and d.mean() > 0:
        print(f"  eps = 0.1 da o'rganish PAYTIDA SARSA yaxshiroq (+{d.mean():.1f}),"
              " yiqilish kam")
    def yetgan(a):
        n = [len(ochkoz_yol(Q)[1]) - 1 for Q, _, _ in natija[a]]
        return [x for x in n if x < 100]
    q_och, s_och = yetgan("Q-learning"), yetgan("SARSA")
    if max(q_och) < min(s_och):
        print(f"  ochko'z yo'l: Q-learning qisqaroq ({max(q_och)} vs "
              f"{min(s_och)}+ qadam) - rampa yonidan")
    if len(s_och) < 10:
        print(f"  SARSA ning ochko'z siyosati {10 - len(s_och)} urug'da G ga"
              " yetmadi (aylanib qoldi)")
    print("  ⭐ Q-learning: 'keyin xato qilmayman' deb o'rganadi (optimal, xavfli);"
          " SARSA: 'ba'zan tasodifiy qadam qo'yaman' deb (xavfsiz)")


if __name__ == "__main__":
    main()

=== 1. O'rgatish davomida o'rtacha mukofot (eps = 0.1, 10 urug') ===
  epizodlar   Q-learning       SARSA
  0-50            -115.9      -108.8
  50-100           -47.9       -36.0
  100-200          -50.6       -29.3
  200-300          -52.4       -25.6
  300-500          -46.4       -26.7
  tasodifiy siyosat (bazaviy): -9590.2

=== 2. Oxirgi 200 epizod: juftlashgan farq urug'lar bo'yicha ===
  o'rtacha mukofot: Q-learning -46.4, SARSA -26.7
  yiqilish / epizod: Q-learning 0.301, SARSA 0.050
  SARSA - Q-learning: +19.7, SE 1.8, sezilarli: True

=== 3. Yakuniy ochko'z siyosat (eps = 0 bilan yurish) ===
  Q-learning  G ga yetdi: 10/10, qadamlar: [13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
  SARSA       G ga yetdi: 7/10, qadamlar: [17, 17, 17, 17, 17, 19, 21]
  Q-learning (urug' 0) yo'li, qaytish -13:
    ------------
    ------------
    >>>>>>>>>>>v
    SXXXXXXXXXXG
  SARSA (urug' 0) yo'li, qaytish -19:
    ->>>v->>>>v-
    >^-->>^---v-
    ^--------->v
    SXXXXXXXXXXG

=== 4. eps 0.1 dan 0 gacha kamaysa (10 urug') ===
  algoritm     oxirgi 100 ep.  G ga yetdi  qadamlar
  Q-learning            -16.0       10/10        13
  SARSA                 -17.6       10/10        17
  optimal yo'l: 13 qadam (-13)

=== 5. Xulosa (natijadan) ===
  eps = 0.1 da o'rganish PAYTIDA SARSA yaxshiroq (+19.7), yiqilish kam
  ochko'z yo'l: Q-learning qisqaroq (13 vs 17+ qadam) - rampa yonidan
  SARSA ning ochko'z siyosati 3 urug'da G ga yetmadi (aylanib qoldi)
  ⭐ Q-learning: 'keyin xato qilmayman' deb o'rganadi (optimal, xavfli); SARSA: 'ba'zan tasodifiy qadam qo'yaman' deb (xavfsiz)

"""Izlanish va gamma: eps-greedy, eps kamayishi, optimistik boshlash; gamma ta'siri."""

import random

import numpy as np

XARITA = [
    "###########",
    "#         #",
    "#g S     G#",
    "#         #",
    "###########",
]
YONALISH = [(-1, 0), (0, 1), (1, 0), (0, -1)]


class Xona:
    """Robot S dan chiqadi. 'g' - yaqin zaryad nuqtasi (+1), 'G' - asosiy
    stansiya (+10). Ikkalasi ham epizodni tugatadi; qadam narxi yo'q,
    kelajak faqat gamma bilan 'arzonlashadi'. 100 qadamdan keyin kesiladi."""

    def __init__(self):
        self.kataklar = [(r, c) for r in range(len(XARITA))
                         for c in range(len(XARITA[0])) if XARITA[r][c] != "#"]
        self.idx = {k: i for i, k in enumerate(self.kataklar)}
        self.n_holat = len(self.kataklar)
        self.start = next(i for i, (r, c) in enumerate(self.kataklar)
                          if XARITA[r][c] == "S")

    def reset(self, seed=None):
        self.s, self.t = self.start, 0
        return self.s, {}

    def step(self, a):
        r, c = self.kataklar[self.s]
        nr, nc = r + YONALISH[a][0], c + YONALISH[a][1]
        if XARITA[nr][nc] != "#":
            self.s = self.idx[(nr, nc)]
        self.t += 1
        b = XARITA[nr][nc] if XARITA[nr][nc] != "#" else " "
        mukofot = {"g": 1.0, "G": 10.0}.get(b, 0.0)
        return self.s, mukofot, b in "gG", self.t >= 100, {"belgi": b}


def q_learning(urug, gamma=0.95, strategiya="eps0.1", epizodlar=300, alfa=0.5):
    rng = random.Random(urug)
    env = Xona()
    boshlangich = 10.0 if strategiya == "optimistik" else 0.0
    Q = [[boshlangich] * 4 for _ in range(env.n_holat)]
    oqitish = []
    for k in range(epizodlar):
        if strategiya == "ochkoz" or strategiya == "optimistik":
            eps = 0.0
        elif strategiya == "eps0.1":
            eps = 0.1
        elif strategiya == "eps0.3":
            eps = 0.3
        elif strategiya == "kamay-tez":               # 1.0 -> 0.05, 30% da
            eps = max(0.05, 1.0 - k / (0.3 * epizodlar))
        else:                                         # kamay-sekin: 80% da
            eps = max(0.05, 1.0 - k / (0.8 * epizodlar))
        s, _ = env.reset()
        jami = 0.0
        while True:
            if rng.random() < eps:
                a = rng.randrange(4)
            else:
                m = max(Q[s])
                a = rng.choice([i for i in range(4) if Q[s][i] == m])
            s2, r, tugadi, kesildi, _ = env.step(a)
            maqsad = r if tugadi else r + gamma * max(Q[s2])
            Q[s][a] += alfa * (maqsad - Q[s][a])
            jami += r
            s = s2
            if tugadi or kesildi:
                break
        oqitish.append(jami)
    return Q, np.array(oqitish)


def ochkoz_natija(Q):
    """eps = 0 bilan bitta epizod: qaysi nuqtaga borildi va necha qadamda."""
    env = Xona()
    s, _ = env.reset()
    for n in range(1, 101):
        s, r, tugadi, kesildi, info = env.step(int(np.argmax(Q[s])))
        if tugadi:
            return info["belgi"], n
    return "-", 100


def masofa(belgi):
    """BFS: S dan belgigacha eng qisqa qadamlar soni."""
    env = Xona()
    maqsad = next(i for i, (r, c) in enumerate(env.kataklar) if XARITA[r][c] == belgi)
    navbat, korilgan = [(env.start, 0)], {env.start}
    while navbat:
        s, d = navbat.pop(0)
        if s == maqsad:
            return d
        r, c = env.kataklar[s]
        for dr, dc in YONALISH:
            k = (r + dr, c + dc)
            if k in env.idx and env.idx[k] not in korilgan:
                korilgan.add(env.idx[k])
                navbat.append((env.idx[k], d + 1))
    return None


def main() -> None:
    urug = list(range(20))

    print("=== 1. Izlanish strategiyalari (gamma = 0.95, 300 epizod, 20 urug') ===")
    print(f"  S dan: g (+1) {masofa('g')} qadam, G (+10) {masofa('G')} qadam;"
          " optimal - G")
    strategiyalar = ["ochkoz", "eps0.1", "eps0.3", "kamay-tez", "kamay-sekin",
                     "optimistik"]
    print(f"  {'strategiya':<12} {'G topdi':>8} {'g da qoldi':>11} "
          f"{'o_qitishda o_rt.':>17} {'oxirgi 50':>10}")
    natija = {}
    for st in strategiyalar:
        oxirlar, ortacha, oxirgi = [], [], []
        for u in urug:
            Q, tarix = q_learning(u, strategiya=st)
            oxirlar.append(ochkoz_natija(Q)[0])
            ortacha.append(tarix.mean())
            oxirgi.append(tarix[-50:].mean())
        natija[st] = (np.array(ortacha), np.array(oxirgi))
        print(f"  {st:<12} {oxirlar.count('G'):>5}/20 {oxirlar.count('g'):>8}/20 "
              f"{np.mean(ortacha):>17.2f} {np.mean(oxirgi):>10.2f}")
    rng = random.Random(0)
    env = Xona()
    tasodifiy = []
    for _ in range(2000):
        env.reset()
        jami = 0.0
        while True:
            _, r, tugadi, kesildi, _ = env.step(rng.randrange(4))
            jami += r
            if tugadi or kesildi:
                break
        tasodifiy.append(jami)
    print(f"  tasodifiy siyosat (bazaviy): o'rtacha mukofot {np.mean(tasodifiy):.2f}")

    print("\n=== 2. Juftlashgan taqqoslash (oxirgi 50 epizod, 20 urug') ===")
    asos = natija["eps0.1"][1]
    for st in ["kamay-tez", "kamay-sekin", "optimistik"]:
        d = natija[st][1] - asos
        se = d.std(ddof=1) / np.sqrt(len(d))
        print(f"  {st:<11} - eps0.1: {d.mean():+6.2f}, SE {se:.2f}, "
              f"sezilarli: {abs(d.mean()) > 2 * se}")

    print("\n=== 3. Gamma ta'siri: robot qaysi nuqtani tanlaydi? ===")
    dg, dG = masofa("g"), masofa("G")
    print(f"  S dan masofa: g - {dg} qadam, G - {dG} qadam")
    print(f"  V(g yo'li) = gamma^{dg - 1} * 1,  V(G yo'li) = gamma^{dG - 1} * 10")
    chegara = 0.1 ** (1 / (dG - dg))
    print(f"  G yaxshi <=> gamma^{dG - dg} > 0.1 <=> gamma > {chegara:.3f}")
    print(f"  {'gamma':>6} {'ufq 1/(1-g)':>12} {'g qiymati':>10} {'G qiymati':>10} "
          f"{'nazariya':>9} {'Q-learning (G)':>15}")
    for g in [0.3, 0.5, 0.55, 0.6, 0.7, 0.9, 0.99]:
        tanlov = [ochkoz_natija(q_learning(u, gamma=g, strategiya="optimistik")[0])[0]
                  for u in urug[:10]]
        vg, vG = g ** (dg - 1) * 1, g ** (dG - 1) * 10
        nazariya = "G" if vG > vg else "g"
        print(f"  {g:>6} {1 / (1 - g):>12.1f} {vg:>10.3f} {vG:>10.3f} "
              f"{nazariya:>9} {tanlov.count('G'):>12}/10")
    print("  ⭐ gamma - vazifaning bir qismi: 'kelajak qanchalik muhim' degan qaror")


if __name__ == "__main__":
    main()

=== 1. Izlanish strategiyalari (gamma = 0.95, 300 epizod, 20 urug') ===
  S dan: g (+1) 2 qadam, G (+10) 6 qadam; optimal - G
  strategiya    G topdi  g da qoldi  o_qitishda o_rt.  oxirgi 50
  ochkoz           0/20       20/20              1.03       1.00
  eps0.1           0/20       20/20              1.04       1.00
  eps0.3           0/20       20/20              1.06       1.01
  kamay-tez        7/20       13/20              3.75       4.10
  kamay-sekin     19/20        1/20              8.25       9.55
  optimistik      20/20        0/20              9.89      10.00
  tasodifiy siyosat (bazaviy): o'rtacha mukofot 3.36

=== 2. Juftlashgan taqqoslash (oxirgi 50 epizod, 20 urug') ===
  kamay-tez   - eps0.1:  +3.10, SE 0.97, sezilarli: True
  kamay-sekin - eps0.1:  +8.55, SE 0.45, sezilarli: True
  optimistik  - eps0.1:  +9.00, SE 0.00, sezilarli: True

=== 3. Gamma ta'siri: robot qaysi nuqtani tanlaydi? ===
  S dan masofa: g - 2 qadam, G - 6 qadam
  V(g yo'li) = gamma^1 * 1,  V(G yo'li) = gamma^5 * 10
  G yaxshi <=> gamma^4 > 0.1 <=> gamma > 0.562
   gamma  ufq 1/(1-g)  g qiymati  G qiymati  nazariya  Q-learning (G)
     0.3          1.4      0.300      0.024         g            0/10
     0.5          2.0      0.500      0.312         g            0/10
    0.55          2.2      0.550      0.503         g            0/10
     0.6          2.5      0.600      0.778         G           10/10
     0.7          3.3      0.700      1.681         G           10/10
     0.9         10.0      0.900      5.905         G           10/10
    0.99        100.0      0.990      9.510         G           10/10
  ⭐ gamma - vazifaning bir qismi: 'kelajak qanchalik muhim' degan qaror

Q[s, a] += alfa * (r + gamma * Q[s2].max() - Q[s, a])                  # ⚠️
Q[s, a] += alfa * (r + gamma * Q[s2].max() * (not tugadi) - Q[s, a])   # ✅

if tugadi or kesildi: maqsad = r                                        # ⚠️
maqsad = r if tugadi else r + gamma * Q[s2].max()                       # ✅ kesilganda bootstrap

a = int(np.argmax(Q[s]))                                                # ⚠️ eps = 0, Q = 0
a = rng.integers(4) if rng.random() < eps else int(np.argmax(Q[s]))    # ✅ + eps kamayishi

a = int(np.argmax(Q[s]))                                                # ⚠️ boshida doim "yuqori"
a = rng.choice(np.flatnonzero(Q[s] == Q[s].max()))                      # ✅ tasodifiy tanlov

print(np.mean(mukofotlar[-100:]))                                       # ⚠️ eps-siyosat
print(ochkoz_baholash(Q, epizodlar=100))                                # ✅ eps = 0 alohida

natija = orgat(urug=0)                                                  # ⚠️
natija = [orgat(urug=u) for u in range(10)]                             # ✅ o'rtacha, SE, juftlashgan farq

pi = value_iteration(Ombor(s_hol=0.0), gamma)                           # ⚠️ sirpanish yo'q deb
pi = value_iteration(Ombor(s_hol=0.2), gamma)                           # ✅ haqiqiy dinamika

1.  # bandit va RL ning ikki asosiy farqi?
2.  # gamma = 0.9 da effektiv ufq?
3.  # V^pi ni model ma'lum bo'lsa qanday aniq topish mumkin?
4.  # policy iteration va value iteration: qaysi biri kam iteratsiya qiladi?
5.  # sirpanishni bilmagan siyosat sirpanchiq omborda yiqilish ehtimoli?
6.  # MC va TD(0): qaysi biri bootstrap qiladi?
7.  # TD(0) 1/N qadam bilan nima bo'ldi?
8.  # jarlik yoqasida o'rganish paytida kim yaxshiroq?
9.  # jarlik yoqasida ochko'z siyosat bo'yicha kim yaxshiroq?
10. # eps = 0.1 bilan uzoqdagi +10 topildimi?
11. # optimistik boshlash nima uchun ishlaydi?
12. # 4-misolda gamma chegarasi?

1.  Q[s, a] += alfa * (r + gamma * Q[s2].max() - Q[s, a])     # s2 terminal bo'lishi mumkin

2.  if tugadi or kesildi:
        maqsad = r

3.  a = int(np.argmax(Q[s]))                                   # Q = 0 dan boshlanadi, eps yo'q

4.  natija = orgat("Q-learning", urug=0)
    print("Q-learning yaxshiroq:", natija > orgat("SARSA", urug=0))

5.  print("siyosat sifati:", np.mean(oqitish_mukofotlari[-100:]))