BMSTU/03-mas-lab-01-report.tex

\documentclass[a4paper]{article}

\input{../common-preamble}
\input{../bmstu-preamble}
\input{../fancy-listings-preamble}

\numerationTop

\begin{document}
\fontsize{14pt}{14pt}\selectfont % Вполне очевидно, что мы хотим 14й шрифт, все его хотят
\thispagestyle{empty}
\makeBMSTUHeader

\makeReportTitle{Лабораторной работе}{1}{Табулярное Q-обучение игрового агента в Toytext}{Мультиагентные интеллектуальные системы}{}{В.Э. Большаков}
\newpage
\thispagestyle{empty}
\tableofcontents
\newpage
\pagestyle{fancy}
\sloppy
\section{Цель}
Целью работы является разработка мультиагентной интеллектуальной системы на языке программирования Python для игры FrozenLake-v1 с размером карты 8x8. В ходе работы требуется исследовать влияние параметров learning rate, discount factor lambda, total episodes на исход игры. Обосновать выбор лучших параметров. Провести сравнительный эксперимент по определению количества побед и скорости обучения с помощью агента обученного табулярным Q-learning и случайно действующим агентом (random).

\subsection{Описание игры}

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

\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{03-mas-lab-01-frozenLakeScreenshot.png}
    \caption{Скриншот игры FrozenLake}
    \label{fig:frozenLake}
\end{figure}

\subsection{Легенда}

Наступила зима. Вы и ваши друзья бросали фрисби в парке, и вдруг вы сделали сумасшедший бросок, который отправил фрисби на середину озера. Вода в основном замерзла, но есть несколько мест, где лед растаял. Если вы наступите на одну из этих дыр, вы попадете в замерзшую воду. В настоящее время ощущается нехватка фрисби, поэтому абсолютно необходимо, чтобы вы прошли по льду озера и забрали диск. Однако лед скользкий, поэтому вы не всегда будете двигаться в том направлении, в каком собираетесь.

Поверхность описывается с использованием сетки, как показано ниже:

Для карты размером "4x4":
\begin{verbatim}
    [
    "SFFF",
    "FHFH",
    "FFFH",
    "HFFG"
    ]
\end{verbatim}

Для карты размером "8x8":
\begin{verbatim}
    [
    "SFFFFFFF",
    "FFFFFFFF",
    "FFFHFFFF",
    "FFFFFHFF",
    "FFFHFFFF",
    "FHHFFFHF",
    "FHFFHFHF",
    "FFFHFFFG",
    ]
\end{verbatim}

Где соответствующие символы на карте обозначают следующее:
\begin{itemize}
    \item S:	начальное положение, безопасная клетка
    \item F:	замерзшее озеро, безопасная клетка
    \item H:	прорубь, проигрыш при попадании сюда
    \item G:	цель, где находится фрисби
\end{itemize}

Эпизод игры завершается, когда вы попадаете в прорубь (проигрыш, награда = 0), либо когда вы добираетесь до фрисби (выигрыш, награда = 1).

\subsection{Понятие среды (Environment)}
Чтобы понять основы импорта пакетов Gym, загрузки среды и других важных функций, связанных с OpenAI Gym, вот пример среды Frozen Lake.

Загрузка среды Frozen Lake:
\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Блок программы на языке Python}]
import gym
env = gym.make('FrozenLake-v1', desc=None, map_name="4x4", is_slippery=True)
\end{lstlisting}

Далее разберемся, как сбрасывать состояние среды. Пока агент в обучении с подкреплением учится, он многократно повторяет действия и эпизоды обучения. Из-за этого необходимо, чтобы в начале каждого эпизода среда была в начальном состоянии. Сбросить состояние среды можно следующим образом:
\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Блок программы на языке Python}]
import gym
env	= gym.make('FrozenLake-v1', desc=None, map_name="4x4", is_slippery=True)
s = env.reset() print(s)
\end{lstlisting}

