Обучение с подкреплением: введение

Ричард С. Саттон, Эндрю Дж. Барто
Обучение с подкреплением
Введение

Reinforcement Learning
An Introduction
Second Edition
Richard S. Sutton and Andrew G. Barto

Обучение с подкреплением
Введение
Второе издание
Ричард С. Саттон, Эндрю Дж. Барто
        Москва, 2020

УДК 004.85
ББК 32.971.3
С21
Саттон Р. С., Барто Э. Дж.
С21	
Обучение с подкреплением: Введение. 2-е изд. / пер. с англ. А. А. Слинкина. – М.: ДМК Пресс, 2020. – 552 с.: ил. 
ISBN 978-5-97060-097-9
Идея обучения с подкреплением возникла десятки лет назад, но этой дисциплине 
предстояло пройти долгий путь, прежде чем она стала одним из самых активных направлений исследований в области машинного обучения и нейронных сетей. Сегодня 
это предмет интереса ученых, занимающихся психологией, теорией управления, 
искусственным интеллектом и многими другими отраслями знаний.
Подход, принятый авторами книги, ставит акцент на практическое использование 
обучения с подкреплением. В первой части читатель знакомится с базовыми его 
аспектами. Во второй части представлены приближенные методы решения в условиях ограниченных вычислительных ресурсов. В третьей части книги обсуждается 
важность обучения с подкреплением для психологии и нейронаук.
Издание предназначено для студентов технических вузов, разработчиков, специализирующихся на машинном обучении и искусственном интеллекте, а также 
представителей нетехнических профессий, которые могут использовать описанные 
методики в своей работе.
УДК  004.85
ББК  32.971.3
Original English language edition published by The MIT Press Cambridge, MA. Copyright © 2018 
Richard S. Sutton and Andrew G. Barto. Russian-language edition copyright © 2020 by DMK Press. 
All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой 
бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав.
ISBN 978-0-262-03924-6 (англ.)	
Copyright © 2018 Richard S. Sutton and Andrew G. Barto
ISBN 978-5-97060-097-9 (рус.)	
©  Оформление, издание, перевод, ДМК Пресс, 2020

Посвящается памяти А. Гарри Клопфа

Содержание
Вступительное слово..................................................................................................... 11
Предисловие ко второму изданию...................................................................... 12
Предисловие к первому изданию........................................................................ 17
Обозначения...................................................................................................................... 20
От издательства................................................................................................................ 25
Глава 1. Введение............................................................................................................ 26
1.1. Обучение с подкреплением................................................................................................ 26
1.2. Примеры.............................................................................................................................. 30
1.3. Элементы обучения с подкреплением.............................................................................. 31
1.4. Ограничения и круг вопросов............................................................................................ 33
1.5. Развернутый пример: игра в крестики-нолики................................................................ 34
1.6. Резюме................................................................................................................................. 39
1.7. История ранних этапов обучения с подкреплением........................................................ 39
Библиографические замечания................................................................................................ 49
Часть I. ТАБЛИЧНЫЕ МЕТОДЫ РЕШЕНИЯ................................................ 50
Глава 2. Многорукие бандиты................................................................................. 51
2.1. Задача о k-руком бандите................................................................................................... 51
2.2. Методы ценности действий............................................................................................... 53
2.3. 10-рукий испытательный стенд......................................................................................... 54
2.4. Инкрементная реализация................................................................................................. 57
2.5. Нестационарная задача...................................................................................................... 59
2.6. Оптимистические начальные значения............................................................................ 60
2.7. Выбор действия, дающего верхнюю доверительную границу......................................... 62
2.8. Градиентные алгоритмы бандита...................................................................................... 64
2.9. Ассоциативный поиск (контекстуальные бандиты)......................................................... 68
2.10. Резюме............................................................................................................................... 69
Библиографические и исторические замечания..................................................................... 71
Глава 3. Конечные марковские процессы принятия решений........... 74
3.1. Интерфейс между агентом и окружающей средой........................................................... 74
3.2. Цели и вознаграждения...................................................................................................... 80
3.3. Доход и эпизоды................................................................................................................. 82
3.4. Унифицированная нотация для эпизодических и непрерывных задач......................... 84
3.5. Стратегии и функции ценности......................................................................................... 86
3.6. Оптимальные стратегии и оптимальные функции ценности......................................... 91
3.7. Оптимальность и аппроксимация..................................................................................... 96
3.8. Резюме................................................................................................................................. 97
Библиографические и исторические замечания..................................................................... 99

