Предисловие редактора серии «Adaptive computation and machin learning» . . .5
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Часть I. Постановка задачи и подходы к ее решению. . . 11
Глава 1. Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1. Обучение с подкреплением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2. Примеры. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3. Элементы обучения с подкреплением. . . . . . . . . . . . . . . . . . . . . 18
1.4. Подробный пример: крестики-нолики . . . . . . . . . . . . . . . . . . . . 21
1.5. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6. История обучения с подкреплением . . . . . . . . . . . . . . . . . . . . . . 29
1.7. Библиографические и исторические справки . . . . . . . . . . . . . 40
Глава 2. Оценочная обратная связь. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.1. Задача об n-руком бандите. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2. Методы вычисления значений ценности действий . . . . . . . . 45
2.3. Выбор действия с помощью операции softmax . . . . . . . . . . . . 49
?2.4. Оценивание в сравнении с инструктированием . . . . . . . . . . . 50
2.5. Пошаговая реализация обучения . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.6. Нестационарные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.7. Оптимистичные начальные оценки . . . . . . . . . . . . . . . . . . . . . . . 60
?2.8. Сравнение с подкреплением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
?2.9. Методы преследования. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
?2.10. Ассоциативный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.11. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.12. Библиографические и исторические справки . . . . . . . . . . . . . 71
Глава 3. Задача обучения с подкреплением. . . . . . . . . . . . . . . . . . . . . . . . 74
3.1. Взаимосвязь агент — окружающая среда . . . . . . . . . . . . . . . . . 74
3.2. Цели и вознаграждения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.3. Выгода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.4. Единые обозначения для непрерывных заданий и заданий, состоящих из эпизодов . .85
?3.5. Марковское свойство . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.6. Марковские процессы принятия решений. . . . . . . . . . . . . . . . . 92
3.7. Функции ценности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.8. Оптимальные функции ценности . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.9. Оптимальность и аппроксимация . . . . . . . . . . . . . . . . . . . . . . . . 109
3.10. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.11. Библиографические и исторические справки . . . . . . . . . . . . . 112
Часть II. Фундаментальные методы решения . . . . . . . . . . . . 116
Глава 4. Динамическое программирование . . . . . . . . . . . . . . . . . . . . . . . . 117
4.1. Оценка стратегии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.2. Улучшение стратегии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.3. Итерация по стратегиям . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.4. Итерация по ценностям . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.5. Асинхронное динамическое программирование . . . . . . . . . . . 133
4.6. Обобщенная итерация по стратегиям. . . . . . . . . . . . . . . . . . . . . 135
4.7. Эффективность динамического программирования . . . . . . . 137
4.8. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.9. Библиографические и исторические справки . . . . . . . . . . . . . 140
Глава 5. МетодыМонт е-Карло . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.1. Оценка стратегии методами Монте-Карло . . . . . . . . . . . . . . . . 143
5.2. Оценка ценности действия методом Монте-Карло . . . . . . . . 149
5.3. Формирование управления методом Монте-Карло . . . . . . . . 150
5.4. Управление по методу Монте-Карло с интегрированной
оценкой ценности стратегий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.5. Оценивание одной стратегии при использовании другой . . 158
5.6. Управление по методу Монте-Карло с разделенной оцен-
кой ценности стратегий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.7. Пошаговая реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.8. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.9. Библиографические и исторические справки . . . . . . . . . . . . . 166
Глава 6. Обучение на основе временных различий. . . . . . . . . . . . . . . . . 168
6.1. Предсказание на основе временных различий . . . . . . . . . . . . 168
6.2. Преимущества TD-методов предсказания . . . . . . . . . . . . . . . . 174
6.3. Оптимальность метода TD(0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
6.4. SARSA: управление по TD-методу с интегрированной
оценкой ценности стратегий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
6.5. Q-обучение: управление по TD-методу с разделенной
оценкой ценности стратегий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
?6.6. Методы исполнитель—критик . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
?6.7. R-обучение для неприведенных продолжающихся задач . . 192
6.8. Игры, послесостояния и другие особые случаи . . . . . . . . . . . 195
6.9. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
6.10. Библиографические и исторические справки . . . . . . . . . . . . . 198
Часть III. Единый подход . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Глава 7. Следыприемлемост и. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
7.1. n-шаговое TD-прогнозирование . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.2. Прямой подход к методам TD(?) . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.3. Обратный подход к методам TD(?) . . . . . . . . . . . . . . . . . . . . . . 213
7.4. Эквивалентность прямого и обратного представлений . . . . 217
7.5. SARSA(?). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
7.6. Метод Q(?) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
?7.7. Следы приемлемости для методов типа исполнитель—
критик . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.8. Замещающие следы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
7.9. Проблемы реализации. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
?7.10. Переменный параметр ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
7.11. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
7.12. Библиографические и исторические справки . . . . . . . . . . . . . 234
Глава 8. Обобщение и аппроксимация функций . . . . . . . . . . . . . . . . . . . 237
8.1. Прогнозирование ценности при помощи аппроксимации
функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.2. Методы наискорейшего спуска . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
8.3. Линейные методы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.4. Управление с аппроксимацией функции . . . . . . . . . . . . . . . . . . 258
8.5. Самонастройка с разделенной оценкой ценности стратегий. . . . . . . 264
8.6. Нужна ли самонастройка? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
8.7. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
8.8. Библиографические и исторические справки . . . . . . . . . . . . . 273
Глава 9. Планирование и обучение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
9.1. Модели и планирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
9.2. Объединение планирования, исполнения и обучения. . . . . . 282
9.3. Когда модель неверна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
9.4. Приоритетная прогонка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
9.5. Сравнение полного и выборочного вариантов дублирования . . .296
9.6. Траекторная выборка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
9.7. Эвристический поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
9.8. Итоги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
9.9. Библиографические и исторические справки . . . . . . . . . . . . . 311
Глава 10. Важнейшие аспектыобучения с подкреплением . . . . . . . . . 313
10.1. Единый подход. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
10.2. Некоторые другие новые направления. . . . . . . . . . . . . . . . . . . . 317
Глава 11. Конкретные примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
11.1. Программа TD-Gammon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
11.2. Программа игры в шашки Сэмюеля. . . . . . . . . . . . . . . . . . . . . . 327
11.3. Акробот . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
11.4. Управление лифтом. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
11.5. Динамическое распределение каналов . . . . . . . . . . . . . . . . . . . . 342
11.6. Задача планирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
Список обозначений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380