\begin{verbatim}
0 #initial state is 0
\end{verbatim}

После совершения какого-либо действия может возникнуть необходимость показать статус агента в среде. Визуализация среды:
\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Блок программы на языке Python}]
env.render()
\end{lstlisting}

\begin{verbatim}
SFFF
FHFH
FFFH
HFFG
\end{verbatim}

\subsection{Описание среды}

Так как мир игры представляет собой сетку 4х4, существует 16 возможных состояний.

Узнать количество состояний можно так:
\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Блок программы на языке Python}]
print(env.observation_space)
\end{lstlisting}

\begin{verbatim}
Discrete(16)
\end{verbatim}

Для клетки с дырой во льду предусмотрен штраф – 10 очков. Для клетки с целью – награда в 100 очков. Для того, чтобы маршруты не были излишне длинными, за каждый переход на соседнюю ледяную клетку существует штраф 1 очко.

\subsection{Описание агента}
У агента есть 4 действия: пойти влево, вниз, направо, вверх. Задача агента дойти до цели, не упав в ледяную воду. Для агента будет лучше, если он сможет дойти до цели наиболее коротким маршрутом.

Посмотреть действия агента:
\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Блок программы на языке Python}]
print(env.action_space)
\end{lstlisting}

\begin{verbatim}
Discrete(4)
\end{verbatim}

\subsection{Q-обучение игрового агента для FrozenLake-v1}
Q-таблица для агента (для карты размером 4x4) будет иметь 16 строк (по числу возможных состояний в игре) и 4 столбца (по числу доступных агенту действий):

\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Блок программы на языке Python}]
print("Number of actions : ", env.action_space.n)
print("Number of states : ", env.observation_space.n)
\end{lstlisting}

\begin{verbatim}
Number of actions : 4
Number of states : 16
\end{verbatim}

\subsection{Алгоритм Q-обучения}
Обновление таблицы Q будет происходить по следующей формуле:
\[ Q_{new}(s_t, a_t) = Q(s_t, a_t) + \alpha\cdot(r_t + \gamma\cdot max_aQ(s_{t + 1}, a) - Q(s_t, a_t)) \]
    
Для обучения будет использована $\varepsilon$-жадная стратегия. Это значит, что агент выбирает свои действия таким образом, что с определенной вероятностью он выберет лучшее действие в данном состоянии среды, в другом же случае ходит случайным образом. Это позволяет найти компромисс между стратегиями исследования среды и использования накопленных знаний.

Например, $\varepsilon$-жадная стратегия может быть реализована так:
\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Блок программы на языке Python}]
def epsilon_greedy(state, epsilon):
    if np.random.uniform(0, 1) < epsilon:
        action = env.action_space.sample()
    else:
        action = np.argmax(Q[state, :])
    return action
\end{lstlisting}

Параметр $\varepsilon$ будет уменьшаться для того, чтобы постепенно агент начал делать более обоснованный выбор, вместо случайных действий. Со временем агент достаточно исследует среду, после чего лучше делать самые выгодные действия всё чаще, а случайные всё реже. Пора начать использовать полученную ранее информацию о среде.

\section{Экспериментальная часть}
Выполнение разработанной программы делится на два этапа: этап обучения и этап игры.
В процессе этапа обучения можно включить вывод информации о ходах, принимаемых агентом. Агент может сделать ход в одном из 4 различных направлений, подобные действия в выводе программы выглядят следующим образом:

\begin{figure}[H]
  \centering
  \begin{subfigure}[b]{0.30\textwidth}
  \includegraphics[width=\textwidth]{03-mas-lab-01-initialState.png}
  \caption{Начальное}
  \label{pic:state-init}
  \end{subfigure}
 \hfill
  \begin{subfigure}[b]{0.32\textwidth}
  \includegraphics[width=\textwidth]{03-mas-lab-01-rightMove.png}
  \caption{После действий агента}
  \label{pic:state-after}
  \end{subfigure}
  \caption{Состояния среды}
  \label{pic:states}
