24 KiB

Raw Permalink Blame History Unescape Escape

Вступ до навчання з підкріпленням та Q-Learning

Скетчнот від Tomomi Imura

Навчання з підкріпленням включає три важливі концепції: агент, деякі стани та набір дій для кожного стану. Виконуючи дію в заданому стані, агент отримує винагороду. Уявіть комп'ютерну гру Super Mario. Ви — Маріо, знаходитеся на рівні гри, стоїте поруч із краєм обриву. Над вами монета. Ви, як Маріо, на рівні гри, у певній позиції — це ваш стан. Переміщення на один крок вправо (дія) призведе до падіння з обриву, і це дасть вам низький числовий бал. Однак натискання кнопки стрибка дозволить вам отримати очко і залишитися живим. Це позитивний результат, і він повинен нагородити вас позитивним числовим балом.

Використовуючи навчання з підкріпленням і симулятор (гру), ви можете навчитися грати в гру, щоб максимізувати винагороду, тобто залишатися живим і набирати якомога більше очок.

🎥 Натисніть на зображення вище, щоб почути Дмитра, який розповідає про навчання з підкріпленням

Квіз перед лекцією

Передумови та налаштування

У цьому уроці ми будемо експериментувати з кодом на Python. Ви повинні мати можливість виконувати код Jupyter Notebook з цього уроку, або на вашому комп'ютері, або десь у хмарі.

Ви можете відкрити ноутбук уроку і пройти через цей урок, щоб створити.

Примітка: Якщо ви відкриваєте цей код з хмари, вам також потрібно отримати файл rlboard.py, який використовується в коді ноутбука. Додайте його до тієї ж директорії, що й ноутбук.

Вступ

У цьому уроці ми дослідимо світ Петрика і вовка, натхненний музичною казкою російського композитора Сергія Прокоф'єва. Ми використаємо навчання з підкріпленням, щоб дозволити Петрику досліджувати своє середовище, збирати смачні яблука і уникати зустрічі з вовком.

Навчання з підкріпленням (RL) — це техніка навчання, яка дозволяє нам навчитися оптимальній поведінці агента в певному середовищі, проводячи багато експериментів. Агент у цьому середовищі повинен мати мету, визначену функцією винагороди.

Середовище

Для простоти уявімо світ Петрика як квадратну дошку розміром width x height, як на цьому зображенні:

Кожна клітинка на цій дошці може бути:

землею, по якій Петрик та інші створіння можуть ходити.
водою, по якій, очевидно, ходити не можна.
деревом або травою, місцем, де можна відпочити.
яблуком, яке Петрик буде радий знайти, щоб нагодувати себе.
вовком, який небезпечний і якого слід уникати.

Існує окремий модуль Python, rlboard.py, який містить код для роботи з цим середовищем. Оскільки цей код не важливий для розуміння наших концепцій, ми імпортуємо модуль і використовуємо його для створення зразкової дошки (блок коду 1):

from rlboard import *

width, height = 8,8
m = Board(width,height)
m.randomize(seed=13)
m.plot()

Цей код повинен надрукувати зображення середовища, схоже на наведене вище.

Дії та політика

У нашому прикладі мета Петрика — знайти яблуко, уникаючи вовка та інших перешкод. Для цього він може просто ходити, поки не знайде яблуко.

Таким чином, у будь-якій позиції він може вибрати одну з наступних дій: вгору, вниз, вліво і вправо.

Ми визначимо ці дії як словник і зіставимо їх із парами відповідних змін координат. Наприклад, рух вправо (R) буде відповідати парі (1,0). (блок коду 2):

actions = { "U" : (0,-1), "D" : (0,1), "L" : (-1,0), "R" : (1,0) }
action_idx = { a : i for i,a in enumerate(actions.keys()) }

Підсумовуючи, стратегія та мета цього сценарію такі:

Стратегія нашого агента (Петрика) визначається так званою політикою. Політика — це функція, яка повертає дію в будь-якому заданому стані. У нашому випадку стан проблеми представлений дошкою, включаючи поточну позицію гравця.
Мета навчання з підкріпленням — зрештою навчитися хорошій політиці, яка дозволить нам ефективно вирішувати проблему. Однак, як базовий варіант, розглянемо найпростішу політику, яку називають випадковою прогулянкою.

Випадкова прогулянка

Спочатку вирішимо нашу проблему, реалізувавши стратегію випадкової прогулянки. У випадковій прогулянці ми будемо випадково вибирати наступну дію з дозволених дій, поки не досягнемо яблука (блок коду 3).

Реалізуйте випадкову прогулянку за допомогою наведеного нижче коду:

def random_policy(m):
    return random.choice(list(actions))