Содержание    7
Глава 4. Динамическое программирование................................................. 102
4.1. Оценивание стратегии (предсказание)........................................................................... 103
4.2. Улучшение стратегии........................................................................................................ 107
4.3. Итерация по стратегиям................................................................................................... 109
4.4. Итерация по ценности...................................................................................................... 112
4.5. Асинхронное динамическое программирование........................................................... 115
4.6. Обобщенная итерация по стратегиям............................................................................. 116
4.7. Эффективность динамического программирования..................................................... 117
4.8. Резюме............................................................................................................................... 118
Библиографические и исторические замечания................................................................... 119
Глава 5. Методы Монте-Карло.............................................................................. 122
5.1. Предсказание методами Монте-Карло............................................................................ 123
5.2. Оценивание ценности действий методом Монте-Карло............................................... 127
5.3. Управление методом Монте-Карло................................................................................. 129
5.4. Управление методом Монте-Карло без исследовательских стартов............................. 132
5.5. Предсказание с разделенной стратегией посредством выборки по значимости........ 135
5.6. Инкрементная реализация............................................................................................... 142
5.7. Управление методом Монте-Карло с разделенной стратегией..................................... 143
5.8. *Выборка по значимости с учетом обесценивания........................................................ 146
5.9. *Приведенная выборка по значимости........................................................................... 147
5.10. Резюме............................................................................................................................. 149
Библиографические и исторические замечания................................................................... 150
Глава 6. Обучение на основе временных различий................................ 152
6.1. Предсказание TD-методами............................................................................................ 152
6.2. Преимущества TD-методов предсказания...................................................................... 157
6.3. Оптимальность TD(0)........................................................................................................ 159
6.4. Sarsa: TD-управление с единой стратегией.................................................................... 162
6.5. Q-обучение: TD-управление с разделенной стратегией................................................ 165
6.6. Expected Sarsa.................................................................................................................... 167
6.7. Смещение максимизации и двойное обучение.............................................................. 169
6.8. Игры, послесостояния и другие специальные случаи.................................................... 171
6.9. Резюме............................................................................................................................... 173
Библиографические и исторические замечания................................................................... 174
Глава 7. n-шаговый бутстрэппинг........................................................................ 176
7.1. n-шаговое TD-предсказание............................................................................................. 176
7.2. n-шаговый алгоритм Sarsa................................................................................................ 181
7.3. n-шаговое обучение с разделенной стратегией.............................................................. 184
7.4. *Приведенные методы с переменным управлением..................................................... 186
7.5. Обучение с разделенной стратегией без выборки по значимости :  
n-шаговый алгоритм обновления по дереву......................................................................... 188
7.6. *Унифицированный алгоритм: n-шаговый Q(σ)............................................................. 190
7.7. Резюме................................................................................................................................ 193
Библиографические и исторические замечания................................................................... 194
Глава 8. Планирование и обучение табличными методами.............. 195
8.1. Модели и планирование................................................................................................... 195
8.2. Dyna: объединение планирования, исполнения и обучения......................................... 198