\end{figure}

На приведённых рисунках агент осуществляет случайный переход (в данном случае агент осуществляет движение вправо) с целью исследовать окружающую его среду, таким образом агент осуществляет переход из состояния, приведённого на рисунке \hrf{pic:state-init} в состояние \hrf{pic:state-after}.

Агент осуществляет ход вправо и попадает на безопасную клетку, за счёт этого действия происходит обновление матрицы состояний Q, учитывающее штраф в -1 единицу.

По ходу действий агента, он может попасть на клетку проруби и проиграть, тогда обновление матрицы состояний Q учтёт штраф в размере 10 штрафных единиц. Если агнет в результате своих действий попадает на клетку с фрисби, то алгоритм оценивает его действия в 100 поощряющих единиц и обновляет матрицу состояний с учётом данного факта, что приводит к закреплению соответствующих значений в матрице состояний.

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

Матрица состояний будет иметь следующий вид:

\begin{figure}[H]
 \begin{small}
 \begin{verbatim}
 [[3.72503070e-01 3.72021394e-01 3.73252576e-01 3.72769500e-01]
  [3.78044111e-01 3.78190119e-01 3.78897886e-01 3.79553241e-01]
  [3.92140099e-01 3.92508656e-01 3.92181150e-01 3.91273172e-01]
  [4.10530706e-01 4.10892760e-01 4.09736098e-01 4.19185894e-01]
  ...
  [5.56639598e-02 1.66467536e-01 2.62878380e-01 1.56094241e-01]
  [2.80415038e-02 2.08575331e-01 5.97742895e-01 4.83463168e-02]
  [0.00000000e+00 0.00000000e+00 0.00000000e+00 0.00000000e+00]]
 \end{verbatim}
 \end{small}
\end{figure}

Каждый элемент отображает вероятность от 0 до 1, определяющее направление победы (направление в сторону максимума вероятности победы).

\subsection{Исследование влияния параметров на исход игры}
Анализ графика \ref{fig:learn_win_rate} показал, что большие значения фактора скорости обучения снижают эффективность обучения, это можно объяснить сильным косвенным влиянием обновления на значения матрицы состояний, не относящийся к текущей ячейке в которой в данный момент располагается агент.
\begin{figure}[H]
    \begin{center}
        \input{pics/03-mas-lab-01-win_rate-learning_rate.pgf}
    \end{center}
    \caption{Зависимость относительного числа побед от фактора обучения}
    \label{fig:learn_win_rate}
\end{figure}

Анализ графика \ref{fig:gamma_win_rate} позволяет сказать о том, что коэффициент штрафа сильно влияет на относительное значение побед, так как данный фактор определяет насколько сильно агент стремится к сиюминутной награде (локально-оптимальное решение, жадный алгоритм), по сравнению с большой наградой, которую он мог бы получить в результате победы.
\begin{figure}[H]
    \begin{center}
        \input{pics/03-mas-lab-01-win_rate-gamma.pgf}
    \end{center}
    \caption{Зависимость относительного числа побед от коэффициента штрафа}
    \label{fig:gamma_win_rate}
\end{figure}

По графику \ref{fig:episodes_win_rate} можно сказать, что количество эпизодов обучения в целом не влияет, однако, существует некоторый провал графика в районе 10000 эпизодов обучения, это связано с корректировкой весов матрицы состояния после её выхода на стабильное состояние, другими словами уже скорректированная матрица состояния проходит этап докорректировки, что влечёт за собой повторное изменение значений матрицы, которые уже занимали близкие к требуемым значения. При дальнейшем увеличении эпизодов обучения корректировки не так сильно влияют на матрицу состояния, а элементы матрицы принимают свои требуемые значения.
\begin{figure}[H]
    \begin{center}
        \input{pics/03-mas-lab-01-win_rate-episodes.pgf}
    \end{center}
    \caption{Зависимость относительного числа побед от количества итераций обучения}
    \label{fig:episodes_win_rate}
