Q-Learning

Value Iteration - так называемый model based алгоритм, так как для него нам требуется полная модель среды.

Но, в реальности, нам почти никогда не известны вероятности переходов.

Существует и другой класс алгоритмов - model free, которым не нужна модель среды для обучения и работы. Самый известный из них - Q-Learning, который мы сейчас разберем.

Алгоритм

Траектории

Так как у нас нет модели среды, получать данные из нее мы можем только взаимодействуя с ней.

Взаимодействуя со средой, мы запоминаем состояния, в которых мы находились, действия, которые мы совершали и награды, которые мы получали. Это и есть наши данные

V vs Q

В Value Interation мы учили \(V\). Но для model free, \(V\) бесполезны, потому что на их основе нельзя совершать действия, не зная вероятности перехода в среде.

Имея же \(Q\), мы можем выбирать действия как \(\pi(s) = argmax_{a\in\mathcal{A}}q(s, a)\). Поэтому наш алгоритм должен выучивать \(q\).

Итерационное улучшение

Аналогично Policy iteration, мы можем пробовать улучшать \(q\) итерационно:

\[q(s_t, a_t) \leftarrow \mathbb{E}_{r_t, s_{t+1}} [r_t + \gamma \max_{a'} q(s_{t+1}, a')]\]

, но нам неизвестны вероятности перехода, а значит мы не можем честно посчитать матожидание. Но мы можем его оценить:

\[ \mathbb{E}_{r_t, s_{t+1}} [r_t + \gamma \max_{a'} q(s_{t+1}, a')] = \frac{1}{N} \sum\limits_i [r_i + \gamma \max_{a'} q(s_{i}^{next}, a')] \]

, где суммирование происходит по всем моментам из траекторий, где в состоянии \(s_t\) было совершено действие \(a_t\). Для таких моментов нам также надо помнить полученную награду \(r_i\) и следующее состояние \(s_{i}^{next}\).

На самом деле, нам даже не нужно считать среднее по всем таким моментам: мы можем производить обновление небольшими шагами:

\[q(s_t, a_t) \leftarrow \alpha (r_t + \gamma \max_{a'} q(s_{t+1}, a')) + (1 - \alpha) q(s_t, a_t)\]

, где \(\alpha\) - вес обновления, обычно близкий к 0 (т.к. не хотим слишком большого разброса при обновлении лишь по одному шагу на траектории).

Exploration

Мы пока не обсудили, как именно получать траектории. Очевидно два плохих подхода:

• Выбирать действия случайно: так мы получим большое разнообразие состояний и действий, но агенту будет тяжело оптимизировать уже неплохую стратегию, потому что он будет получать очень мало релевантных действий

• Выбирать оптимальные действия: агент не будет в достаточной мере исследовать различные стратегии, а быстро сойдемся к какой-то субоптимальной стратегии.

Наиболее простой работающий подход - комбинация этих двух:

• с вероятностью \(\epsilon\) (обычно небольшой) мы выбираем действие случайно

• с вероятностью \(1 - \epsilon\) мы выбираем оптимальное действие.

Такой выбор действий называется epsilon-greedy sampling

#@title Установка зависимостей и вспомогательные функции

import sys, os
if 'google.colab' in sys.modules and not os.path.exists('.setup_complete'):
    !wget -q https://raw.githubusercontent.com/yandexdataschool/Practical_RL/master/setup_colab.sh -O- | bash

    !touch .setup_complete

# This code creates a virtual display to draw game images on.
# It will have no effect if your machine has a monitor.
if type(os.environ.get("DISPLAY")) is not str or len(os.environ.get("DISPLAY")) == 0:
    !bash ../xvfb start
    os.environ['DISPLAY'] = ':1'

!pip3 install -q gymnasium[classic-control] --quiet



import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

bash: ../xvfb: No such file or directory

Имплементация

Допишите код класса QLearningAgent, реализуещего агента для обучения с помощью Q-Learning

from collections import defaultdict
import random
import math
import numpy as np