8    Содержание
8.3. Когда модель неверна....................................................................................................... 203
8.4. Приоритетный проход...................................................................................................... 206
8.5. Сравнение выборочного и полного обновлений............................................................ 210
8.6. Траекторная выборка....................................................................................................... 213
8.7. Динамическое программирование в реальном времени............................................... 216
8.8. Планирование в момент принятия решений................................................................. 220
8.9. Эвристический поиск....................................................................................................... 221
8.10. Разыгрывающие алгоритмы.......................................................................................... 224
8.11. Поиск по дереву методом Монте-Карло........................................................................ 226
8.12. Резюме главы................................................................................................................... 229
8.13. Резюме части I: оси......................................................................................................... 230
Библиографические и исторические замечания................................................................... 233
Часть II. ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ............................... 236
Глава 9. Предсказание с единой стратегией  
и аппроксимацией........................................................................................................ 238
9.1. Аппроксимация функции ценности................................................................................ 239
9.2. Целевая функция предсказания (VE
—).............................................................................. 240
9.3. Стохастические градиентные и полуградиентные методы........................................... 242
9.4. Линейные методы............................................................................................................. 246
9.5. Конструирование признаков для линейных методов.................................................... 252
9.5.1. Полиномы.................................................................................................................. 252
9.5.2. Базис Фурье................................................................................................................ 254
9.5.3. Грубое кодирование.................................................................................................. 257
9.5.4. Плиточное кодирование........................................................................................... 260
9.5.5. Радиально-базисные функции................................................................................. 265
9.6. Выбор размера шага вручную.......................................................................................... 266
9.7. Нелинейная аппроксимация функций: искусственные нейронные сети..................... 267
9.8. Алгоритм TD наименьших квадратов............................................................................. 272
9.9. Аппроксимация функций с запоминанием.................................................................... 274
9.10. Аппроксимация с помощью ядерных функций............................................................ 276
9.11. Более глубокий взгляд на обучение с единой стратегией : заинтересованность  
и значимость............................................................................................................................ 278
9.12. Резюме............................................................................................................................. 280
Библиографические и исторические замечания................................................................... 281
Глава 10. Управление с единой стратегией и аппроксимацией....... 288
10.1. Эпизодическое полуградиентное управление.............................................................. 288
10.2. Полуградиентный n-шаговый Sarsa............................................................................... 292
10.3. Среднее вознаграждение: новая постановка непрерывных задач............................. 294
10.4. Возражения против постановки с обесцениванием..................................................... 299
10.5. Дифференциальный полуградиентный n-шаговый Sarsa........................................... 301
10.6. Резюме............................................................................................................................. 302
Библиографические и исторические замечания................................................................... 303
Глава 11. *Методы с разделенной стратегией  
и аппроксимацией ....................................................................................................... 304
11.1. Полуградиентные методы.............................................................................................. 305
11.2. Примеры расходимости в случае с разделенной стратегией....................................... 307
11.3. Смертельная триада........................................................................................................ 312