\end{figure}

\subsection{Сравнение Q-learning и Random агентов}
Следующим этапом было проведение сравнение агентов, обученных табулярным Q-learning и случайно действующим (random) алгоритмами. В результате сравнения, приведённого в таблицах \hrf{tab:tab_10000} - \hrf{tab:tab_20000}, можно сказать что агент, обученный табулярным алгоритмом показывает большее количество побед, хотя время обучения такого агента выше. Случайно действующий агент не учитывает информацию об окружающей его среде, а основывается исключительно на заученной информации, на тех вероятностях, доставляющих его к цели. В свою очередь агент, обученный табулярным способом учитывает особенности окружающей его среды (например - проскальзывание, которое также имеет вероятностную природу), таким образом при принятии решения агент будет основываться также на предполагаемой вероятности ошибиться, то есть оказаться после выбранного действия в требуемой клетке, даже при наибольшей вероятности благоприятного исхода.

\begin{table}[H]
\centering
    \caption{Сравнение табулярного и случайного алгоритмов для 10 000 эпизодов обучения}
    \label{tab:tab_10000}
    \begin{tabular}{|c|c|c|}
    \hline
    Эпизоды обучения = 10 000 & Количество побед {[}-{]} & Скорость обучения {[}сек.{]} \\ \hline
    Q-learning                & 910                      & 16.352                       \\ \hline
    Random                    & 413                      & 11.629                       \\ \hline
    \end{tabular}
\end{table}

\begin{table}[H]
\centering
    \caption{Сравнение табулярного и случайного алгоритмов для 20 000 эпизодов обучения}
    \label{tab:tab_20000}
    \begin{tabular}{|c|c|c|}
    \hline
    Эпизоды обучения = 20 000 & Количество побед {[}-{]} & Скорость обучения {[}сек.{]} \\ \hline
    Q-learning                & 943                      & 34.477                       \\ \hline
    Random                    & 368                      & 20.272                       \\ \hline
    \end{tabular}
\end{table}

\section{Выводы}
По результатам лабораторной работы можно сделать следующие выводы:
\begin{itemize}
    \item Увеличение фактора скорости обучения негативно сказывается на относительном проценте побед.
    \item Увеличение коэффициента штрафа оказывается положительную динамику на относительное число побед.
    \item Число обучающих эпох не оказывается существенного влияния на относительную величину побед.
    \item Агент, обученный табулярным алгоритмом показал большую приспособленность к изменчивым факторам окружающей среды.
    \item Агент, обученный случайным алгоритмом обучился быстрее, но процент побед оказался меньше.
\end{itemize}

\newpage
\appendix
\section*{Приложения}
\addcontentsline{toc}{section}{Приложения}
\renewcommand{\thesubsection}{\Alph{subsection}}

