# 🚕 Шпаргалка для телефона: Лабораторная работа №6 (RL & Q-learning в Taxi-v3)

> **Для кого этот конспект:** для быстрого повторения в метро / автобусе по дороге на пару.
> **Цель:** сдать лабу на максимум, понимая каждую формулу, строчку кода и реальные цифры графиков.

---

## 📱 1. Главные концепции «на пальцах»

### Что такое Reinforcement Learning (Обучение с подкреплением)?
Это обучение методом проб и ошибок. В отличие от классического ML (где есть размеченные $X$ и $y$), здесь есть **Агент** (наше такси) и **Среда** (городская карта $5 \times 5$). Агент совершает действия, среда меняется и выдаёт награду (+ или -). Задача агента — максимизировать **суммарную дисконтированную награду**.

### Что такое Марковский процесс (MDP)?
«Будущее зависит только от настоящего и не зависит от прошлого». Чтобы такси решило, куда ехать, ему не нужно помнить, где оно было 5 минут назад, — достаточно знать текущее состояние $s_t$.

### Откуда берётся цифра 500 состояний в Taxi?
Карта $5 \times 5 = 25$ клеток:
$$\text{Размерность} = (\text{Строка}: 5) \times (\text{Колонка}: 5) \times (\text{Пассажир}: 5) \times (\text{Цель}: 4) = 500$$
- У пассажира **5 состояний**: 4 фиксированные точки (Red, Green, Yellow, Blue) + 5-е состояние: **«внутри такси»**.
- У финиша **4 состояния**: те же 4 точки R, G, Y, B.

### Пространство действий (6 штук):
- `0: Вниз`, `1: Вверх`, `2: Вправо`, `3: Влево`
- `4: Pickup` (посадить пассажира)
- `5: Dropoff` (высадить пассажира)

### Награды среды:
- **-1** за каждый шаг (чтобы такси не кружило, а ехало кратчайшим путём).
- **+20** за успешную доставку в нужную точку.
- **-10** за незаконную посадку/высадку (например, высадить посреди дороги).

---

## 🧠 2. Уравнение Беллмана и Q-таблица

### Что такое Q-таблица?
Это «шпаргалка» такси размера $500 \times 6$ (3000 чисел). 
Строка — состояние, колонка — действие. Число $Q(s, a)$ показывает: *«насколько выгодно в состоянии $s$ выбрать действие $a$»*.

### Формула обновления Q-learning:
$$Q(s, a) \leftarrow Q(s, a) + \alpha \cdot \Big[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \Big]$$

- $\alpha$ (**Learning Rate**, скорость обучения): насколько сильно мы доверяем новому опыту.
  - $\alpha = 0.5$ — идеальный баланс.
  - $\alpha = 0.1$ — агент учится слишком медленно (не успевает за 1500 эпизодов).
- $\gamma$ (**Discount Factor**, дисконт): насколько важна долгосрочная выгода.
  - $\gamma = 0.9 \dots 0.99$ — агент смотрит далеко вперёд (видит цель +20).
  - $\gamma = 0.6$ — агент «близорук», видит только штраф -1 и боится ехать далеко.
