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

Ричард С. Саттон, Эндрю Дж. Барто

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

Введение

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.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

 Содержание

Глава 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

Вступительное слово от ГК «Цифра» 

Прошло уже несколько лет с тех пор, как наша команда ступила на путь применения 
искусственного интеллекта для совершенствования процессов в промышленности 
и логистике. В самом начале мы и представить не могли, насколько тернистой, но в то 
же время невероятно интересной окажется эта дорога. За это время мы успели поработать с различными производствами и решить множество задач – от оптимизации 
производства битумных материалов до улучшения системы распределения нефтепродуктов и внедрения систем машинного зрения на карьерные экскаваторы. Методы 
машинного обучения, которые используются для решения подобных задач, постоянно 
совершенствуются, и мы внимательно следим за развитием подходов в области искусственного интеллекта, в том числе за исследованиями в обучении с подкреплением. 
Обучение с подкреплением – это один из разделов машинного обучения, исследующий вычислительный подход к обучению агента, который пытается максимизировать 
свою совокупную накопленную награду путем взаимодействия со сложной, зачастую 
стохастической средой. Последние несколько лет исследования этого подхода переживают настоящий ренессанс – ни одна научная конференция по искусственному интеллекту не обходится без секции на эту тему. Каждый год публикуются сотни научных 
статей, и все больше компаний в России и за рубежом начинают применять последние 
достижения этой области в своем бизнесе для улучшения различных внутренних процессов – от рекомендательных систем до оптимизации цепей поставок.
Мы видим огромный потенциал практического применения методов обучения 
с подкреплением для совершенствования процессов в промышленности и логистике, 
а также верим в решающее значение данных теоретических концепций и алгоритмов 
для прогресса искусственного интеллекта как области человеческого знания. Несмотря на огромный интерес к этой области в последнее время, по указанной теме издано 
не так много литературы. Именно поэтому мы решили поучаствовать в публикации 
этой замечательной книги на русском языке. 
Данная книга представляет собой исчерпывающее введение в такую интересную 
и быстро развивающуюся область искусственного интеллекта, как обучение с подкреп лением. Ее авторы, Ричард Саттон и Эндрю Барто, проделали невероятную работу, описав простым и понятным языком не только ключевые концепции и алгоритмы обучения с подкреплением, но и современные достижения этой области. В книге 
продемонстрирована связь дисциплины с психологией и нейронауками. Авторами 
по дробно рассматриваются детали работы системы AlphaGo, обыгравшей чемпиона 
мира в японскую настольную игру го, а также алгоритма, играющего в игры Atari на 
уровне человека, и многие другие приложения. 
Мы желаем читателю удачи на пути изучения такой сложной, но невероятно полезной и увлекательной дисциплины.

Сергей Свиридов,  
директор по исследованиям и разработкам, группа компаний «Цифра»

Группа компаний «Цифра» разрабатывает технологии цифровизации промышленности, инвестирует в продукты и развивает среду 
промышленного интернета вещей и искусственного интеллекта. 
Компания создала самую крупную в России лабораторию промышленного AI. Сегодня решения «Цифры» повышают эффективность промышленных предприятий в 22 странах мира. Ключевые 
отрасли для группы – это горная добыча и металлургия, машиностроение, нефтегазовый сектор и химическая промышленность. 
«Цифра входит» в Industrial Internet Consortium и ряд других российских и международных отраслевых ассоциаций.

Предисловие 
ко второму изданию

