Практика 39 · Учень без учителя (навчання з підкріпленням)¶
📖 Теорія: відкрий
lecture.htmlу цій же теці. 📝 Домашнє завдання:homework.md· 🧪 Тест:quiz.html
Тут ми напишемо з нуля все, що бачили в інтерактивах лекції: ε-жадібного бандита, табличне Q-навчання й точний розвʼязок через динамічне програмування, з яким можна звірити результат.
Що зробимо:
- Багаторукий бандит: оцінки Q збігаються до справжніх середніх
- Порівняємо ε = 0, 0.1, 0.5, 1 за накопиченим жалем (regret) проти оракула
- Розберемо один крок Q-навчання по числах — звідки береться δ
- Побачимо, як γ керує далекоглядністю, у світі-лінії
- Напишемо табличне Q-навчання для сітки з кактусами
- Звіримо вивчену політику з точною — і побачимо парадокс великого ε
1. Багаторукий бандит¶
Найпростіший випадок: станів немає, часу немає, є лише вибір. Перед роботом три дерева. Кожне дає випадкову кількість бананів зі своїм середнім, якого робот не знає.
Робот веде для кожної дії оцінку Q(a) — середню винагороду з усіх разів, коли він цю дію обирав. Оновлювати середнє зручно по одному спостереженню:
Q(a) ← Q(a) + (1/n)·[ r − Q(a) ]
Придивись до форми: у квадратних дужках стоїть різниця між тим, що сталось, і тим, чого ми чекали. Оцінка зсувається в бік несподіванки. Ця сама форма зустрінеться нам ще двічі.
In [1]:
import numpy as np
import matplotlib.pyplot as plt
СЕРЕДНІ = np.array([3.0, 6.0, 4.5]) # справжні середні дерев A, B, C
РОЗКИДИ = np.array([1.0, 2.0, 1.5]) # робот їх не знає
НАЗВИ = ["дерево A", "дерево B", "дерево C"]
НАЙКРАЩА_ДІЯ = int(np.argmax(СЕРЕДНІ))
def зіграти_в_бандита(епсилон, кроків, зерно):
"""Один запуск ε-жадібного агента. Повертає історію оцінок і накопичену винагороду."""
генератор = np.random.default_rng(зерно)
оцінки = np.zeros(len(СЕРЕДНІ)) # Q(a): починаємо з нуля — робот нічого не знає
скільки_разів = np.zeros(len(СЕРЕДНІ))
історія_оцінок = np.zeros((кроків, len(СЕРЕДНІ)))
накопичено = np.zeros(кроків)
зібрано = 0.0
оптимальних = 0
for крок in range(кроків):
# ε-жадібність: з імовірністю ε пробуємо випадкове дерево
if генератор.random() < епсилон:
дія = int(генератор.integers(len(СЕРЕДНІ)))
else:
дія = int(np.argmax(оцінки))
винагорода = СЕРЕДНІ[дія] + РОЗКИДИ[дія] * генератор.normal()
# те саме оновлення «оцінка + крок × несподіванка»
скільки_разів[дія] += 1
оцінки[дія] += (винагорода - оцінки[дія]) / скільки_разів[дія]
зібрано += винагорода
оптимальних += (дія == НАЙКРАЩА_ДІЯ)
історія_оцінок[крок] = оцінки
накопичено[крок] = зібрано
return {"оцінки": оцінки, "скільки_разів": скільки_разів,
"історія": історія_оцінок, "накопичено": накопичено,
"зібрано": зібрано, "частка_оптимальних": оптимальних / кроків}
print(f"{'дерево':>12} {'справжнє середнє':>18} {'розкид':>9}")
for номер, назва in enumerate(НАЗВИ):
зірочка = " ← найкраще" if номер == НАЙКРАЩА_ДІЯ else ""
print(f"{назва:>12} {СЕРЕДНІ[номер]:18.1f} {РОЗКИДИ[номер]:9.1f}{зірочка}")
print("\nРобот цих чисел не бачить. Він може лише пробувати й дивитись на результат.")
дерево справжнє середнє розкид
дерево A 3.0 1.0
дерево B 6.0 2.0 ← найкраще
дерево C 4.5 1.5
Робот цих чисел не бачить. Він може лише пробувати й дивитись на результат.
Оцінки збігаються до справжніх середніх¶
Запустимо ε = 0.1 на 400 кроків і подивимось, як три криві Q(a) підповзають до пунктирних ліній справжніх середніх.
In [2]:
КРОКІВ = 400
запуск = зіграти_в_бандита(0.1, КРОКІВ, зерно=1000)
fig, (ліва, права) = plt.subplots(1, 2, figsize=(13, 4.4))
кольори = ["gray", "teal", "darkorange"]
for номер, (назва, колір) in enumerate(zip(НАЗВИ, кольори)):
ліва.plot(запуск["історія"][:, номер], lw=2, color=колір, label=назва)
ліва.axhline(СЕРЕДНІ[номер], color=колір, ls="--", lw=1.2)
ліва.set_xlabel("крок"); ліва.set_ylabel("оцінка Q(a)")
ліва.set_title("Оцінки підповзають до справжніх середніх (пунктир)")
ліва.legend(); ліва.grid(alpha=.25)
оракул = СЕРЕДНІ[НАЙКРАЩА_ДІЯ] * np.arange(1, КРОКІВ + 1)
навмання = СЕРЕДНІ.mean() * np.arange(1, КРОКІВ + 1)
права.plot(оракул, lw=2, color="teal", ls="--", label="оракул (завжди найкраще)")
права.plot(запуск["накопичено"], lw=2.4, color="crimson", label="наш агент, ε = 0.1")
права.plot(навмання, lw=2, color="gray", ls=":", label="випадковий вибір")
права.set_xlabel("крок"); права.set_ylabel("накопичено бананів")
права.set_title("Накопичена винагорода проти оракула")
права.legend(); права.grid(alpha=.25)
plt.tight_layout(); plt.show()
print(f"{'дерево':>12} {'справжнє':>10} {'оцінка Q':>10} {'разів обрано':>14}")
for номер, назва in enumerate(НАЗВИ):
print(f"{назва:>12} {СЕРЕДНІ[номер]:10.2f} {запуск['оцінки'][номер]:10.2f} "
f"{int(запуск['скільки_разів'][номер]):14d}")
print(f"\nчастка оптимальних дій: {запуск['частка_оптимальних']:.3f}")
print(f"жаль (regret) проти оракула: {оракул[-1] - запуск['зібрано']:.0f} бананів")
дерево справжнє оцінка Q разів обрано
дерево A 3.00 2.59 25
дерево B 6.00 6.11 343
дерево C 4.50 4.60 32
частка оптимальних дій: 0.858
жаль (regret) проти оракула: 94 бананів
Порівнюємо ε: скільки коштує дослідження¶
Один запуск нічого не доводить — результат сильно залежить від зерна випадковості. Тому усереднимо по 200 незалежних запусках. Це, до речі, і є правило з лекції: порівнювати два RL-алгоритми за одним запуском безглуздо.
In [3]:
ЗАПУСКІВ = 200
def усереднити(епсилон, кроків=КРОКІВ, запусків=ЗАПУСКІВ):
"""Середні показники ε-жадібного агента по багатьох незалежних запусках."""
оцінки, зібрано, оптимальних = [], [], []
for номер_запуску in range(запусків):
результат = зіграти_в_бандита(епсилон, кроків, зерно=1000 + номер_запуску)
оцінки.append(результат["оцінки"])
зібрано.append(результат["зібрано"])
оптимальних.append(результат["частка_оптимальних"])
оцінки = np.array(оцінки)
оракул = СЕРЕДНІ[НАЙКРАЩА_ДІЯ] * кроків
return {
"середні_оцінки": оцінки.mean(axis=0),
"жаль": оракул - np.mean(зібрано),
"середня_винагорода": np.mean(зібрано) / кроків,
"частка_оптимальних": np.mean(оптимальних),
}
ЗВЕДЕННЯ = {ε: усереднити(ε) for ε in [0.0, 0.05, 0.1, 0.3, 0.5, 1.0]}
print(f"{'ε':>6} {'оптимальних дій':>17} {'сер. винагорода':>17} {'жаль проти оракула':>20} "
f"{'макс. похибка Q':>17}")
for ε, дані in ЗВЕДЕННЯ.items():
похибка_оцінок = np.max(np.abs(дані["середні_оцінки"] - СЕРЕДНІ))
print(f"{ε:>6} {дані['частка_оптимальних']:17.3f} {дані['середня_винагорода']:17.3f} "
f"{дані['жаль']:20.0f} {похибка_оцінок:17.3f}")
print("\nЩо читати:")
print("ε = 0 — чиста жадібність. Робот зупинився на першому ж дереві, що дало")
print(" щось позитивне. Оцінки решти дерев так і лишились нульовими:")
print(f" {np.round(ЗВЕДЕННЯ[0.0]['середні_оцінки'], 2)}")
print("ε = 1 — чиста випадковість. Оцінки найточніші з усіх, зате знання ніяк")
print(" не використовується: зібрано стільки ж, скільки при випадковому виборі.")
print("ε = 0.1 — баланс: найменший жаль з усіх.")
ε оптимальних дій сер. винагорода жаль проти оракула макс. похибка Q
0.0 0.000 2.997 1201 6.000
0.05 0.787 5.545 182 0.046
0.1 0.850 5.666 134 0.013
0.3 0.781 5.510 196 0.008
0.5 0.655 5.223 311 0.016
1.0 0.336 4.505 598 0.008
Що читати:
ε = 0 — чиста жадібність. Робот зупинився на першому ж дереві, що дало
щось позитивне. Оцінки решти дерев так і лишились нульовими:
[3. 0. 0.]
ε = 1 — чиста випадковість. Оцінки найточніші з усіх, зате знання ніяк
не використовується: зібрано стільки ж, скільки при випадковому виборі.
ε = 0.1 — баланс: найменший жаль з усіх.
In [4]:
жалі = np.array([ЗВЕДЕННЯ[ε]["жаль"] for ε in ЗВЕДЕННЯ])
епсилони = np.array(list(ЗВЕДЕННЯ.keys()))
fig, (ліва, права) = plt.subplots(1, 2, figsize=(13, 4.2))
for ε, колір in zip([0.0, 0.1, 0.5, 1.0], ["gray", "teal", "darkorange", "crimson"]):
запуск_ε = зіграти_в_бандита(ε, КРОКІВ, зерно=1000)
жаль_у_часі = СЕРЕДНІ[НАЙКРАЩА_ДІЯ] * np.arange(1, КРОКІВ + 1) - запуск_ε["накопичено"]
ліва.plot(жаль_у_часі, lw=2.2, color=колір, label=f"ε = {ε}")
ліва.set_xlabel("крок"); ліва.set_ylabel("накопичений жаль")
ліва.set_title("Жаль росте лінійно, якщо не досліджувати або досліджувати завжди")
ліва.legend(); ліва.grid(alpha=.25)
права.plot(епсилони, жалі, marker="o", lw=2.4, color="teal")
права.set_xlabel("ε"); права.set_ylabel("жаль за 400 кроків (середнє з 200 запусків)")
права.set_title("Оптимум десь біля 0.1"); права.grid(alpha=.25)
plt.tight_layout(); plt.show()
найкращий_ε = min(ЗВЕДЕННЯ, key=lambda ε: ЗВЕДЕННЯ[ε]["жаль"])
print(f"найменший жаль дає ε = {найкращий_ε}")
assert ЗВЕДЕННЯ[0.1]["жаль"] < ЗВЕДЕННЯ[0.0]["жаль"], "дослідження мало допомогти!"
assert ЗВЕДЕННЯ[0.1]["жаль"] < ЗВЕДЕННЯ[1.0]["жаль"], "надмір дослідження мав шкодити!"
assert np.max(np.abs(ЗВЕДЕННЯ[1.0]["середні_оцінки"] - СЕРЕДНІ)) < 0.1, \
"при ε = 1 оцінки мали зійтись до справжніх середніх!"
print("\n✅ ε = 0.1 програє оракулу менше, ніж і чиста жадібність, і чиста випадковість")
print("✅ при ε = 1 оцінки Q зійшлися до справжніх середніх з похибкою < 0.1")
найменший жаль дає ε = 0.1 ✅ ε = 0.1 програє оракулу менше, ніж і чиста жадібність, і чиста випадковість ✅ при ε = 1 оцінки Q зійшлися до справжніх середніх з похибкою < 0.1
2. Один крок Q-навчання¶
Тепер додамо стани й час. Агент був у стані s, зробив дію a, отримав винагороду r і опинився в s'. У нас є дві оцінки однієї й тієї самої величини:
- стара, з таблиці: Q(s, a);
- щойно отримана з реальності: r + γ·max Q(s', a').
Друга спирається на один справжній крок, тож вона трохи ближча до істини. Різницю між ними називають похибкою часової різниці:
δ = r + γ·max Q(s', a') − Q(s, a), далі Q(s, a) ← Q(s, a) + α·δ
Порахуємо це руками на числах з інтерактиву лекції.
In [5]:
стара_оцінка = 2.0 # Q(s, a) з таблиці
винагорода = 1.0 # r, яку видало середовище
найкраще_далі = 7.0 # max Q(s', a') — на що можна розраховувати в новому стані
гамма = 0.9
альфа = 0.3
ціль = винагорода + гамма * найкраще_далі
похибка = ціль - стара_оцінка
нова_оцінка = стара_оцінка + альфа * похибка
print(f"що ми думали Q(s,a) = {стара_оцінка:.2f}")
print(f"що показала реальність ціль = r + γ·max Q(s',a') = "
f"{винагорода:.2f} + {гамма} · {найкраще_далі:.2f} = {ціль:.2f}")
print(f"похибка часової різниці δ = {ціль:.2f} − {стара_оцінка:.2f} = {похибка:.2f}")
print(f"новий запис у таблиці Q = {стара_оцінка:.2f} + {альфа} · {похибка:.2f} = {нова_оцінка:.3f}")
# що буде, якщо повторити той самий крок багато разів поспіль
оцінка = стара_оцінка
шлях = [оцінка]
for _ in range(20):
оцінка = оцінка + альфа * (ціль - оцінка)
шлях.append(оцінка)
fig, ax = plt.subplots(figsize=(9, 3.8))
ax.plot(шлях, marker="o", lw=2.2, color="teal", label="Q(s,a) після кожного повторення")
ax.axhline(ціль, color="crimson", ls="--", lw=1.8, label=f"ціль = {ціль:.2f}")
ax.set_xlabel("скільки разів повторили той самий крок"); ax.set_ylabel("Q(s,a)")
ax.set_title("Оцінка експоненційно наближається до цілі, швидкість задає α")
ax.legend(); ax.grid(alpha=.25)
plt.tight_layout(); plt.show()
print(f"\nчерез 20 повторень Q = {шлях[-1]:.4f}, ціль = {ціль:.2f}")
assert abs(шлях[-1] - ціль) < 0.01, "оцінка мала майже дійти до цілі!"
print("\n✅ оцінка зійшлася до цілі. При α = 1 вона стрибнула б туди одразу —")
print(" і разом із нею стрибнув би весь шум, який у цій цілі є.")
що ми думали Q(s,a) = 2.00 що показала реальність ціль = r + γ·max Q(s',a') = 1.00 + 0.9 · 7.00 = 7.30 похибка часової різниці δ = 7.30 − 2.00 = 5.30 новий запис у таблиці Q = 2.00 + 0.3 · 5.30 = 3.590
через 20 повторень Q = 7.2958, ціль = 7.30 ✅ оцінка зійшлася до цілі. При α = 1 вона стрибнула б туди одразу — і разом із нею стрибнув би весь шум, який у цій цілі є.
3. Як γ керує далекоглядністю¶
Світ-лінія з одинадцяти клітинок. Ліворуч маленьке дерево (+3), праворуч велике (+10). Обидва завершують епізод. Кожен крок нічого не коштує.
Коефіцієнт дисконтування γ каже, наскільки знецінюється винагорода, отримана через k кроків: вона входить у суму з вагою γ^k. Грубо кажучи, агент бачить приблизно на 1/(1−γ) кроків уперед. Порахуємо оптимальну політику точно — динамічним програмуванням — і подивимось, з якої γ клітинки біля лівого краю «здаються».
In [6]:
ДОВЖИНА_ЛІНІЇ = 11
МАЛЕНЬКЕ_ДЕРЕВО = 3.0 # за крок ліворуч із клітинки 0
ВЕЛИКЕ_ДЕРЕВО = 10.0 # за крок праворуч із клітинки 10
def цінності_лінії(гамма, ітерацій=500):
"""Точний розвʼязок ітерацією по цінностях: середовище нам відоме, тому можна.
Повертає (цінності станів, політику як рядок зі стрілок).
"""
цінності = np.zeros(ДОВЖИНА_ЛІНІЇ)
for _ in range(ітерацій):
нові = цінності.copy()
for стан in range(ДОВЖИНА_ЛІНІЇ):
варіанти = []
for напрямок in (-1, +1):
сусід = стан + напрямок
if сусід < 0:
варіанти.append(МАЛЕНЬКЕ_ДЕРЕВО) # вийшли ліворуч — епізод скінчився
elif сусід >= ДОВЖИНА_ЛІНІЇ:
варіанти.append(ВЕЛИКЕ_ДЕРЕВО) # вийшли праворуч — теж
else:
варіанти.append(гамма * цінності[сусід])
нові[стан] = max(варіанти)
цінності = нові
політика = ""
for стан in range(ДОВЖИНА_ЛІНІЇ):
ліворуч = МАЛЕНЬКЕ_ДЕРЕВО if стан == 0 else гамма * цінності[стан - 1]
праворуч = ВЕЛИКЕ_ДЕРЕВО if стан == ДОВЖИНА_ЛІНІЇ - 1 else гамма * цінності[стан + 1]
політика += "←" if ліворуч > праворуч else "→"
return цінності, політика
print(f"{'γ':>6} {'горизонт 1/(1−γ)':>18} {'ідуть ліворуч':>15} політика")
кількість_лівих = {}
for гамма_значення in [0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99]:
цінності, політика = цінності_лінії(гамма_значення)
кількість_лівих[гамма_значення] = політика.count("←")
print(f"{гамма_значення:>6} {1 / (1 - гамма_значення):18.1f} "
f"{політика.count('←'):15d} {політика}")
assert кількість_лівих[0.5] > кількість_лівих[0.9], "мала γ мала робити агента короткозорим!"
assert кількість_лівих[0.9] == 0, "при γ = 0.9 усі мали йти до великого дерева!"
print("\n✅ при великій γ навіть із крайньої лівої клітинки вигідно пройти всю лінію")
print(" до великого дерева. Знижуй γ — і клітинки біля лівого краю одна за одною")
print(" «здаються»: для них десять бананів через девʼять кроків коштують уже менше,")
print(" ніж три банани через один.")
γ горизонт 1/(1−γ) ідуть ліворуч політика 0.5 2.0 5 ←←←←←→→→→→→ 0.6 2.5 4 ←←←←→→→→→→→ 0.7 3.3 4 ←←←←→→→→→→→ 0.8 5.0 3 ←←←→→→→→→→→ 0.9 10.0 0 →→→→→→→→→→→ 0.95 20.0 0 →→→→→→→→→→→ 0.99 100.0 0 →→→→→→→→→→→ ✅ при великій γ навіть із крайньої лівої клітинки вигідно пройти всю лінію до великого дерева. Знижуй γ — і клітинки біля лівого краю одна за одною «здаються»: для них десять бананів через девʼять кроків коштують уже менше, ніж три банани через один.
In [7]:
fig, ax = plt.subplots(figsize=(10, 4.2))
for гамма_значення, колір in zip([0.5, 0.7, 0.9], ["crimson", "darkorange", "teal"]):
цінності, _ = цінності_лінії(гамма_значення)
ax.plot(range(ДОВЖИНА_ЛІНІЇ), цінності, marker="o", lw=2.2, color=колір,
label=f"γ = {гамма_значення}")
ax.set_xlabel("клітинка світу-лінії (0 — біля маленького дерева, 10 — біля великого)")
ax.set_ylabel("цінність стану V(s)")
ax.set_title("Що більша γ, то далі «дотягується» цінність великого дерева")
ax.legend(); ax.grid(alpha=.25)
plt.tight_layout(); plt.show()
print("Маленька γ робить агента короткозорим: він хапає найближчу винагороду,")
print("навіть якщо трохи далі лежить набагато більша.")
Маленька γ робить агента короткозорим: він хапає найближчу винагороду, навіть якщо трохи далі лежить набагато більша.
4. Табличне Q-навчання в сітці з кактусами¶
Тепер справжня задача. Робот ходить у чотирьох напрямках по сітці 5 × 6. Десь лежать банани (+10, кінець епізоду), десь ростуть кактуси (−10, теж кінець), а кожен крок коштує невеликої плати −0.2.
Ця плата — важлива деталь: без неї агенту байдуже, чи йти до мети десять кроків, чи сто.
В алгоритмі нічого нового немає: та сама таблиця Q, те саме оновлення через δ. Змінилась лише кількість станів і дій.
In [8]:
КАРТА = [
"......",
".##...",
"....#.",
".#....",
"..#..G",
]
РЯДКІВ, СТОВПЦІВ = len(КАРТА), len(КАРТА[0])
ПЛАТА_ЗА_КРОК = -0.2
НАГОРОДА_ЗА_БАНАНИ = 10.0
ШТРАФ_ЗА_КАКТУС = -10.0
ГАММА = 0.95
# 0 — ліворуч, 1 — праворуч, 2 — угору, 3 — униз
ЗСУВ_РЯДКА = [0, 0, -1, +1]
ЗСУВ_СТОВПЦЯ = [-1, +1, 0, 0]
СТРІЛКИ = ["←", "→", "↑", "↓"]
def вільна(рядок, стовпець):
"""Клітинка, у якій робот може стояти: не кактус і не мета."""
return КАРТА[рядок][стовпець] == "."
def зробити_крок(рядок, стовпець, дія):
"""Повертає (новий рядок, новий стовпець, винагорода, чи скінчився епізод)."""
новий_рядок = рядок + ЗСУВ_РЯДКА[дія]
новий_стовпець = стовпець + ЗСУВ_СТОВПЦЯ[дія]
# стіна по краю: робот просто лишається на місці
if not (0 <= новий_рядок < РЯДКІВ and 0 <= новий_стовпець < СТОВПЦІВ):
новий_рядок, новий_стовпець = рядок, стовпець
клітинка = КАРТА[новий_рядок][новий_стовпець]
if клітинка == "#":
return новий_рядок, новий_стовпець, ШТРАФ_ЗА_КАКТУС, True
if клітинка == "G":
return новий_рядок, новий_стовпець, НАГОРОДА_ЗА_БАНАНИ, True
return новий_рядок, новий_стовпець, ПЛАТА_ЗА_КРОК, False
ВІЛЬНІ_КЛІТИНКИ = [(р, с) for р in range(РЯДКІВ) for с in range(СТОВПЦІВ) if вільна(р, с)]
for рядок in КАРТА:
print(" " + " ".join(рядок))
print(f"\n{len(ВІЛЬНІ_КЛІТИНКИ)} вільних клітинок, 4 дії, отже таблиця Q має "
f"{len(ВІЛЬНІ_КЛІТИНКИ) * 4} чисел")
print("# — кактус (−10, кінець), G — банани (+10, кінець), . — звичайна клітинка (−0.2)")
. . . . . . . # # . . . . . . . # . . # . . . . . . # . . G 24 вільних клітинок, 4 дії, отже таблиця Q має 96 чисел # — кактус (−10, кінець), G — банани (+10, кінець), . — звичайна клітинка (−0.2)
Спочатку — точний розвʼязок¶
Середовище нам відоме, тому оптимальну політику можна порахувати точно, не навчаючись: ітерацією по цінностях. Це буде еталон, з яким ми звіримо результат Q-навчання. Саме так у навчальних задачах перевіряють, чи алгоритм збігся.
In [9]:
def точний_розвʼязок(ітерацій=400):
"""Ітерація по цінностях. Повертає (V, Q-таблиця еталона)."""
цінності = np.zeros((РЯДКІВ, СТОВПЦІВ))
for _ in range(ітерацій):
for рядок, стовпець in ВІЛЬНІ_КЛІТИНКИ:
найкраще = -np.inf
for дія in range(4):
нр, нс, винагорода, кінець = зробити_крок(рядок, стовпець, дія)
значення = винагорода + (0.0 if кінець else ГАММА * цінності[нр, нс])
найкраще = max(найкраще, значення)
цінності[рядок, стовпець] = найкраще
еталонні_Q = np.full((РЯДКІВ, СТОВПЦІВ, 4), np.nan)
for рядок, стовпець in ВІЛЬНІ_КЛІТИНКИ:
for дія in range(4):
нр, нс, винагорода, кінець = зробити_крок(рядок, стовпець, дія)
еталонні_Q[рядок, стовпець, дія] = винагорода + (0.0 if кінець else ГАММА * цінності[нр, нс])
return цінності, еталонні_Q
ЕТАЛОННІ_ЦІННОСТІ, ЕТАЛОННІ_Q = точний_розвʼязок()
print("цінність V(s) у кожній клітинці (0.00 — кактус або мета):")
for рядок in range(РЯДКІВ):
print(" " + " ".join(f"{ЕТАЛОННІ_ЦІННОСТІ[рядок, с]:6.2f}" for с in range(СТОВПЦІВ)))
print("\nоптимальна політика:")
for рядок in range(РЯДКІВ):
рядок_стрілок = []
for стовпець in range(СТОВПЦІВ):
if not вільна(рядок, стовпець):
рядок_стрілок.append(КАРТА[рядок][стовпець])
else:
рядок_стрілок.append(СТРІЛКИ[int(np.argmax(ЕТАЛОННІ_Q[рядок, стовпець]))])
print(" " + " ".join(рядок_стрілок))
цінність V(s) у кожній клітинці (0.00 — кактус або мета):
5.29 5.78 6.29 6.83 7.40 8.00
5.78 0.00 0.00 7.40 8.00 8.64
6.29 6.83 7.40 8.00 0.00 9.30
5.78 0.00 8.00 8.64 9.30 10.00
5.29 4.82 0.00 9.30 10.00 0.00
оптимальна політика:
→ → → → → ↓
↓ # # → → ↓
→ → → ↓ # ↓
↑ # → → → ↓
↑ ← # → → G
Тепер вчимось самі¶
Робот не знає ні карти, ні винагород. Він просто ходить і оновлює таблицю через δ. Стартує щоразу у випадковій клітинці — це важливо, інакше жадібний агент ніколи б не побачив половину світу.
In [10]:
КРОК_НАВЧАННЯ = 0.2 # α
def навчити_Q(епсилон, епізодів, зерно=9091, максимум_кроків=80):
"""Табличне Q-навчання. Повертає таблицю Q і статистику по епізодах."""
генератор = np.random.default_rng(зерно)
таблиця = np.zeros((РЯДКІВ, СТОВПЦІВ, 4))
дійшли_до_мети = 0
вкололись = 0
for _ in range(епізодів):
рядок, стовпець = ВІЛЬНІ_КЛІТИНКИ[генератор.integers(len(ВІЛЬНІ_КЛІТИНКИ))]
for _ in range(максимум_кроків):
if генератор.random() < епсилон:
дія = int(генератор.integers(4))
else:
дія = int(np.argmax(таблиця[рядок, стовпець]))
нр, нс, винагорода, кінець = зробити_крок(рядок, стовпець, дія)
# ціль: винагорода плюс найкраще, на що можна розраховувати далі
ціль = винагорода + (0.0 if кінець else ГАММА * таблиця[нр, нс].max())
похибка = ціль - таблиця[рядок, стовпець, дія]
таблиця[рядок, стовпець, дія] += КРОК_НАВЧАННЯ * похибка
рядок, стовпець = нр, нс
if кінець:
дійшли_до_мети += (винагорода > 0)
вкололись += (винагорода < 0)
break
return таблиця, дійшли_до_мети / епізодів, вкололись / епізодів
def збіг_з_еталоном(таблиця):
"""Частка клітинок, де вивчена стрілка є однією з оптимальних (нічиї теж рахуємо)."""
збіглось = 0
for рядок, стовпець in ВІЛЬНІ_КЛІТИНКИ:
обрана = int(np.argmax(таблиця[рядок, стовпець]))
найкраще = ЕТАЛОННІ_Q[рядок, стовпець].max()
if ЕТАЛОННІ_Q[рядок, стовпець, обрана] >= найкраще - 1e-9:
збіглось += 1
return збіглось / len(ВІЛЬНІ_КЛІТИНКИ)
таблиця_Q, частка_мети, частка_кактусів = навчити_Q(епсилон=0.15, епізодів=1500)
print(f"епізодів: 1500, ε = 0.15, α = {КРОК_НАВЧАННЯ}, γ = {ГАММА}\n")
print(f"дійшли до бананів: {частка_мети:.2f}")
print(f"вкололись у кактус: {частка_кактусів:.2f}")
print(f"збіг політики з еталоном: {збіг_з_еталоном(таблиця_Q):.2f}")
assert збіг_з_еталоном(таблиця_Q) > 0.9, "вивчена політика мала майже збігтись з еталоном!"
print("\n✅ агент вивчив політику, яка майже всюди збігається з точним розвʼязком")
епізодів: 1500, ε = 0.15, α = 0.2, γ = 0.95
дійшли до бананів: 0.85 вкололись у кактус: 0.15 збіг політики з еталоном: 0.96 ✅ агент вивчив політику, яка майже всюди збігається з точним розвʼязком
Малюємо політику стрілками¶
Колір клітинки — цінність V(s) = max Q(s, ·). Стрілка — вивчена політика. Ліворуч еталон із динамічного програмування, праворуч — те, чого агент навчився сам.
In [11]:
def намалювати_політику(вісь, значення, дії, заголовок):
"""Кольорова карта цінностей плюс стрілка політики в кожній вільній клітинці."""
полотно = np.full((РЯДКІВ, СТОВПЦІВ), np.nan)
for рядок, стовпець in ВІЛЬНІ_КЛІТИНКИ:
полотно[рядок, стовпець] = значення[рядок, стовпець]
вісь.imshow(полотно, cmap="YlGn", vmin=np.nanmin(полотно), vmax=np.nanmax(полотно))
for рядок in range(РЯДКІВ):
for стовпець in range(СТОВПЦІВ):
символ = КАРТА[рядок][стовпець]
if символ == "#":
вісь.text(стовпець, рядок, "кактус", ha="center", va="center",
fontsize=10, color="crimson", fontweight="bold")
elif символ == "G":
вісь.text(стовпець, рядок, "МЕТА", ha="center", va="center",
fontsize=11, color="darkgreen", fontweight="bold")
else:
напрямок = int(np.argmax(дії[рядок, стовпець]))
вісь.text(стовпець, рядок, СТРІЛКИ[напрямок], ha="center", va="center",
fontsize=20, color="black")
вісь.text(стовпець, рядок + 0.34, f"{значення[рядок, стовпець]:.1f}",
ha="center", va="center", fontsize=8, color="dimgray")
вісь.set_xticks(range(СТОВПЦІВ)); вісь.set_yticks(range(РЯДКІВ))
вісь.set_title(заголовок)
вивчені_цінності = np.zeros((РЯДКІВ, СТОВПЦІВ))
for рядок, стовпець in ВІЛЬНІ_КЛІТИНКИ:
вивчені_цінності[рядок, стовпець] = таблиця_Q[рядок, стовпець].max()
fig, (ліва, права) = plt.subplots(1, 2, figsize=(13, 5))
намалювати_політику(ліва, ЕТАЛОННІ_ЦІННОСТІ, np.nan_to_num(ЕТАЛОННІ_Q, nan=-1e9),
"Еталон: динамічне програмування")
намалювати_політику(права, вивчені_цінності, таблиця_Q,
"Вивчено самим агентом за 1500 епізодів")
plt.tight_layout(); plt.show()
print("Стрілки складаються в маршрут, який обходить кактуси. Нічого схожого")
print("на «планування» в алгоритм не закладено — воно виникло само собою з того,")
print("що оцінка одного стану підтягується до оцінки сусіднього.")
Стрілки складаються в маршрут, який обходить кактуси. Нічого схожого на «планування» в алгоритм не закладено — воно виникло само собою з того, що оцінка одного стану підтягується до оцінки сусіднього.
5. Парадокс великого ε¶
Останнє й найважливіше спостереження лекції. Збільшуючи ε, ми покращуємо таблицю (агент бачить більше станів, оцінки точніші) і водночас псуємо поведінку (кожен випадковий крок поруч із кактусом може виявитись останнім).
Перевіримо це числами. Тримай в голові одну деталь нашого стенду: старт випадковий, тому агент і без ε бачить усі клітинки. Дослідження тут майже нічого не додає до таблиці — зате виразно псує поведінку.
In [12]:
print(f"{'ε':>6} {'епізодів':>10} {'дійшли до мети':>16} {'вкололись':>11} "
f"{'збіг політики':>15}")
зведення_сітки = {}
for ε in [0.0, 0.05, 0.15, 0.35, 0.6]:
for епізодів in [300, 1500]:
таблиця, мета, кактус = навчити_Q(ε, епізодів)
збіг = збіг_з_еталоном(таблиця)
зведення_сітки[(ε, епізодів)] = (мета, кактус, збіг)
print(f"{ε:>6} {епізодів:>10} {мета:16.2f} {кактус:11.2f} {збіг:15.2f}")
частки_кактусів = [зведення_сітки[(ε, 1500)][1] for ε in [0.0, 0.05, 0.15, 0.35, 0.6]]
збіги = [зведення_сітки[(ε, 1500)][2] for ε in [0.0, 0.05, 0.15, 0.35, 0.6]]
print(f"\nчастка епізодів у кактусі по ε: {[round(v, 2) for v in частки_кактусів]}")
print(f"збіг політики з еталоном по ε: {[round(v, 2) for v in збіги]}")
assert all(частки_кактусів[k] < частки_кактусів[k + 1] for k in range(len(частки_кактусів) - 1)), \
"частка уколів мала рости з ε!"
assert min(збіги) > 0.9, "таблиця мала лишитись доброю за будь-якого ε!"
print("\n✅ частка уколів росте з ε монотонно: від "
f"{частки_кактусів[0]:.2f} до {частки_кактусів[-1]:.2f}")
print(f"✅ а таблиця весь час майже ідеальна: збіг не падає нижче {min(збіги):.2f}")
print("\nОсь і парадокс. Агент знає правильний шлях — і майже ніколи ним не йде,")
print("бо кожен другий-третій крок робить навмання. Дослідження не безкоштовне:")
print("у світі з кактусами воно коштує епізодів.")
print("\nІ ще одне: у нашому стенді старт випадковий, тому таблиця вчиться добре")
print("навіть при ε = 0. У світі-лінії з лекції старт теж випадковий — а от якби")
print("він був фіксованим, жадібний агент застряг би на першій же винагороді.")
ε епізодів дійшли до мети вкололись збіг політики 0.0 300 0.94 0.06 1.00 0.0 1500 0.99 0.01 1.00 0.05 300 0.89 0.11 0.96 0.05 1500 0.94 0.06 0.96 0.15 300 0.78 0.22 0.96 0.15 1500 0.85 0.15 0.96
0.35 300 0.66 0.34 1.00
0.35 1500 0.71 0.29 1.00 0.6 300 0.43 0.57 0.96 0.6 1500 0.45 0.55 1.00 частка епізодів у кактусі по ε: [0.01, 0.06, 0.15, 0.29, 0.55] збіг політики з еталоном по ε: [1.0, 0.96, 0.96, 1.0, 1.0] ✅ частка уколів росте з ε монотонно: від 0.01 до 0.55 ✅ а таблиця весь час майже ідеальна: збіг не падає нижче 0.96 Ось і парадокс. Агент знає правильний шлях — і майже ніколи ним не йде, бо кожен другий-третій крок робить навмання. Дослідження не безкоштовне: у світі з кактусами воно коштує епізодів. І ще одне: у нашому стенді старт випадковий, тому таблиця вчиться добре навіть при ε = 0. У світі-лінії з лекції старт теж випадковий — а от якби він був фіксованим, жадібний агент застряг би на першій же винагороді.
💻 Завдання¶
🟢 Рівень 1 — разом¶
- У бандиті постав
оцінки = np.full(3, 10.0)замість нулів — це оптимістична ініціалізація. Запусти з ε = 0 і подивись, чи знайде агент найкраще дерево. Поясни, чому дослідження виникає само собою, без жодної випадковості. - Постав
ПЛАТА_ЗА_КРОК = 0у сітці й перебудуй еталонну політику. Що змінилось у стрілках і чому?
🟡 Рівень 2 — самостійно¶
- Побудуй криву «частка оптимальних дій за кроками» для трьох стратегій: ε-жадібної, чисто жадібної та оптимістичної. Усередни по 150 запусках, як це зроблено в лекції.
- Додай у сітку загасання ε: почни з 1.0 і плавно знижуй до 0.05 по ходу навчання. Порівняй із фіксованим ε за трьома числами: збігом політики, часткою уколів і середньою винагородою за останні 50 епізодів.
🔴 Рівень 3 — виклик¶
- Реалізуй SARSA (замість
max Q(s', a')бериQ(s', a')для тієї дії, яку агент справді зробить) і порівняй із Q-навчанням на цій же сітці. Хто ходить ближче до кактусів і чому? - Зроби сітку більшою (наприклад, 12 × 12) і виміряй, скільки епізодів потрібно для збігу політики > 0.9. Побудуй цю залежність від розміру сітки — і зрозумій, чому табличні методи не масштабуються.
🧪 Самоперевірка¶
1. При ε = 0 оцінки Q для двох із трьох дерев лишились нульовими. Чому?
відповідь
Бо жадібний агент обирає дію з найбільшим Q. Стартуючи з нулів, він бере перше дерево, отримує щось позитивне — і тепер його Q найбільший. Решта дерев більше ніколи не обираються, тож їхні оцінки нікому оновлювати.2. Чому в бандиті ми усереднювали по 200 запусках, а не подивились на один?
відповідь
Результат RL сильно залежить від зерна випадковості. Один запуск може випадково показати, що ε = 0 краще за ε = 0.1. Порівнювати алгоритми за одним запуском безглуздо — потрібні кілька запусків і, у серйозній роботі, довірчі інтервали.3. Ми збільшили ε з 0.05 до 0.6. Таблиця Q стала точнішою, а робот став частіше вколюватись. Це помилка в коді?