- **TD-error** (ошибка временной разности): скобка $[r + \gamma \max Q(s') - Q(s)]$. Разница между новой оценкой и старым значением.

### Почему Q-learning — это Off-policy?
Потому что в формуле стоит $\max_{a'} Q(s', a')$. Агент оценивает будущее, исходя из **идеального (жадного)** действия, хотя сам в этот момент может совершать случайное исследовательское действие ($\varepsilon$-greedy).

---

## 📊 3. Разбор реальных цифр и графиков наших экспериментов

### 1) Случайный агент (Этап 1):
- Длина эпизода: **200 шагов** (сработал лимит `truncated=True`).
- Суммарная награда: **$-704$**.
- Почему так плохо: случайно нажимал `Pickup`/`Dropoff` посреди улицы (получая каждый раз по $-10$) и врезался в стены.

### 2) Q-таблица До и После обучения (Этап 2):
- **ДО обучения:** 0 ненулевых ячеек из 3000 ($0\%$). Все нули.
- **ПОСЛЕ обучения:** ровно **2400 ненулевых ячеек ($80.0\%$)**, $\min = -15.93$, $\max = +20.0$, $\text{mean} = -3.36$.
- **Вопрос на засыпку:** *Почему заполнилось ровно 2400 (80%), а не все 3000?*
  - **Ответ:** В среде ровно 100 состояний соответствуют случаям, когда пассажир уже в пункте назначения (эпизод сразу завершается) или они недостижимы. Остаётся ровно **400 активных состояний**, у каждого по 6 действий: $400 \times 6 = 2400$!

### 3) Обученный агент на тесте ($\varepsilon = 0$):
- Длина оптимального маршрута: **15 шагов**.
- Награда: **$+6$** ($+20$ за доставку минус 14 шагов по $-1$).
- Ошибочных действий: **0**.

### 4) Сравнение 3 стратегий исследования (Этап 3, 2000 эпизодов):
| Стратегия | Время (с) | Шагов в обучении | Награда на тесте | Шагов на тесте | Успех (%) |
| :--- | :---: | :---: | :---: | :---: | :---: |
| **Фиксированный $\varepsilon = 0.1$** | **1.00 с** | 51 365 | +7.63 | 13.37 | 100% |
| **Затухающий $\varepsilon$ ($1.0 \to 0.01$)** | **1.46 с** | 71 236 | +7.61 | 13.39 | 100% |
| **Softmax (Больцман $\tau: 5 \to 0.1$)** | **4.43 с** | 84 044 | +7.43 | 13.57 | 100% |

- **Вывод:** Все 3 стратегии дают 100% успех. Но **Softmax работает в 3–4 раза медленнее** из-за постоянного вычисления экспонент `np.exp()` и нормализации вероятностей. **Затухающий $\varepsilon$ — лучший промышленный выбор**.

### 5) Влияние $\alpha$ и $\gamma$ (Тепловые карты):
- При $\alpha = 0.1$: провал (награда $-140 \dots -72$, успех всего $28\% \dots 61\%$). Агент недообучен.
- При $\gamma = 0.6$: близорукость (успех $83\%$ при $\alpha=0.5$).
- Оптимум: $\alpha = 0.5$, $\gamma = 0.9 \dots 0.99$ $\to$ **100% успех, награда +7.63, 13.37 шага**.

### 6) Масштабирование по числу эпизодов:
- **500 эпизодов:** успех **70%**, награда $-53.9$ (недообучение).
- **2000 эпизодов:** успех **100%**, награда $+7.61$, время **1.61 с**.
- **5000 эпизодов:** успех **100%**, награда $+7.61$, время **2.47 с**.
- **10000 эпизодов:** успех **100%**, награда $+7.59$, время **4.14 с**.
- **Вывод:** 2000–2500 эпизодов — точка насыщения. Обучать 10 000 эпизодов бессмысленно, качество не растёт, а время тратится.

---

## 🎓 4. 15 типовых вопросов преподавателя на защите с ответами

#### 1. В чём разница между Reinforcement Learning и Supervised Learning?
> В Supervised Learning есть «учитель», который даёт правильный ответ на каждый объект выборки. В RL учителя нет: агент получает лишь числовую награду (часто с задержкой) и сам должен понять, какие именно действия привели к успеху (проблема распределения кредита / Credit Assignment Problem).

#### 2. Что означают флаги terminated и truncated в gymnasium?
> `terminated = True` — агент достиг естественного конца задачи (пассажир успешно высажен).  
> `truncated = True` — принудительный сброс по таймауту среды (в Taxi — 200 шагов), цель не достигнута.

#### 3. Почему пространство состояний равно 500?
> $5 \text{ строк} \times 5 \text{ колонок} \times 5 \text{ положений пассажира} \times 4 \text{ пункта назначения} = 500$. У пассажира 5 положений, потому что он может быть в 4 точках на карте или внутри такси.

#### 4. Что такое компромисс Exploration vs Exploitation?
> **Exploration (исследование)** — выбор случайных или неоптимальных действий для сбора новой информации о среде.  
> **Exploitation (эксплуатация)** — выбор действия с максимальным текущим $Q(s, a)$ для получения максимальной награды прямо сейчас. Без исследования агент застрянет в локальном оптимуме; без эксплуатации он не сможет стабильно решать задачу.

#### 5. Почему в формуле обновления Q-learning стоит $\max_{a'} Q(s', a')$?
> Это оператор оптимальности Беллмана. Агент оценивает потенциал следующего состояния $s'$ по максимально возможной награде из него, что делает алгоритм Off-policy.

#### 6. Чем Q-learning отличается от SARSA?
> SARSA — это **On-policy** алгоритм. В формуле SARSA вместо $\max$ берётся $Q(s', a')$, где $a'$ — действие, реально выбранное текущей исследовательской политикой. SARSA более «осторожна» (например, держится подальше от обрывов), а Q-learning учит строго оптимальную траекторию.

#### 7. Зачем нужен дисконт $\gamma$ (гамма)? Что будет, если $\gamma = 0$ или $\gamma = 1$?
> $\gamma$ определяет горизонт планирования.  
> Если $\gamma = 0$, агент учитывает только немедленную награду $r_{t+1}$ («живёт одним днём») и никогда не доедет до пассажира.  
> Если $\gamma = 1$, все будущие награды равноценны текущим, а в бесконечных задачах ряды наград могут расходиться до бесконечности.

#### 8. Что показывает скорость обучения $\alpha$ (альфа)?
> $\alpha$ — это вес обновления в формуле Temporal Difference: $Q_{new} = (1 - \alpha) Q_{old} + \alpha \cdot TD_{target}$. При $\alpha = 1$ старое знание мгновенно заменяется новым. При $\alpha = 0$ обучение не происходит.

#### 9. Почему у нас в Q-таблице заполнилось 2400 ячеек, а не 3000?
> Из 500 математически возможных состояний 100 состояний являются терминальными (пассажир уже на месте) либо недостижимыми. Агент реально посещает 400 состояний, у каждого по 6 действий: $400 \times 6 = 2400$ значений.

#### 10. Как работает стратегия Softmax (Больцман) и чем она отличается от $\varepsilon$-greedy?
> В $\varepsilon$-greedy все неоптимальные действия равновероятны. В Softmax вероятность действия пропорциональна его ценности: $P(a) = \frac{e^{Q(s, a)/\tau}}{\sum e^{Q(s, b)/\tau}}$. Второе по качеству действие выбирается чаще, чем заведомо худшее. Параметр $\tau$ (температура) регулирует случайность.

#### 11. Почему Softmax обучался в 3–4 раза дольше $\varepsilon$-greedy?
> Для каждого шага агента требуется вычислять экспоненты вектора из 6 чисел, сумму и семплировать индекс по распределению вероятностей через `np.random.choice(p=...)`, тогда как в $\varepsilon$-greedy выполняется просто `random.random() < eps` и поиск индекса максимума `np.argmax()`.

#### 12. Какая награда считается идеальной для эпизода Taxi?
> В среднем от $+7$ до $+9$. За успешную высадку даётся $+20$. Минимальное расстояние от старта до пассажира и от пассажира до цели в среднем составляет 11–13 шагов (по $-1$ за шаг). $20 - 13 = +7$.

#### 13. Что произошло при обучении на 500 эпизодах?
> Агент не успел посетить все 400 активных состояний. В $30\%$ тестовых случаев такси попадало в незнакомые состояния и упиралось в лимит 200 шагов (успех составил только $70\%$, а средняя награда $-53.9$).

#### 14. Можно ли применить табличный Q-learning для управления беспилотным автомобилем Tesla?
> Нет. Табличный метод применим только для маленьких дискретных пространств состояний (как в Taxi: 500 штук). В реальном автомобиле состояния непрерывны (видеокамеры, лидары, скорость, координаты). Таблица потребовала бы бесконечной памяти. Для таких задач используют **Deep Q-Networks (DQN)** или непрерывные алгоритмы (PPO, SAC), где Q-функцию аппроксимирует нейросеть.

#### 15. Как мы замеряли время обучения и почему именно так?
> Через `time.perf_counter()`. Это монотонный таймер высокого разрешения в Python, который не подвержен скачкам системных часов и идеально подходит для бенчмаркинга кода.

---
*Шпаргалка подготовлена в рамках выполнения Лабораторной работы №6. Удачи на защите!* 🚀