def walk(m,policy,start_position=None):
    n = 0 # number of steps
    # set initial position
    if start_position:
        m.human = start_position 
    else:
        m.random_start()
    while True:
        if m.at() == Board.Cell.apple:
            return n # success!
        if m.at() in [Board.Cell.wolf, Board.Cell.water]:
            return -1 # eaten by wolf or drowned
        while True:
            a = actions[policy(m)]
            new_pos = m.move_pos(m.human,a)
            if m.is_valid(new_pos) and m.at(new_pos)!=Board.Cell.water:
                m.move(a) # do the actual move
                break
        n+=1

walk(m,random_policy)

Виклик walk повинен повернути довжину відповідного шляху, яка може змінюватися від одного запуску до іншого.

Запустіть експеримент прогулянки кілька разів (скажімо, 100) і надрукуйте отриману статистику (блок коду 4):
```
def print_statistics(policy):
    s,w,n = 0,0,0
    for _ in range(100):
        z = walk(m,policy)
        if z<0:
            w+=1
        else:
            s += z
            n += 1
    print(f"Average path length = {s/n}, eaten by wolf: {w} times")

print_statistics(random_policy)
```
Зверніть увагу, що середня довжина шляху становить близько 30-40 кроків, що досить багато, враховуючи той факт, що середня відстань до найближчого яблука становить близько 5-6 кроків.

Ви також можете побачити, як виглядає рух Петрика під час випадкової прогулянки:

Функція винагороди

Щоб зробити нашу політику більш розумною, нам потрібно зрозуміти, які кроки є "кращими" за інші. Для цього нам потрібно визначити нашу мету.

Мета може бути визначена у вигляді функції винагороди, яка повертає певне значення оцінки для кожного стану. Чим більше число, тим краща функція винагороди. (блок коду 5)

move_reward = -0.1
goal_reward = 10
end_reward = -10

def reward(m,pos=None):
    pos = pos or m.human
    if not m.is_valid(pos):
        return end_reward
    x = m.at(pos)
    if x==Board.Cell.water or x == Board.Cell.wolf:
        return end_reward
    if x==Board.Cell.apple:
        return goal_reward
    return move_reward

Цікаво, що у більшості випадків ми отримуємо значну винагороду лише наприкінці гри. Це означає, що наш алгоритм повинен якось запам’ятовувати "хороші" кроки, які призводять до позитивної винагороди в кінці, і збільшувати їх важливість. Аналогічно, всі кроки, які призводять до поганих результатів, слід знеохочувати.

Q-Learning

Алгоритм, який ми тут обговоримо, називається Q-Learning. У цьому алгоритмі політика визначається функцією (або структурою даних), яка називається Q-таблиця. Вона записує "корисність" кожної дії в даному стані.

Вона називається Q-таблицею, тому що її часто зручно представляти у вигляді таблиці або багатовимірного масиву. Оскільки наша дошка має розміри width x height, ми можемо представити Q-таблицю за допомогою масиву numpy з формою width x height x len(actions): (блок коду 6)

Q = np.ones((width,height,len(actions)),dtype=np.float)*1.0/len(actions)

Зверніть увагу, що ми ініціалізуємо всі значення Q-таблиці однаковим значенням, у нашому випадку — 0.25. Це відповідає політиці "випадкової прогулянки", оскільки всі кроки в кожному стані однаково хороші. Ми можемо передати Q-таблицю до функції plot, щоб візуалізувати таблицю на дошці: m.plot(Q).

У центрі кожної клітинки є "стрілка", яка вказує на бажаний напрямок руху. Оскільки всі напрямки рівні, відображається точка.

Тепер нам потрібно запустити симуляцію, дослідити наше середовище та навчитися кращому розподілу значень Q-таблиці, що дозволить нам набагато швидше знайти шлях до яблука.

Суть Q-Learning: рівняння Беллмана

Як тільки ми починаємо рухатися, кожна дія матиме відповідну винагороду, тобто теоретично ми можемо вибрати наступну дію на основі найвищої миттєвої винагороди. Однак у більшості станів цей крок не досягне нашої мети — досягти яблука, і тому ми не можемо одразу вирішити, який напрямок кращий.

Пам’ятайте, що важливий не миттєвий результат, а кінцевий результат, який ми отримаємо наприкінці симуляції.

Щоб врахувати цю відкладену винагороду, нам потрібно використовувати принципи динамічного програмування, які дозволяють мислити про нашу проблему рекурсивно.

Припустимо, що зараз ми знаходимося в стані s, і хочемо перейти до наступного стану s'. Роблячи це, ми отримаємо миттєву винагороду r(s,a), визначену функцією винагороди, плюс певну майбутню винагороду. Якщо припустити, що наша Q-таблиця правильно відображає "привабливість" кожної дії, то в стані s' ми виберемо дію a, яка відповідає максимальному значенню Q(s',a'). Таким чином, найкраща можлива майбутня винагорода, яку ми могли б отримати в стані s, буде визначена як max Q(s',a') (максимум тут обчислюється для всіх можливих дій a' у стані s').