За двадцать лет, прошедших после выхода первого издания этой книги, мы стали свидетелями колоссального прогресса в области искусственного интеллекта, 
в немалой степени обусловленного достижениями машинного обучения, в т. ч. 
обучения с подкреплением. И этот прогресс был достигнут не только за счет впечатляющего роста вычислительных мощностей, но и благодаря развитию теории и алгоритмов. Поэтому необходимость во втором издании книги, вышедшей 
в 1998 году, давно назрела и перезрела, и наконец-то в 2012 году мы решили приняться за нее. Во втором издании мы ставили себе ту же цель, что и в первом: 
дать простое и понятное изложение основных идей и алгоритмов обучения с подкреплением, которое было бы доступно специалистам из смежных дисциплин. 
Книга по-прежнему осталась введением, основное внимание уделяется базовым 
алгоритмам онлайнового обучения. Мы включили ряд новых вопросов, возникших и приобретших важность за прошедшие годы, а также расширили описание 
тем, которые теперь понимаем лучше. Но мы даже не пытались дать исчерпывающее изложение всего предмета, который стремительно развивался во многих 
направлениях. Приносим извинения за то, что были вынуждены оставить все эти 
достижения (за исключением небольшого числа) без внимания.
Как и в первом издании, мы решили отказаться от строго формального изложения теории обучения с подкреплением и от постановки задачи в самом общем 
виде. Но по мере углубления нашего понимания некоторых вопросов потребовалось включить больше математики; части, для которых необходимо более уверенное владение математическим аппаратом, оформлены в виде врезок; читатели, 
не склонные к математике, могут их пропустить. Мы также используем не совсем 
такую же нотацию, как в первом издании. В процессе преподавания мы поняли, что новая нотация помогает устранить ряд распространенных недоразумений. Она подчеркивает различие между случайными величинами, которые обозначаются заглавными буквами, и их экземплярами, обозначаемыми строчными 
буквами. Например, состояние, действие и вознаграждение на временном шаге t 
обозначаются St, At и Rt, а их возможные значения – s, a и r. Кроме того, строчными буквами записываются функции ценности (например, vπ), а заглавными – их 
табличные представления (например, Qt(s, a)). Приближенные функции ценности являются детерминированными функциями случайных параметров, поэтому 
также записываются строчными буквами (например, vˆ(s, wt) » vπ(s)). Векторы, например вектор весов wt (ранее обозначался θt) и вектор признаков xt (ранее ϕt), 
записываются строчными полужирными буквами, даже если являются случайными величинами. Заглавные полужирные буквы оставлены для матриц. В первом 
издании мы употребляли специальные обозначения 𝒫a
ss¢ и ℛa
ss¢ для вероятности 
перехода и ожидаемого вознаграждения. Один из недостатков этой нотации заключается в том, что она не полностью характеризует динамику вознаграждения, 

Предисловие ко второму изданию  13

а дает только математические ожидания – этого достаточно для динамического 
программирования, но не для обучения с подкреплением. Другой недостаток – 
чрезмерное количество верхних и нижних индексов. В этом издании мы ввели 
явное обозначение p(s¢, r | s, a) для совместной вероятности следующего состояния 
и вознаграждения при условии текущего состояния и действия. Все изменения 
нотации сведены в таблице на стр. 20.
Второе издание значительно дополнено, и организация материала претерпела 
изменения. После первой вводной главы появились три новые части. В первой 
части (главы 2–8) обучение с подкреплением рассматривается настолько полно, 
насколько возможно без выхода за пределы табличного случая, для которого можно найти точные решения. Мы включили методы обучения и планирования для 
табличного случая, а также их унификацию в n-шаговых методах и в архитектуре Dyna. Многих алгоритмов, представленных в этой части, в первом издании не 
было, например: UCB, Expected Sarsa, двойное обучение, обновление по дереву, 
Q(σ), RTDP и MCTS. Подробное рассмотрение табличного случая в начале книги 
позволяет изложить основные идеи в простейшей постановке. Вторая часть книги 
(главы 9–13) посвящена обобщению этих идей на аппроксимации функций. В ней 
появились новые разделы об искусственных нейронных сетях, о базисе Фурье, 
LSTD, ядерных методах, методах Gradient-TD и Emphatic-TD, методах среднего 
вознаграждения, истинно онлайновом методе TD(λ) и методах градиента стратегии. Во втором издании намного подробнее рассмотрено обучение с разделенной 
стратегией, сначала в табличном случае (главы 5–7), а затем для аппроксимации 
функций в главах 11 и 12. Еще одно отличие второго издания заключается в отделении идеи прямого представления, связанной с n-шаговым бутстрэппингом 
(теперь она более полно рассмотрена в главе 7), от идеи обратного представления, связанной со следами приемлемости (она теперь независимо описана в главе 12). В третью часть книги включены новые большие главы о связях обучения 
с подкреп лением с психологией (глава 14) и нейронауками (глава 15), а также переработанная глава с примерами, включающая игры Atari, стратегию ставок в программе Watson, а также две программы игры в го: AlphaGo и AlphaGo Zero (глава 16). Но по необходимости мы смогли включить лишь малую часть сделанного 
в этой области. Выбор отражает наш давний интерес к недорогим безмодельным 
методам, которые хорошо масштабируются на крупные приложения. Последняя 
глава посвящена обсуждению будущего влияния обучения с подкреплением на 
общество. Хорошо это или плохо, но второе издание получилось почти в два раза 
больше первого.
Эта книга задумывалась как основной учебник для одно- или двухсеместрового 
курса по обучению с подкреплением. В односеместровый курс следует включить 
первые десять глав и излагать их по порядку. Это составит хорошую основу, к которой можно добавить материал из других глав, а также из других книг, например 
Bertsekas and Tsitsiklis (1996), Wiering and van Otterlo (2012), Szepesvári (2010), или 
из литературы – сообразуясь со вкусами лектора. В зависимости от подготовки 
студентов может оказаться полезным дополнительный материал по онлайновому 
обучению с учителем. Естественным дополнением будут идеи опций и моделей опций (Sutton, Precup and Singh, 1999). В двухсеместровый курс можно включить все 
главы и дополнительные материалы. Эту книгу можно также включить как часть 
более широких курсов машинного обучения, искусственного интеллекта или ней

 Предисловие ко второму изданию

