Аналогии для обучения с подкреплением:

Мне очень нравится то, как Скотт Янг учится. Он говорит, что ключ к быстрому обучению - это налаживание связей и аналогий. С тех пор он вернулся к этому заявлению, но я все же нашел этот подход очень полезным. Важно активно вспоминать информацию, но также важно проводить аналогии, чтобы лучше понимать темы. В этом посте я подробно расскажу о аналогиях, которые я провел для обучения с подкреплением, чтобы помочь вам, ребята, лучше понять эту тему.

Чтобы научиться обучению с подкреплением, я просмотрел видеолекции профессора Баларама Равиндрана [1]. Этот курс является теоретическим из-за его опыта, но я также считаю, что это хорошее введение. Он очень точно следует классической книге Ричарда Саттона и Эндрю Барто, и здесь присутствуют онлайн-задания и решения. Поэтому рекомендую этот курс для самостоятельного изучения. Теперь перейдя к основной теме этой статьи, я перейду к аналогии для каждой концепции обучения с подкреплением и надеюсь расширить их, чтобы вы, ребята, могли использовать эти аналогии для понимания тем, которые кажутся вам сложными.

Основы :: Я обнаружил, что большинство концепций подкрепления полезно при размышлении об использовании отношений. Это можете быть вы и ваша подруга, вы и ваша собака, вы и ваш отец и так далее. Я обычно использую подругу и собаку, так как считаю такие аналогии наиболее интересными и интуитивно понятными, и в результате их намного легче вспомнить. Начнем с вас и вашей собаки. Обучение с подкреплением обычно моделируется как агент, среда, состояние, установка вознаграждения. В этом случае мы будем рассматривать только агента, среду и вознаграждение, предполагая, что существует только одно состояние. В отношениях между вами и вашей собакой вы являетесь агентом, собака - окружающей средой, а реакция собаки - наградой. У вас есть набор «действий», которые могут быть: погладить собаку, кормить ее, мыть и так далее. Ваш набор действий вызывает у собаки определенную награду. Это может быть ваша собака, которая виляет хвостом, ваша собака лает, ваша собака лижет вас и так далее. Есть некоторые положительные награды, которые представляют собой действия, которые ваша собака выполняет, которые вам нравятся, и некоторые отрицательные награды, такие как лай на незнакомцев. Подобную логику можно распространить и на подругу. Я считаю, что аналогия с девушкой полезна при работе со сложными алгоритмами, в то время как собака полезна для более простых алгоритмов. Ваша цель как агента - максимизировать положительное вознаграждение. В целом обучение с подкреплением состоит в том, чтобы узнать, какие действия вы должны выполнять, чтобы получить максимальную положительную награду. Следует отметить, что, когда я начинал, я использовал аналогии, относящиеся к шахматным партиям. Одна из ключевых проблем, которые я обнаружил, заключается в том, что здесь «окружение» или ваш оппонент могут изменить состояние доски. Вот почему аналогия с шахматами вызывает больше путаницы, чем ясности. Я буду использовать его в определенных случаях, когда я считаю, что эта аналогия более уместна, но в большинстве случаев размышления о ваших отношениях с девушкой или собакой гораздо более полезны для понимания.

Многорукие бандиты. Самый простой способ подумать об этой проблеме - это попытаться выяснить, какой кофе больше всего нравится вашей девушке, или какой бренд корма для собак больше всего нравится вашей собаке. Итак, изначально у вас есть 7 различных марок кормов для собак. Вы хотите знать, какой из них нравится вашей собаке больше всего. В течение первой недели вы каждый день давайте собаке еду разных марок и изучаете ее реакцию. Наивно вы можете сказать, что собака больше всего виляла хвостом в среду, поэтому очевидно, что клеймо, которое я поставил в среду, является лучшим. Но что, если в среду ваша собака поймала кошку и была этому счастлива. Таким образом, он вилял хвостом как из-за еды, так и из других соображений. В следующий раз, когда вы дадите ему пищу в среду, он будет гораздо меньше вилять хвостом. В тот день, когда вы дали ему любимую еду, было грустно только потому, что у него был плохой день, и вы виляли хвостом гораздо меньше, чем в обычный день. Ключевым моментом здесь является признание того, что окружающей среде присуща неопределенность. Окружающая среда или собака не идеальны. Он будет по-разному реагировать на одно и то же действие. Так что вы можете найти для этого простое решение. Назовите каждую марку продуктов питания определенное количество раз, а затем найдите, что она средняя, ​​а марка с наивысшим средним показателем явно является лучшей. Что ж, поздравляю, вы эффективно решили проблему многоруких бандитов, по общему признанию, это не эффективное решение. Также мы не уверены, сколько раз попробовать каждую марку. Позже мы займемся этими вопросами, а пока я надеюсь, что вы четко понимаете вопрос: понимание того, какое из ваших действий лучше всего, когда реакция окружающей среды является стохастической или неопределенной, - это многорукие бандиты. Стандартная учебная интуиция для этого - пойти в казино и иметь n игровых автоматов. Вам нужно выяснить, какой игровой автомат дает в среднем самую высокую выплату.