class QLearningAgent:
    def __init__(self, alpha, epsilon, discount, get_legal_actions):
        """
        Q-Learning Agent
        based on https://inst.eecs.berkeley.edu/~cs188/sp19/projects.html
        Instance variables you have access to
          - self.epsilon (exploration prob)
          - self.alpha (learning rate)
          - self.discount (discount rate aka gamma)

        Functions you should use
          - self.get_legal_actions(state) {state, hashable -> list of actions, each is hashable}
            which returns legal actions for a state
          - self.get_qvalue(state,action)
            which returns Q(state,action)
          - self.set_qvalue(state,action,value)
            which sets Q(state,action) := value
        !!!Important!!!
        Note: please avoid using self._qValues directly.
            There's a special self.get_qvalue/set_qvalue for that.
        """

        self.get_legal_actions = get_legal_actions
        self._qvalues = defaultdict(lambda: defaultdict(lambda: 0))
        self.alpha = alpha
        self.epsilon = epsilon
        self.discount = discount

    def get_qvalue(self, state, action):
        """ Returns Q(state,action) """
        return self._qvalues[state][action]

    def set_qvalue(self, state, action, value):
        """ Sets the Qvalue for [state,action] to the given value """
        self._qvalues[state][action] = value

    #---------------------START OF YOUR CODE---------------------#

    def get_value(self, state):
        """
        Compute your agent's estimate of V(s) using current q-values
        V(s) = max_over_action Q(state,action) over possible actions.
        Note: please take into account that q-values can be negative.
        """
        possible_actions = self.get_legal_actions(state)

        # If there are no legal actions, return 0.0
        if len(possible_actions) == 0:
            return 0.0

        q_s = [self.get_qvalue(state, action) for action in possible_actions]
        value = max(q_s)
        return value

    def update(self, state, action, reward, next_state):
        """
        You should do your Q-Value update here:
           Q(s,a) := (1 - alpha) * Q(s,a) + alpha * (r + gamma * V(s'))
        """

        # agent parameters
        gamma = self.discount
        learning_rate = self.alpha

        Q = (1-learning_rate)*self.get_qvalue( state, action) + learning_rate*(reward + gamma*self.get_value(next_state))

        self.set_qvalue(state, action, Q )

    def get_best_action(self, state):
        """
        Compute the best action to take in a state (using current q-values).
        """
        possible_actions = self.get_legal_actions(state)

        # If there are no legal actions, return None
        if len(possible_actions) == 0:
            return None

        best_action = None
        Q_opt = -1e20
        for action in possible_actions:
          Q_val = self.get_qvalue(state, action)
          if Q_val > Q_opt:
            Q_opt = Q_val
            best_action = action

        return best_action

    def get_action(self, state):
        """
        Compute the action to take in the current state, including exploration.
        With probability self.epsilon, we should take a random action.
            otherwise - the best policy action (self.get_best_action).

        Note: To pick randomly from a list, use random.choice(list).
              To pick True or False with a given probablity, generate uniform number in [0, 1]
              and compare it with your probability
        """

        # Pick Action
        possible_actions = self.get_legal_actions(state)
        action = None

        # If there are no legal actions, return None
        if len(possible_actions) == 0:
            return None

        # agent parameters:
        epsilon = self.epsilon

        if epsilon < np.random.rand():
            chosen_action = self.get_best_action(state)
        else:
            chosen_action = np.random.choice(possible_actions)

        return chosen_action

Обучение

Обучим агента в окружении Taxi-v3 из библиотеки gymnasium

import gymnasium as gym
env = gym.make("Taxi-v3", render_mode='rgb_array') # Создаем окружение

n_actions = env.action_space.n # Количество возможных действий

Вот так выглядит среда:

s, _ = env.reset()
plt.imshow(env.render())

<matplotlib.image.AxesImage at 0x7f7d6c81c130>

Агент управляет желтым такси. Его задача - подобрать человека с зеленой клетки и высадить в красной клетке. Он может совершать 6 действий: двигаться в 4 направлениях и подбирать/высаживать пассажира.

Создатим агента, код для которого мы написали выше:

agent = QLearningAgent(
    alpha=0.5, epsilon=0.25, discount=0.99,
    get_legal_actions=lambda s: range(n_actions))

Напишите функцию для обучения агента. Выбирайте действия \(\epsilon\)-жадно (вы реализовали агенту метод для этого)

def play_and_train(env, agent, t_max=10**4):
    """
    This function should
    - run a full game, actions given by agent's e-greedy policy
    - train agent using agent.update(...) whenever it is possible
    - return total reward
    """
    total_reward = 0.0
    s, _ = env.reset()

    for t in range(t_max):
        # get agent to pick action given state s.
        a = agent.get_action(s)

        next_s, r, done, _, _ = env.step(a)

        # train (update) agent for state s
        agent.update(s, a, r, next_s)

        s = next_s
        total_reward += r
        if done:
            break

    return total_reward

Запустим 1000 сессий для агента, посмотрим, какую среднуюю награду он получает

from IPython.display import clear_output

rewards = []
for i in range(1000):
    rewards.append(play_and_train(env, agent))
    agent.epsilon *= 0.99

    if i % 100 == 0:
        clear_output(True)
        plt.title('eps = {:e}, mean reward = {:.1f}'.format(agent.epsilon, np.mean(rewards[-10:])))
        plt.plot(rewards)
        plt.show()