ронных сетей. В таком случае имеет смысл рассматривать только некоторое подмножество глав. Мы рекомендуем главу 1 в качестве краткого обзора, главу 2 до 
раздела 2.4, главу 3, а затем избранные разделы остальных глав в зависимости от 
располагаемого времени и интересов лектора и аудитории. Глава 6 наиболее важна для предмета и всей книги. В курс, ориентированный на машинное обучение 
или нейронные сети, следует включить главы 9 и 10, а в курс, ориентированный на 
искусственный интеллект или планирование, – главу 8. Разделы и главы, которые 
мы считаем более трудными и не существенными для книги в целом, помечены 
звездочкой. Их можно опустить при первом чтении без ущерба для понимания 
последующего текста. Упражнения повышенной сложности также помечены звездочкой, они не существенны для усвоения основного материала главы.
Большинство глав заканчиваются разделом «Библиографические и исторические замечания», в которых мы перечисляем источники идей, изложенных 
в главе, приводим ссылки на литературу для дальнейшего чтения и на текущие 
исследовательские работы, а также даем историческую справку. Несмотря на все 
усилия сделать эти разделы полными и авторитетными, мы наверняка упустили 
какие-то важные работы предшественников. Приносим свои извинения и открыты для исправлений и дополнений, которые будут внесены в электронную 
версию книги.
Это издание, как и первое, посвящено памяти А. Гарри Клопфа. Именно Гарри познакомил нас друг с другом, и именно его идеи о мозге и искусственном 
интеллекте побудили нас отправиться в долгое путешествие по миру обучения с подкреплением. Гарри получил образование в области нейрофизиологии 
и очень интересовался машинным интеллектом, он работал старшим научным 
сотрудником в отделе авионики Управления научно-исследовательских работ 
ВВС США (AFOSR) при базе ВВС Райт-Паттерсон в штате Огайо. Он был недоволен 
тем, что процессам поиска равновесия, в т. ч. гомеостазу и методам классификации на основе исправления ошибок, придают чрезмерно большую важность при 
объяснении естественного интеллекта и закладывания фундамента машинного 
интеллекта. Он отмечал, что системы, пытающиеся что-то максимизировать (не 
важно, что именно), качественно отличаются от систем поиска равновесия, и доказывал, что именно в максимизирующих системах ключ к пониманию важных 
аспектов естественного интеллекта и построения искусственного. Гарри сыграл 
решающую роль в получении от AFOSR финансирования для проекта оценки научной ценности этих и родственных им идей. Этот проект был запущен в конце 
1970-х годов в Массачусетском университете в Амхерсте (UMass Amherst), сначала под руководством Майкла Эрбиба (Michael Arbib), Уильяма Килмера (William 
Kilmer) и Нико Спинелли (Nico Spinelli), профессоров факультета компьютерных 
и информационных наук и членов-основателей университетского кибернетического центра нейронаучных систем, созданного с перспективой работы на стыке 
нейронаук и искусственного интеллекта. Барто, недавно получивший докторскую степень в Мичиганском университете, был принят в проект на должность 
младшего научного сотрудника. Тем временем Саттон, студент старшего курса, 
изучавший информатику и психологию в Стэнфорде, переписывался с Гарри на 
тему их общего интереса к роли временных характеристик возбудителя в классической теории обусловливания. Гарри убедил группу в UMass в том, что Саттон 
станет отличным приобретением для проекта. Так Саттон оказался аспирантом 

Предисловие ко второму изданию  15