Теперь, прежде чем мы перейдем к алгоритмам, чтобы решить эту проблему, давайте обсудим, как сравнить эти алгоритмы. Один из способов - проверить, найдет ли алгоритм в конечном итоге лучший бренд корма для собак. Это асимптотическая правильность, ее касается только то, найдет ли ваш алгоритм ответ. Следующая мера - оптимальность сожаления. Это важно для измерения того, сколько страданий вы доставили своей собаке. В идеале вам нужен свой алгоритм, чтобы не выбирать марку, которую ваша собака презирает на раннем этапе, и проводить тестирование только между 2–3 брендами, которые ваша собака любит больше всего. Наивный алгоритм присвоения собаке каждой марки определенное количество раз этого не делает, она заставляет вашу собаку пробовать худшую марку n раз, даже если ваша собака реагирует на этот бренд изрыгать ее еду. Таким образом, оптимальный алгоритм сожаления довольно быстро сузит список хороших вариантов, в свою очередь, выбор между этими вариантами может занять много времени. (Обоснование этого математическое, и его нелегко получить из аналогий.) По сути, он пытается определить скорость сходимости. Наконец, у нас есть приблизительно правильные алгоритмы (оптимальные алгоритмы PAC). Это позволяет определить, насколько вы близки к лучшему бренду корма для собаки в течение 100 дней. Его не интересует точный ответ, его устраивает примерно близкий ответ (вторая любимая марка вашей собаки), но он хочет получить этот ответ намного быстрее, чем предыдущие алгоритмы.

Итак, как мы видим, с течением времени член log (t) увеличивается, увеличивая ценность бренда. По мере того, как вы выбираете этот бренд все больше и больше, член Nj увеличивается, а поскольку он стоит в знаменателе, он снижает ценность бренда. Предыдущий термин - это просто средняя награда от этого бренда. Итак, ваш алгоритм говорит, что чем чаще вы выбираете бренд, тем больше у вас уверенности в среднем, чем меньше он меняется со временем, чем меньше вы выбираете бренд, тем больше вы не уверены в его ценности. Надеюсь, теперь этот алгоритм имеет интуитивное понимание того, почему он работает. 2 в корне - это просто математическое значение для сожаления, этот алгоритм или идея всегда сходятся и работают, даже если квадратного корня не было. Максимальное сожаление по этому алгоритму:

Сожаление - это формально разница в общем вознаграждении между вашим алгоритмом и тем, что вы всегда выбирали правильное действие с самого начала, когда ваш алгоритм не знал оптимального бренда. Доказательство вышеупомянутой теоремы является в высшей степени математическим, но оно опирается на основные аргументы, которые используются во всех алгоритмах RL. Аргумент в том, что мой алгоритм выберет неоптимальное действие только в том случае, если:

В этом доказательстве мы, по сути, доказываем, что 3. невозможно, поэтому мы выберем неоптимальное действие только в том случае, если произойдет 1.) из 2.), а затем, используя оценки вероятности Чернова, мы найдем для него математическое значение. Джереми Кун очень хорошо объяснил математическую часть [«2»]

  1. Я сильно недооценил свои оптимальные действия
  2. Я не сильно переоценивал или недооценивал какое-либо действие, но все же какое-то другое действие оценивается лучше, чем мое текущее действие
  3. Круто, теперь у нас есть мера для сравнения алгоритмов. Первый алгоритм, который я буду обсуждать, - это алгоритм верхней доверительной границы. Я честно прохожу курс RL, о котором упоминал выше, я не создаю здесь свой собственный материал. UCB обычно описывается как оптимизм перед лицом неопределенности. Это означает, что вы всегда будете делать самые оптимистичные предположения. Первоначально после первой недели вы обнаруживаете, что бренд, который вы указали в среду, получил лучший отклик, поэтому теперь вы будете продолжать пробовать один и тот же бренд снова и снова, пока не станет казаться, что этот бренд уже не так хорош, как был. Затем вы перейдете ко второму варианту и так далее. Я надеюсь, что вам интуитивно понятно, что, поскольку вы выбираете только лучший вариант в определенное время, этот алгоритм является оптимальным для сожаления. Если вы это понимаете, то аналогии работают, иначе потратьте больше времени на размышления в этом смысле, пока это не станет для вас очевидным. Конечно, мы это докажем и ниже. Теперь, чтобы этот алгоритм заработал, вам нужно хорошо измерить каждое из ваших действий. Вы можете подумать, что удерживать в качестве меры среднее вознаграждение, полученное за каждое действие, достаточно, но средние показатели сильно различаются. Допустим, в среду у вашей собаки был исключительно удачный день, поэтому измеренная награда зашкаливает. В связи с этим бренд среды выглядит так хорошо, и потребуется много времени, чтобы его среднее значение приблизилось к фактическому среднему. Этот алгоритм больше не беспокоится о переоценке определенных действий, а о недооценке действительно хороших действий. На самом деле и это намного хуже. Допустим, в четверг вы дали своей собаке любимую марку, но тот день был действительно плохим. Из-за этого награда за это действие в тот день была действительно низкой. Теперь ваш оптимистичный алгоритм может закончиться тем, что больше никогда не выберет это действие, поскольку оно уже находится очень низко в списке и, возможно, никогда не приблизится к оптимальному решению. Таким образом, UCB решает эту проблему, масштабируя действия с каждым временным шагом. Обычно ценность четверга увеличивается за каждый день, который вы проводите, не выбирая бренд четверг. Так что в конечном итоге вы выберете этот бренд. Теперь, когда вы в следующий раз выберете его, если он снова даст вам плохой результат, то, вероятно, этот бренд сам по себе плох. Вы по-прежнему будете масштабировать его на каждый день, когда не выбираете его, но теперь, после этого, вы будете масштабировать его гораздо медленнее. Это для того, чтобы прошло больше времени, прежде чем вы снова выберете эту марку. Таким образом, вы пытаетесь количественно оценить наблюдаемые значения и насколько вы не уверены в этих значениях одним способом. Математически это:

Хорошо, пока что мы обсудили алгоритм UCB и основные аналогии для обучения с подкреплением. Позже я рассмотрю другие подходы к Multi Armed Bandits, прежде чем углубляться в RL.

Основные аналогии для обучения с подкреплением и многоруких бандитов

.