Содержание    9
11.4. Геометрия линейной аппроксимации функций ценности.......................................... 314
11.5. Градиентный спуск по беллмановской ошибке............................................................ 318
11.6. Беллмановская ошибка необучаема.............................................................................. 322
11.7. Градиентные TD-методы................................................................................................ 327
11.8. Эмфатические TD-методы............................................................................................. 330
11.9. Уменьшение дисперсии.................................................................................................. 332
11.10. Резюме........................................................................................................................... 334
Библиографические и исторические замечания................................................................... 335
Глава 12. Следы приемлемости............................................................................ 337
12.1. λ-доход............................................................................................................................. 338
12.2. TD(λ)................................................................................................................................. 342
12.3. n-шаговые усеченные λ-доходные методы................................................................... 346
12.4. Пересчет обновлений: онлайновый λ-доходный алгоритм......................................... 348
12.5. Истинно онлайновый TD(λ)............................................................................................ 350
12.6. *Голландские следы в обучении методами Монте-Карло............................................ 352
12.7. Sarsa(λ).............................................................................................................................. 354
12.8. Переменные λ и γ............................................................................................................ 359
12.9. Следы с разделенной стратегией и переменным управлением.................................. 361
12.10. От Q(λ) Уоткинса к Tree-Backup(λ)................................................................................ 364
12.11. Устойчивые методы с разделенной стратегией со следами приемлемости............. 367
12.12. Вопросы реализации..................................................................................................... 368
12.13. Выводы........................................................................................................................... 369
Библиографические и исторические замечания................................................................... 371
Глава 13. Методы градиента стратегии........................................................... 373
13.1. Аппроксимация стратегии и ее преимущества............................................................ 374
13.2. Теорема о градиенте стратегии..................................................................................... 376
13.3. REINFORCE: метод Монте-Карло на основе градиента стратегии.............................. 378
13.4. REINFORCE с базой.......................................................................................................... 381
13.5. Методы исполнитель–критик........................................................................................ 383
13.6. Метод градиента стратегии для непрерывных задач................................................... 385
13.7. Параметризация стратегии для непрерывных действий............................................. 388
13.8. Резюме............................................................................................................................. 389
Библиографические и исторические замечания................................................................... 390
Часть III. ЗАГЛЯНЕМ ПОГЛУБЖЕ..................................................................... 392
Глава 14. Психология.................................................................................................. 393
14.1. Предсказание и управление........................................................................................... 394
14.2. Классическое обусловливание....................................................................................... 395
14.2.1. Блокирующее обусловливание и обусловливание высшего порядка.................... 397
14.2.2. Модель Рескорлы–Вагнера...................................................................................... 399
14.2.3. TD-модель................................................................................................................ 401
14.2.4. Имитирование TD-модели...................................................................................... 403
14.3. Инструментальное обусловливание.............................................................................. 410
14.4. Отложенное подкрепление............................................................................................ 415
14.5. Когнитивные карты........................................................................................................ 416
14.6. Привычное и целеустремленное поведение................................................................. 418
14.7. Резюме.............................................................................................................................. 423
Библиографические и исторические замечания................................................................... 425

10    Содержание
Глава 15. Нейронауки................................................................................................. 432
15.1. Основы нейронаук.......................................................................................................... 433
15.2. Сигналы вознаграждения, сигналы подкрепления, ценности и ошибки   
предсказания........................................................................................................................... 435
15.3. Гипотеза об ошибке предсказания вознаграждения.................................................... 437
15.4. Дофамин.......................................................................................................................... 439
15.5. Экспериментальное подтверждение гипотезы об ошибке предсказания   
вознаграждения....................................................................................................................... 443
15.6. Параллель между TD-ошибкой и дофамином............................................................... 447
15.7. Нейронный исполнитель–критик.................................................................................. 452
15.8. Правила обучения критика и исполнителя................................................................... 456
15.9. Гедонистические нейроны............................................................................................. 460
15.10. Коллективное обучение с подкреплением.................................................................. 462
15.11. Основанные на модели методы в мозге...................................................................... 466
15.12. Наркотическая зависимость......................................................................................... 468
15.13. Резюме........................................................................................................................... 469
Библиографические и исторические замечания................................................................... 472
Глава 16. Примеры и приложения...................................................................... 481
16.1. TD-Gammon..................................................................................................................... 481
16.2. Программы игры в шашки Сэмюэла............................................................................. 486
16.3. Стратегия выбора ставки в программе Watson............................................................. 489
16.4. Оптимизация управления памятью.............................................................................. 492
16.5. Игра в видеоигры на уровне человека........................................................................... 497
16.6. Мастерство игры в го...................................................................................................... 503
16.6.1. AlphaGo..................................................................................................................... 506
16.6.2. AlphaGo Zero............................................................................................................. 509
16.7. Персонализированные веб-службы............................................................................... 513
16.8. Парение в восходящих потоках воздуха....................................................................... 516
Глава 17. Передовые рубежи................................................................................. 521
17.1. Общие функции ценности и вспомогательные задачи................................................ 521
17.2. Абстрагирование времени посредством опций............................................................ 523
17.3. Наблюдения и состояние................................................................................................ 526
17.4. Проектирование сигналов вознаграждения.................................................................. 532
17.5. Остающиеся вопросы...................................................................................................... 535
7.6. Экспериментальное подтверждение гипотезы об ошибке предсказания   
вознаграждения....................................................................................................................... 539
Библиографические и исторические замечания................................................................... 543
Предметный указатель.............................................................................................. 587