в UMass и начал писать докторскую диссертацию под руководством Барто, который к тому времени занял должность доцента. Исследования обучения с подкреплением, описанные в этой книге, – закономерный итог проекта, начатого Гарри 
и питавшегося его идеями. Таким образом, Гарри свел нас, авторов книги, положив начало долгой и плодотворной совместной работе. Посвящая эту книгу Гарри, 
мы отдаем должное его существенному вкладу не только в дисциплину обучения 
с подкреплением, но и в наше сотрудничество. Мы также выражаем благодарность 
профессорам Эрбибу, Килмеру и Спинелли за предоставленную нам возможность 
начать разработку этих идей. Наконец, мы благодарны AFOSR за щедрую поддержку, которую управление оказывало на ранней стадии наших исследований, 
и Национальному научному фонду (NSF) за щедрое финансирование в течение 
ряда последующих лет.
Есть много людей, которым мы благодарны за их идеи и помощь в подготовке 
второго издания. Все, кого мы благодарили за помощь в первом издании, заслуживают нашей глубочайшей благодарности и за это издание тоже – оно бы прос то 
не состоялось без их вклада в первое издание. К этому длинному перечню мы обязаны добавить многих, кто помогал готовить только второе издание. Студенты, 
которым мы много лет преподавали эту дисциплину, отметились самыми разными способами: находили ошибки, предлагали исправления и – не в последнюю 
очередь – испытывали затруднения, заставляя нас думать, как объяснить материал лучше. Мы выражаем особую благодарность Марте Стинструп (Martha Steenstrup), которая прочитала весь текст и поделилась подробными комментариями. 
Главы по психологии и нейронаукам не были бы написаны без помощи многочисленных специалистов в этих областях. Мы признательны Джону Муру (John 
Moore) за его многолетние терпеливые разъяснения теории и экспериментов по 
обучению животных и основ нейронауки, а также за внимательное прочтение нескольких черновых вариантов глав 14 и 15. Мы также благодарны Мэтту Ботвинику (Matt Botvinick), Натаниэлю Доу (Nathaniel Daw), Питеру Дайяну (Peter Dayan) 
и Йелю Ниву (Yael Niv) за проницательные замечания к черновикам этих глав, 
помощь в освоении огромного массива литературы и указание на наши многочисленные ошибки в ранних вариантах рукописи. Разумеется, все оставшиеся 
ошибки в этих главах (а их не может не быть) – целиком наша вина. Мы выражаем 
благодарность Филу Томасу (Phil Thomas), который помог сделать эти главы доступными неспециалистам в области психологии и нейронаук, и Питеру Стерлингу (Peter Sterling), помогавшему сделать объяснения более понятными. Спасибо 
также Джиму Хоуку (Jim Houk) за знакомство с вопросами обработки информации 
в подкорковых ядрах головного мозга и за привлечение нашего внимания к смежным разделам нейронауки. Хосе Мартинес (José Martinez), Терри Сейновски (Terry 
Sejnowski), Дэвид Силвер (David Silver), Джерри Тезауро (Gerry Tesauro), Георгиос Теочарус (Georgios Theocharous) и Фил Томас (Phil Thomas) любезно помогли 
нам разобраться в деталях их приложений обучения с подкреплением, чтобы мы 
могли включить их в главу с примерами. Они же поделились ценными комментариями к черновым вариантам соответствующих разделов. Отдельное спасибо 
Дэвиду Силверу, который помог нам лучше понять дерево поиска Монте-Карло 
и программу DeepMind для игры в го. Мы также благодарны Джорджу Конидарису (George Konidaris) за помощь при написании раздела о базисе Фурье. Эмилио 
Картони (Emilio Cartoni), Томас Седерборг (Thomas Cederborg), Стефан Дернбах 

 Предисловие ко второму изданию

(Stefan Dernbach), Клеменс Розенбаум (Clemens Rosenbaum), Патрик Тэйлор (Patrick Taylor), Томас Колин (Thomas Colin) и Пьер-Люк Бэкон (Pierre-Luc Bacon) помогали нам различными способами, за что мы им очень благодарны.
Саттон также выражает благодарность сотрудникам лаборатории обучения 
с подкреплением и искусственного интеллекта в университете Альберты за вклад 
во второе издание. Отдельное спасибо Рупаму Махмуду (Rupam Mahmood) за ценный вклад в обсуждение методов Монте-Карло обучения с разделенной стратегией в главе 5, Хамиду Мэю (Hamid Maei) за помощь в становлении взгляда на 
обуче ние с разделенной стратегией, представленного в главе 11, Эрику Грейвсу 
(Eric Graves) за постановку экспериментов в главе 13, Шан-тон Чжану (Shangtong 
Zhang) за воспроизведение и, как следствие, проверку почти всех экспериментальных результатов, Крису де Асису (Kris De Asis) за улучшение нового технического наполнения глав 7–12 и Харму ван Сейну (Harm van Seijen) за идеи, которые 
привели к отделению n-шаговых методов от следов приемлемости и (совместно 
с Хадо ван Хасселтом [Hado van Hasselt]) – за идеи, касающиеся точной эквивалентности прямого и обратного представления следов приемлемости (глава 12). 
Саттон также выражает признательность за финансовую поддержку и свободу 
исследований, которые обеспечивали правительство провинции Альберты и Национальный совет научных и инженерных исследований Канады на протяжении 
всей работы над вторым изданием книги. В частности, он благодарен Рэнди Гебелю (Randy Goebel) за создание благоприятной среды для исследований в Альберте с прицелом на перспективу. Также он благодарен компании DeepMind за 
поддержку на протяжении последних шести месяцев работы над книгой.
Наконец, мы признательны многочисленным придирчивым читателям черновых вариантов второго издания, которые мы выкладывали в интернет. Они нашли немало пропущенных нами ошибок и указали места, где может возникнуть 
недопонимание.