\subsection{Полный листинг программы}
\label{appendix:fulls}
\begin{lstlisting}[language=Python,style=PyCodeStyle,caption={Полный код программы на языке Python}]
    import gym
    import numpy as np
    import matplotlib.pyplot as plt
    import matplotlib
    import time

    def calculation(episodes, learn_rate, gamma):
    environment = gym.make('FrozenLake-v1', map_name="8x8",
                           is_slippery=True)
    environment.reset()
    qtable = np.zeros((environment.observation_space.n, environment.action_space.n))
    epsilon_decay = 1 / episodes
    epsilon = 1.0
    max_step = 1000000
    epsilon_final = 0.0001
    start_time = time.time()
    for _ in range(episodes):
        state = environment.reset()[0]
        done = False
        step = 0
        # Until the agent gets stuck in a hole or reaches the goal, keep training it
        while not done and step < max_step:
            # Generate a random number between 0 and 1
            rnd = np.random.random()

            # If random number < epsilon, take a random action
            if rnd < epsilon:
                action = environment.action_space.sample()
            # Else, take the action with the highest value in the current state
            else:
                action = np.argmax(qtable[state])

            # Implement this action and move the agent in the desired direction
            new_state, reward, done, info, res = environment.step(action)

            # Update Q(s,a)
            qtable[state, action] = qtable[state, action] + \
                                    learn_rate * (reward + gamma * np.max(qtable[new_state]) - qtable[state, action])

            # Update our current state
            state = new_state
            step += 1
        # Update epsilon
        epsilon = max(epsilon - epsilon_decay, epsilon_final)
    print("--- %s seconds ---" % (time.time() - start_time))
    episodes_win = 100
    nb_success = 0
    print(qtable)
    # Evaluation
    for _ in range(episodes_win):
        state = environment.reset()[0]
        done = False

        # Until the agent gets stuck or reaches the goal, keep training it
        while not done and step < max_step:
            # Choose the action with the highest value in the current state
            action = np.argmax(qtable[state])

            # Implement this action and move the agent in the desired direction
            new_state, reward, done, info, res = environment.step(action)

            # Update our current state
            state = new_state

            # When we get a reward, it means we solved the game
            nb_success += reward
            step += 1
    # Let's check our success rate!
    print(f"Success rate = {nb_success / episodes_win * 100}%")
    print("win = ", nb_success)
    print("lose = ", episodes_win - nb_success)
    return nb_success / episodes_win * 100

    learning_rate = [0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5]
    win_rate_learning_rate = []

    total_episodes = [5000, 10000, 20000, 30000, 40000, 50000, 60000]
    win_rate_total_episodes = []

    gamma_total = [0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 0.99]
    win_rate_gamma_total = []

    for gamma in gamma_total:
    result = calculation(10000, 0.1, gamma)
    while result < 0.1:
        result = calculation(10000, 0.1, gamma)
    win_rate_gamma_total.append(result)

    print(gamma_total[win_rate_gamma_total.index(max(win_rate_gamma_total))])
    max_gamma = gamma_total[win_rate_gamma_total.index(max(win_rate_gamma_total))]

    for rate in learning_rate:
    result = calculation(10000, rate, max_gamma)
    while result < 0.1: 
        result = calculation(10000, rate, max_gamma)
    win_rate_learning_rate.append(result)

    print(learning_rate[win_rate_learning_rate.index(max(win_rate_learning_rate))])
    max_learning_rate = learning_rate[win_rate_learning_rate.index(max(win_rate_learning_rate))]

    for episodes in total_episodes:
    result = calculation(episodes, max_learning_rate, max_gamma)
    while result < 0.1:
        result = calculation(episodes, max_learning_rate, max_gamma)
    win_rate_total_episodes.append(result)

    matplotlib.use("pgf")
    matplotlib.rcParams.update({
    "pgf.texsystem": "pdflatex",
    'font.family': 'serif',
    'text.usetex': True,
    'pgf.rcfonts': False,
    })

    plt.title('win_rate (learning_rate)')
    plt.xlabel('learning_rate [-]')
    plt.ylabel('win_rate [%]')
    plt.grid(True)
    plt.plot(learning_rate, win_rate_learning_rate)
    plt.show()
    plt.savefig('win_rate (learning_rate).pgf')

    plt.title('win_rate (gamma)')
    plt.xlabel('gamma [-]')
    plt.ylabel('win_rate [%]')
    plt.grid(True)
    plt.plot(gamma_total, win_rate_gamma_total)
    plt.show()
    plt.savefig('win_rate (gamma).pgf')

    plt.title('win_rate (total)')
    plt.xlabel('episodes [count]')
    plt.ylabel('win_rate [%]')
    plt.grid(True)
    plt.plot(total_episodes, win_rate_total_episodes)
    plt.show()
    plt.savefig('win_rate (episodes).pgf')
\end{lstlisting}

\end{document}