Це дає формулу Беллмана для обчислення значення Q-таблиці в стані s, враховуючи дію a:

Перевірка політики

Оскільки Q-Table містить "привабливість" кожної дії в кожному стані, її досить легко використовувати для визначення ефективної навігації у нашому світі. У найпростішому випадку ми можемо вибрати дію, що відповідає найвищому значенню в Q-Table: (блок коду 9)

def qpolicy_strict(m):
        x,y = m.human
        v = probs(Q[x,y])
        a = list(actions)[np.argmax(v)]
        return a

walk(m,qpolicy_strict)

Якщо ви спробуєте код вище кілька разів, то можете помітити, що іноді він "зависає", і вам потрібно натиснути кнопку STOP у ноутбуці, щоб перервати виконання. Це відбувається через те, що можуть виникати ситуації, коли два стани "вказують" один на одного з точки зору оптимального Q-Value, у результаті чого агент безкінечно переміщується між цими станами.

🚀Виклик

Завдання 1: Змініть функцію walk, щоб обмежити максимальну довжину шляху певною кількістю кроків (наприклад, 100), і подивіться, як код вище час від часу повертає це значення.

Завдання 2: Змініть функцію walk так, щоб вона не поверталася до місць, де вже була раніше. Це запобігатиме зацикленню walk, однак агент все одно може опинитися "заблокованим" у місці, з якого не може вибратися.

Навігація

Кращою політикою навігації буде та, яку ми використовували під час навчання, що поєднує експлуатацію та дослідження. У цій політиці ми будемо вибирати кожну дію з певною ймовірністю, пропорційною значенням у Q-Table. Ця стратегія все ще може призводити до того, що агент повертається до вже досліджених позицій, але, як видно з коду нижче, вона забезпечує дуже короткий середній шлях до бажаного місця (пам'ятайте, що print_statistics запускає симуляцію 100 разів): (блок коду 10)

def qpolicy(m):
        x,y = m.human
        v = probs(Q[x,y])
        a = random.choices(list(actions),weights=v)[0]
        return a

print_statistics(qpolicy)

Після запуску цього коду ви повинні отримати значно меншу середню довжину шляху, ніж раніше, у діапазоні 3-6.

Дослідження процесу навчання

Як ми вже згадували, процес навчання — це баланс між дослідженням і використанням отриманих знань про структуру простору задачі. Ми побачили, що результати навчання (здатність допомогти агенту знайти короткий шлях до мети) покращилися, але також цікаво спостерігати, як середня довжина шляху змінюється під час процесу навчання:

Висновки з навчання можна підсумувати так:

Середня довжина шляху збільшується. На початку середня довжина шляху зростає. Це, ймовірно, пов'язано з тим, що коли ми нічого не знаємо про середовище, ми, швидше за все, потрапляємо в погані стани, наприклад, у воду або до вовка. Коли ми дізнаємося більше і починаємо використовувати ці знання, ми можемо довше досліджувати середовище, але все ще не дуже добре знаємо, де знаходяться яблука.
Довжина шляху зменшується, коли ми дізнаємося більше. Як тільки ми дізнаємося достатньо, агенту стає легше досягати мети, і довжина шляху починає зменшуватися. Однак ми все ще відкриті до досліджень, тому часто відхиляємося від найкращого шляху і досліджуємо нові варіанти, що робить шлях довшим за оптимальний.
Довжина різко збільшується. На графіку також видно, що в певний момент довжина різко збільшується. Це вказує на стохастичну природу процесу і на те, що ми можемо в якийсь момент "зіпсувати" коефіцієнти Q-Table, перезаписавши їх новими значеннями. Це ідеально слід мінімізувати, зменшуючи швидкість навчання (наприклад, ближче до кінця навчання ми лише трохи коригуємо значення Q-Table).

Загалом, важливо пам'ятати, що успіх і якість процесу навчання значною мірою залежать від параметрів, таких як швидкість навчання, зменшення швидкості навчання та коефіцієнт дисконтування. Їх часто називають гіперпараметрами, щоб відрізнити їх від параметрів, які ми оптимізуємо під час навчання (наприклад, коефіцієнти Q-Table). Процес пошуку найкращих значень гіперпараметрів називається оптимізацією гіперпараметрів, і це заслуговує окремої теми.

Тест після лекції

Завдання

Більш реалістичний світ

Відмова від відповідальності:
Цей документ було перекладено за допомогою сервісу автоматичного перекладу Co-op Translator. Хоча ми прагнемо до точності, зверніть увагу, що автоматичні переклади можуть містити помилки або неточності. Оригінальний документ мовою оригіналу слід вважати авторитетним джерелом. Для критично важливої інформації рекомендується професійний переклад людиною. Ми не несемо відповідальності за будь-які непорозуміння або неправильні тлумачення, що виникли внаслідок використання цього перекладу.

24 KiB Raw Permalink Blame History Unescape Escape