Известия РАН. Теория и системы управления, 2023, № 3, стр. 76-89

ОБУЧЕНИЕ С ПОДКРЕПЛЕНИЕМ ДЛЯ МОДЕЛЬНЫХ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

С. С. Семенов^a, *, В. И. Цурков^b, **

^a МФТИ
МО, Долгопрудный, Россия

^b ФИЦ ИУ РАН
Москва, Россия

^* E-mail: semenov.ss@phystech.edu
^** E-mail: tsur@ccas.ru

Поступила в редакцию 10.11.2022
После доработки 08.01.2023
Принята к публикации 06.02.2023

EDN: EVAFAM
DOI: 10.31857/S0002338823030125

Полный текст (PDF)

Аннотация

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

Введение. К настоящему времени известны широко применяемые классические подходы в оптимальном управлении, такие, как принцип максимума Понтрягина, принцип оптимальности Беллмана, численные методы и т.д. Однако круг их использования ограничен. В последнее время в данной области получило развитие машинное обучение на нейронных сетях.

Обучение с подкреплением формулирует задачу оптимального управления на языке марковского процесса принятия решений и осуществляет переход к эквивалентной задаче оптимизации. Задача оптимального управления может быть переведена на язык принятия решения. Для осуществления перехода к эквивалентной задаче оптимизации вводятся такие объекты, как агент и среда. Среда – это некоторый марковский процесс принятия решений, который характеризуется пространством действий s ∈ S, пространством состояний a ∈ A, динамикой среды $\mathcal{P}_{{ss'}}^{a}$, функцией вознаграждения $\mathcal{R}_{s}^{a}$ и дисконтирующим фактором γ. Агент представляет собой некоторый стохастический алгоритм, который принимает на вход состояние среды s и возвращает действие a, которое необходимо принять, чтобы максимизировать итоговое вознаграждение. Взаимодействуя со средой, агент накапливает опыт игры и с каждой новой попыткой улучшает стратегию своей игры. Осуществив сотни тысяч попыток, стратегия агента сходится к оптимальной. Полученная стратегия максимизирует дисконтированную награду агента по траекториям при взаимодействии со средой и, как следcтвие, решает исходную задачу оптимального управления.

В настоящее время существуют два основных семейства алгоритмов обучения с подкреплением, в основе которых лежат различные принципы, а именно семейство Actor-Critic и семейство Policy Gradient. В решении практических задач наиболее эффективными являются алгоритмы DDPG [1], TRPO [2] из Policy Gradient и алгоритмы SAC [3], A2C [4] из Actor-Critic. В данной работе используется алгоритм Proximal Policy Optimization [5–7], который базируется на идее обновления весов не только с помощью подсчета градиента стратегии как в Policy Gradient, но и на выборе наиболее релевантного действия актором и оценке правдоподобия выбранного действия критиком как в Actor-Critic. Обучение с подкреплением успешно применяется в работах [8–12].

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

1. Постановка задачи. 1.1. Линейная задача оптимального управления. Имеем простейшую динамическую модель распределения ресурсов с двумя подсистемами. Близкие задачи оптимального управления широко представлены в книге [13]:

$\begin{gathered} \mathcal{F}(u) = {{x}_{1}}(T) + {{x}_{2}}(T) \to \max , \\ \frac{{d{{x}_{1}}}}{{dt}} = {{a}_{1}}(t){{u}_{1}}(t), \\ \end{gathered} $

(1.1)

$\begin{gathered} \frac{{d{{x}_{2}}}}{{dt}} = {{a}_{2}}(t){{u}_{2}}(t), \\ {{u}_{1}} \geqslant 0,\quad {{u}_{2}} \geqslant 0,\quad {{u}_{1}} + {{u}_{2}} \leqslant W = {\text{const}}, \\ \end{gathered} $

$\begin{gathered} t \in [0,T],\quad u = {{[{{u}_{1}},{{u}_{2}}]}^{{\text{T}}}}, \\ {{x}_{1}}(0) = {{x}^{1}},\quad {{x}_{2}}(0) = {{x}^{2}}, \\ \end{gathered} $

где u₁(t), u₂(t) – управления, x₁(t), x₂(t) – фазовые переменные, t ∈ ${{\mathbb{R}}_{ + }}$ – время, T ∈ ${{\mathbb{R}}_{ + }}$ – конечное время, a₁(t), a₂(t) – заданные функции, W, x¹, x² – константы.

1.2. Задача оптимального потребления [14]. Имеем

(1.2)

$\begin{gathered} \mathcal{F}(u) = \int\limits_0^T {\exp ( - \alpha t)g(u(t))dt \to \max ,} \\ \dot {x} = \rho x - u,\quad x(0) = {{x}_{0}},\quad x(T) = 0, \\ u(t) \geqslant 0,\quad t \in [0,T], \\ \end{gathered} $

где u(t) – интенсивность потребления или мгновенное значение потребления в момент времени t; x(t) – денежный капитал в момент времени t; g(u) – функция полезности потребления; α – ставка дисконтирования; ρ – банковская депозитная ставка.

Функция полезности потребления g(u) удовлетворяет условиям:

1) g(u) ≥ 0,

2) g(u) строго возрастает для u ≥ 0,

3) g(u) строго вогнутая дифференцируемая функция в области u ≥ 0.

1.3. Дискретная стохастическая задача. Пусть депозитная ставка является случайной величиной:

(1.3)

$\begin{gathered} \mathcal{F}(u) = {{\mathbb{E}}_{\rho }}\sum\limits_{k = 0}^K {\exp ( - \alpha k)g({{u}_{k}}) \to \max ,} \\ {{x}_{{k + 1}}} - {{x}_{k}} = \rho {{x}_{k}} - {{u}_{k}}, \\ {{x}_{0}} = a,\quad {{x}_{K}} = 0, \\ {{u}_{k}} \geqslant 0,\quad t \in \overline {0,K} , \\ \end{gathered} $

где ρ – депозитная ставка; x_k – значение капитала в момент времени k; u_k – значение потребления в момент времени k; ${{\mathbb{E}}_{\rho }}$[f] – математическое ожидание f по ρ, k и K ∈ $\mathcal{I}$ = {0, 1, 2, …}.

Будут представлены дискретное распределение вероятностей, винеровский процесс и пуассоновский процесс.

Рассмотрим дискретное распределение вероятностей. Пусть {t${{\} }_{{t \in \mathbb{N}}}}$ – процесс, заданный в виде последовательности независимых и одинаково распределенных случайных величин. Пример случайного распределения представлен на рис. 1 с параметрами:

(1.4)

$\mathbb{P}(\rho = r) = p,\quad r \in \{ 1.05,\,\,1.06,\,\,1.07,\,\,1.08,\,\,1.09\} ,$

где $\mathbb{P}$(ρ = r) – вероятность того, что ρ принимает значение r.

Рис. 1.

Коэффициент прироста капитала как дискретное распределение вероятностей

Рассмотрим винеровский процесс. Пусть {ρ_t}_t_{∈ [0,}_T] – геометрическое броуновское движение, т.е. процесс, подчиняющийся дифференциальному уравнению:

(1.5)

$\frac{{d{{\rho }_{t}}}}{{{{\rho }_{t}}}} = \alpha dt + \sigma d{{W}_{t}},$

где W_t – винеровский процесс, dW_t – дифференциал винеровского процесса t ∈ ${{\mathbb{R}}_{ + }}$.

Для решения этого уравнения нам понадобится лемма Ито, сформулированная и доказанная, например, в [15].

Определение 1. Процесс X_t будем называть процессом Ито, если

${{X}_{t}} = {{X}_{0}} + \int\limits_0^t {u(s,\omega )ds + \int\limits_0^t {{v}(t,\omega )d{{W}_{t}},} } $

$d{{X}_{t}} = udt + wd{{W}_{t}}.$

Лемма Ито. Пусть X_t – процесс Ито, задаваемый дифференциалом:

$d{{X}_{t}} = udt + wd{{W}_{t}},$

и пусть g(t, x) дважды непрерывно дифференцируемая функция на [0, +∞) × $\mathbb{R}$. Тогда Y_t = g(t, X_t) – снова есть процесс Ито и

$d{{Y}_{t}} = \frac{{\partial g}}{{\partial t}}dt + \frac{{\partial g}}{{\partial x}}d{{X}_{t}} + \frac{1}{2}\frac{{{{\partial }^{2}}g}}{{{{\partial }^{2}}x}}{{(d{{X}_{t}})}^{2}},$

где (cX_t)² вычисляется с использованием следующих правил:

$dtd\sim dtd{{W}_{t}}\sim 0,\quad d{{W}_{t}}d{{W}_{t}}\sim dt.$

Воспользовавшись леммой Ито, получаем

${{\rho }_{t}} = {{\rho }_{0}}\exp \left( {\left( {\alpha - \frac{{{{\sigma }^{2}}}}{2}} \right)t + \sigma {{W}_{t}})} \right).$

Поведение траекторий представлено на рис. 2.

Рис. 2.

Коэффициент прироста капитала как марковский процесс (16 реализаций)

Рассмотрим пуассоновский процесс. Пусть {ρ_t}_t_{∈ [0,}_T] – случайная функция, подчиняющаяся дифференциальному уравнению:

(1.6)

$\frac{{d{{\rho }_{t}}}}{{{{\rho }_{t}}}} = (\alpha - \lambda )dt + \sigma d{{N}_{t}},$

где N_t – счетчик пуассоновского процесса с интенсивностью λ. Решение стохастического дифференциального уравнения получается с использованием леммы Ито аналогично случаю винеровского процесса. Имеем

${{\rho }_{t}} = {{\rho }_{0}}\exp ((\alpha - \lambda )t + {{N}_{t}}\ln (1 + \sigma )).$

Поведение траекторий представлено на рис. 3.

Рис. 3.

Коэффициент прироста капитала как пуассоновский процесс (16 реализаций)

2. Решения детерминированных задач. 2.1. Линейная задача распределения ресурсов. Для задачи (1.1) применим принцип максимума Понтрягина (см., например, в [16]).

Определим класс (множество) допустимых управлений как множество m-мерных вектор-функций u(t) = (u₁(t), u₂(t), …, u_m(t)), кусочно-непрерывных на заданном отрезке T = [0, T] с условием (ограничением) u(t) ∈ $\mathcal{U}$, t ∈ T, где $\mathcal{U}$ ⊆ ${{\mathbb{R}}^{m}}$ – заданное множество. В формальной записи множество допустимых управлений $\mathcal{W}$ имеет следующий вид:

$\mathcal{W} = \{ u \in {{\mathcal{C}}_{m}}(T),{\mathbf{u}}(t) \in \mathcal{U},t \in {\mathbf{T}}\,\} .$

Рассмотрим обобщенный вариант простейшей задачи для линейной по состоянию системы с неразделенными переменными x, u:

(2.1)

$\begin{gathered} \mathcal{F}({\mathbf{u}}) = \langle {\mathbf{c}},{\mathbf{x}}({{t}_{1}})\rangle \to \min ,\quad {\mathbf{u}} \in \mathcal{W}, \\ {\mathbf{\dot {x}}} = {\mathbf{A}}(u,t)x + {\mathbf{b}}({\mathbf{u}},t),\quad {\mathbf{x}}({{t}_{0}}) = {{{\mathbf{x}}}_{0}}, \\ \mathcal{W} = \{ {\mathbf{u}} \in {{\mathcal{C}}_{m}}(T),{\mathbf{u}}(t) \in \mathcal{U},t \in T = [0,T]\} , \\ {\mathbf{A}} \in {{\mathbb{R}}^{{2 \times 2}}},\quad {\mathbf{x}} \in {{\mathbb{R}}^{2}},\quad {\mathbf{u}} \in {{\mathbb{R}}^{2}},\quad {\mathbf{b}} \in {{\mathbb{R}}^{2}},\quad {\mathbf{c}} \in {{\mathbb{R}}^{2}}, \\ \end{gathered} $

где 〈·, ·〉 – скалярное произведение.

Пусть множество $\mathcal{U}$ допустимых значений управления является компактом в ${{\mathbb{R}}^{n}}$. Пусть матричная функция A(u, t) и вектор-функция b(u, t) непрерывны на произведении $\mathcal{U}$ × $\mathcal{T}$.

Рассмотрим функцию Гамильтона–Понтрягина для (2.1):

$H(\psi ,{\mathbf{x}},{\mathbf{u}},t) = \langle \psi ,{{{\mathbf{A}}}^{{\text{T}}}}({\mathbf{u}},t){\mathbf{x}} + b({\mathbf{u}},t)\rangle ,$

а также сопряженную систему:

$\dot {\psi } = - {{H}_{x}}(\psi ,{\mathbf{x}},{\mathbf{u}},t) = - {{{\mathbf{A}}}^{{\text{T}}}}({\mathbf{u}},t)\psi ,\quad \psi ({{t}_{1}}) = - {\kern 1pt} {\kern 1pt} {\mathbf{c}},$

где ψ и c – двумерные векторы, причем c = (1, 1)^т.

Чтобы допустимое управление u(t), t ∈ T было оптимально в задаче (2.1), необходимо, чтобы всюду на T выполнялось условие

${\mathbf{u}}(t) = \arg \mathop {\max }\limits_{{v} \in \mathcal{U}} H(\psi (t,{\mathbf{u}}),{\mathbf{x}}(t,{\mathbf{u}}),{v},t).$

Для задачи (1.1) получаем окончательно

$H = {{a}_{1}}{{y}_{1}}{{\psi }_{1}}(t) + {{a}_{2}}{{y}_{2}}{{\psi }_{2}}(t),$

${{\dot {\psi }}_{1}} = \frac{{\partial H}}{{\partial {{x}_{1}}}} = 0,$

${{\dot {\psi }}_{2}} = \frac{{\partial H}}{{\partial {{x}_{2}}}} = 0.$

Поэтому

$\frac{{\partial H}}{{\partial {{x}_{1}}}} = \frac{{\partial H}}{{\partial {{x}_{2}}}} = 0,$

$\begin{gathered} \psi = {\text{const}}, \\ \psi ({{t}_{1}}) = - {\kern 1pt} {\kern 1pt} {\mathbf{c}} = {\mathbf{1}}, \\ \end{gathered} $

где 1 – единичный вектор.

Решение выглядит так:

(2.2)

$\begin{gathered} u_{1}^{*} = \left\{ \begin{gathered} W,\quad {{a}_{1}}(t) \geqslant {{a}_{2}}(t), \hfill \\ 0,\quad {{a}_{1}}(t) < {{a}_{2}}(t), \hfill \\ \end{gathered} \right. \\ u_{2}^{*} = \left\{ \begin{gathered} 0,\quad {{a}_{1}}(t) \geqslant {{a}_{2}}(t), \hfill \\ W,\quad {{a}_{1}}(t) < {{a}_{2}}(t). \hfill \\ \end{gathered} \right. \\ \end{gathered} $

Если a₁(t) = t, a₂(t) = 1 – t, t ∈ [0, 1], то решение иллюстрирует рис. 4. Имеем одну точку переключения. Если a₁(t) =t, a₂(t) = sin(3.5πt), t ∈ [0, 1], то решение иллюстрируется с помощью рис. 5. Имеем три точки переключения.

Рис. 4.

Аналитическое решение линейной задачи оптимального управления с одной точкой переключения

Рис. 5.

Аналитическое решение линейной задачи оптимального управления с тремя точками переключения

2.2. Задача оптимального потребления. Безусловно, эту задачу можно было решать принципом максимума, но можно и принципом Беллмана.

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

Дискретизация (1.2) по времени дает:

(2.3)

$\begin{gathered} \sum\limits_{t = 0}^T {{{\beta }^{t}}\ln ({{u}_{t}}) \to \mathop {\max }\limits_{{{u}_{t}}} } , \\ {{x}_{{t + 1}}} = \alpha {{x}_{t}} - {{u}_{t}}, \\ {{x}_{0}} = a, \\ {{x}_{T}} = 0. \\ \end{gathered} $

Найдем решение с помощью принципа оптимальности Беллмана (см., например, в [14]).

Функция Беллмана имеет вид, где k – текущий номер:

${{S}_{k}}(x) = \mathop {\max }\limits_{{{u}_{t}},t = \overline {k,T} } \sum\limits_{t = k}^T {{{\beta }^{t}}\ln {{u}_{t}}} $

при условиях

$\begin{gathered} {{x}_{{t + 1}}} = \alpha {{x}_{t}} - {{u}_{t}}, \\ {{x}_{k}} = x. \\ \end{gathered} $

Запишем рекуррентное соотношение Беллмана

${{S}_{t}}(x) = \mathop {\max }\limits_{{{u}_{t}}} \{ {{\beta }^{t}}\ln ({{u}_{t}}) + {{S}_{{t + 1}}}(\alpha x - {{u}_{t}})\} $

с терминальным значением

${{S}_{T}}(x) = \left\{ \begin{gathered} 0,\quad x \geqslant 0, \hfill \\ - \infty ,\quad x < 0. \hfill \\ \end{gathered} \right.$

Имеем

(2.4)

${{u}_{k}}(x) = \frac{{\alpha x}}{{\sum\limits_{i = 0}^{T - k} {{{\beta }^{i}}} }}.$

В самом деле, подставим решение в правую часть уравнения Беллмана:

(2.5)

${{S}_{j}}(x) = \mathop {\max }\limits_{{{u}_{j}} \geqslant 0} \left[ {{{\beta }^{j}}\ln ({{u}_{j}}) + {{\beta }^{{j + 1}}}\sum\limits_{t = 0}^{T - j - 1} {\left\{ {{{\beta }^{t}}\ln \left[ {\frac{{\alpha (\alpha x - {{u}_{j}}){{{(\alpha \beta )}}^{t}}}}{{\sum\limits_{i = 0}^{T - j - 1} {{{\beta }^{i}}} }}} \right]} \right\}} } \right].$

Максимум получим дифференцированием правой части (2.5):

(2.6)

$\frac{{{{\beta }^{j}}}}{{{{u}_{j}}}} - {{\beta }^{{j + 1}}}\sum\limits_{t = 0}^{T - j - 1} {\frac{{{{\beta }^{t}}}}{{\alpha x - {{u}_{j}}}} = 0 \Rightarrow \,} {{u}_{j}} = \frac{{{{\beta }^{j}}\alpha x}}{{{{\beta }^{j}} + {{\beta }^{{j + 1}}}\sum\limits_{t = 0}^{T - j - 1} {{{\beta }^{t}}} }} = \frac{{\alpha x}}{{\sum\limits_{t = 0}^{T - j} {{{\beta }^{t}}} }}.$

Знак второй производной проверяется аналогично.

При подстановке (2.6) в правую часть соотношения (2.5) получаем

$\begin{gathered} {{S}_{j}}(x) = {{\beta }^{j}}\ln \left[ {\frac{{\alpha x}}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right] + {{\beta }^{{j + 1}}}\sum\limits_{t = 0}^{T - j - 1} {\left\{ {{{\beta }^{t}}\ln \left[ {\alpha \left( {\alpha x - \frac{{\alpha x}}{{\sum\limits_{i = 0}^{T - k} {{{\beta }^{i}}} }}} \right){{{(\alpha \beta )}}^{t}}{{{\left( {\sum\limits_{i = 0}^{T - j - 1} {{{\beta }^{i}}} } \right)}}^{{ - 1}}}} \right]} \right\}} = \\ = {{\beta }^{j}}\ln \left[ {\frac{{\alpha x}}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right] + {{\beta }^{{j + 1}}}\sum\limits_{t = 0}^{T - j - 1} {\left\{ {{{\beta }^{t}}\ln \left[ {\frac{{x{{\alpha }^{2}}{{{(\alpha \beta )}}^{t}}\beta }}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right]} \right\}} = {{\beta }^{j}}\ln \left[ {\frac{{\alpha x}}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right] + {{\beta }^{{j + 1}}}\sum\limits_{u = 0}^{T - j} {\left\{ {{{\beta }^{{u - 1}}}\ln \left[ {\frac{{x{{\alpha }^{2}}{{{(\alpha \beta )}}^{{u - 1}}}\beta }}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right]} \right\}} = \\ \end{gathered} $

$ = {{\beta }^{j}}\ln \left[ {\frac{{\alpha x}}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right] + {{\beta }^{j}}\sum\limits_{u = 0}^{T - j} {\left\{ {{{\beta }^{u}}\ln \left[ {\frac{{x\alpha {{{(\alpha \beta )}}^{u}}}}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right]} \right\}} = {{\beta }^{j}}\sum\limits_{t = 0}^{T - j} {\left\{ {{{\beta }^{t}}\ln \left[ {\frac{{\alpha x{{{(\alpha \beta )}}^{t}}}}{{\sum\limits_{i = 0}^{T - j} {{{\beta }^{i}}} }}} \right]} \right\}} .$

Решение уравнения Беллмана запишем как

(2.7)

${{S}_{k}}(x) = {{\beta }^{k}}\sum\limits_{t = 0}^{T - k} {\left\{ {{{\beta }^{t}}\ln \left[ {\frac{{\alpha x{{{(\alpha \beta )}}^{t}}}}{{\sum\limits_{i = 0}^{T - k} {{{\beta }^{i}}} }}} \right]} \right\}} .$

3. Построение решений с помощью обучения с подкреплением. В работе основой для построения численного решения задач оптимального управления служит алгоритм Proximal Policy Optimization [5]. Вводится ряд понятий.

Определение 2. Марковский процесс принятия решений: 〈S, A, P, R, γ〉, где S – пространство состояний; A – пространство действий, $P_{{ss'}}^{a}$ = $\mathbb{P}$(s_t _{+ 1} = s'|s_t = s, a_t = a) – динамика среды или вероятность перехода агента из состояния s в состояние s' при условии действия a в момент времени t; $R_{s}^{a}$ = $\mathbb{E}$[r_t|s_t = s, a_t = a] – функция вознаграждения. Она характеризует среднее вознаграждение агента в состоянии s при условии действия a в момент времени t; γ ∈ (0, 1] – дисконтирующий фактор.

Определение 3. Стратегия агента:

${{\pi }_{\theta }}(a|s) = \mathbb{P}({{a}_{t}} = a|{{s}_{t}} = s,\theta ).$

Определение 4. Награда за эпизод:

${{r}_{t}} = \mathbb{E}[r|{{a}_{t}} = a,{{s}_{t}} = s],$

${{G}_{t}} = {{r}_{{t + 1}}} + \gamma {{r}_{{t + 2}}} + ... + {{\gamma }^{{T - t - 1}}}{{r}_{T}} = \sum\limits_{t' = t}^{T - 1} {{{\gamma }^{{t' = t}}}} {{r}_{{t' + \,1}}}.$

Определение 5. Полезность состояния:

$V(s) = {{\mathbb{E}}_{\pi }}[{{G}_{t}}|{{s}_{t}} = s].$

Определение 6. Полезность состояния-действия:

$Q(a,s) = {{\mathbb{E}}_{\pi }}[{{G}_{t}}|{{s}_{t}} = s,{{a}_{t}} = a].$

Определение 7. Функция преимущества:

$A(a,s) = Q(a,s) - V(s).$

3.1. Двойственная задача оптимизации. Определим отношение вероятностей r_t(θ) как

${{r}_{t}}(\theta ) = \frac{{{{\pi }_{\theta }}({{a}_{t}}|{{s}_{t}})}}{{{{\pi }_{{{{\theta }_{{old}}}}}}({{a}_{t}}|{{s}_{t}})}},\quad r({{\theta }_{{old}}}) = 1,$

где θ_old – параметры текущей стратегии.

TRPO [2] максимизирует суррогатный функционал:

${{L}^{{CLI}}}(\theta ) = {{\hat {\mathbb{E}}}_{t}}\left[ {\frac{{{{\pi }_{\theta }}({{a}_{t}}|{{s}_{t}})}}{{{{\pi }_{{{{\theta }_{{old}}}}}}({{a}_{t}}|{{s}_{t}})}}{{{\hat {A}}}_{t}}} \right],$

где ${{\hat {\mathbb{E}}}_{t}}$ – математическое ожидание по времени, а ${{\hat {A}}_{t}}$ – функция преимущества в момент времени t.

Без дополнительных ограничений максимизация L^CLI приведет к чрезмерно большому обновлению стратегии. Введем дополнительный штраф за изменения стратегии, которые удаляют r_t(θ) от 1.

Двойственная задача оптимизации

${{L}^{{CLIP}}}(\theta ) = {{\hat {\mathbb{E}}}_{t}}\left[ {\min \{ {{r}_{t}}(\theta ){{{\hat {A}}}_{t}},{\text{clip}}({{r}_{t}}(\theta ),1 - \epsilon ,1 + \epsilon ){{{\hat {A}}}_{t}}\} } \right],$

${{L}^{{CLIP}}}(\theta ) \to \mathop {\max }\limits_{\theta \in {{\mathbb{R}}^{n}}} ,$

где $\epsilon $ – гиперпараметр, а

${\text{clip}}(x,a,b) = \left\{ \begin{gathered} a,\quad {\text{если}}\quad x < a, \hfill \\ x,\quad {\text{если}}\quad a \leqslant x \leqslant b, \hfill \\ b,\quad {\text{если}}\quad x > b. \hfill \\ \end{gathered} \right.$

3.2. Proximal Policy Optimization (PPO). В [5] PPO содержит две независимые параметризации для актора и критика. Процесс принятия решений обеспечивается актором, который имеет параметризацию θ. Процедура оценки полезности действий актора осуществляется критиком, который имеет параметризацию ϕ.

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

4. Результаты вычислений. Для решения поставленных задач наряду с РРО применялись различные алгоритмы обучения с подкреплением семейства Policy Gradient, а именно TRPO [2], DDPG [1], SAC [3], A2C [4].

Для проведения экспериментов использовались фреймворки обучения с подкреплением RLlib и stablebaseline3.

4.1. Линейная задача оптимального управления (1.1). Аналитическое решение задачи (1.1) задается формулой (2.2). Для задачи (1.1) применяем дискретизацию по времени:

$\begin{gathered} \mathcal{F}({\mathbf{u}}) = x_{K}^{1} + x_{K}^{2} \to \max , \\ x_{{k + 1}}^{1} - x_{k}^{1} = a_{k}^{1}u_{k}^{1}\Delta t,\quad x_{{k + 1}}^{2} - x_{k}^{2} = a_{k}^{2}u_{k}^{2}\Delta t, \\ \end{gathered} $

$\begin{gathered} u_{k}^{1} \geqslant 0,\quad u_{k}^{2} \geqslant 0,\quad {{x}_{0}} = 0, \\ u_{k}^{1} + u_{k}^{2} \leqslant W,\quad k \in \overline {0,K} , \\ {{x}_{k}} = x({{t}_{k}}),\quad k \in \overline {0,K} ,\quad {{t}_{{k + 1}}} - {{t}_{k}} = \Delta t. \\ \end{gathered} $

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

Под состоянием будем понимать вектор из четырех компонент:

$s = (a_{t}^{1},a_{t}^{2},t,T - t),$

где $a_{t}^{1}$, и $a_{t}^{2}$ – значения динамических коэффициентов в текущий момент времени, t – текущее время с момента начала эпизода и T – t – оставшееся время до конца эпизода.

Остановимся на функции вознаграждения. Ввиду специфики задачи оптимизации и граничных условий наиболее естественным будет определить функцию вознаграждения для марковского процесса принятия решений следующим образом. Выразим x₁(t) и x₁(t) из уравнения (1.1):

${{x}_{1}}(t) = \int\limits_0^t {{{u}_{1}}(t){{a}_{1}}(t)dt,} $

${{x}_{2}}(t) = \int\limits_0^t {{{u}_{2}}(t){{a}_{2}}(t)dt.} $

Проведем дискретизацию по времени (x_k = x(t_k), k ∈ $\overline {0,K} $, t_k _{+ 1} – t_k = Δt):

$x_{t}^{1} = \sum\limits_{i = 0}^t {u_{i}^{1}a_{i}^{1}\Delta t,} $

$x_{t}^{2} = \sum\limits_{i = 0}^t {u_{i}^{2}a_{i}^{2}\Delta t.} $

Запишем мгновенные вознаграждения в случае действия [$u_{t}^{1}$, $u_{t}^{2}$]^т в момент времени t:

$\begin{gathered} r_{t}^{1} = u_{t}^{1}a_{t}^{1},\quad r_{t}^{2} = u_{t}^{2}a_{t}^{2}, \\ {{r}_{t}} = r_{t}^{1} + r_{t}^{2}. \\ \end{gathered} $

Рассмотрим пространство действий

$\begin{gathered} u = {{[{{u}^{1}},{{u}^{2}}]}^{{\text{T}}}}, \\ {{u}^{i}} \in [\epsilon , + \infty ). \\ \end{gathered} $

Для реализации ограничений на допустимые значения управления $u_{t}^{1}$ + $u_{t}^{2}$ ≤ W существует два основных приема, а именно маскирование заведомо нерелевантных действий или с помощью штрафа за нарушение ограничений. В данном случае нарушение условия $u_{t}^{1}$ + $u_{t}^{2}$ ≤ W влечет за собой наложение штрафа и завершение эпизода. Штраф полагается равным максимально возможной награде за эпизод. Подобный сценарий форсирует агента на использование значений действия из допустимого множества и позволяет ему избегать нарушения поставленных ограничений.

Рассмотрим дисконтирующий фактор. Среда эпизодическая, поэтому необходимости в явном использовании γ нет. Здесь и далее y = 1, т.е. дисконтирование отсутствует. Динамика среды представляет собой детерминированную функцию, которая не зависит от принятого агентом действия:

${{s}_{{t + 1}}} = (a_{{t + 1}}^{1},a_{{t + 1}}^{2},t + 1,T - t - 1).$

Результаты работы PPO таковы. Рассмотрим задачу распределения ресурсов. Согласно принципу максимума Понтрягина, аналитическое решение имеет вид ступенчатых функций:

$u_{1}^{*} = \left\{ \begin{gathered} 1,\quad t \geqslant 0.5, \hfill \\ 0,\quad t < 0.5, \hfill \\ \end{gathered} \right.$

$u_{2}^{*} = \left\{ \begin{gathered} 0,\quad t \geqslant 0.5, \hfill \\ 1,\quad t < 0.5. \hfill \\ \end{gathered} \right.$

На рис. 6 получено совпадение с этим решением, когда применяется обучение с подкреплением, на рис. 7 – то же самое для трех точек переключения.

Рис. 6.

Аналитическое и численное решения линейной задачи оптимального управления при a₁(t) = t, a₂(t) = 1 – t

Рис. 7.

Аналитическое и численное решения линейной задачи оптимального управления при a₁(t) = t, a₂(t) = = max{sin(3.5πt), 0}

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

4.2. Задача оптимального потребления (1.2). Аналитическое решение задачи (1.2) задается формулой (2.7). Под состоянием будем понимать вектор из трех компонент:

$s = (c,t,T - t),$

где c – значение доступного капитала в текущий момент времени, t – текущее время с момента начала эпизода и T – t – оставшееся время до конца эпизода.

Определим дисконтирующий фактор как γ = β, а вознаграждение – как полезность потребления в текущий момент времени.

${{r}_{t}} = \log ({{u}_{t}}).$

Складывая все дисконтированные вознаграждения в каждый момент времени, получим итоговое дисконтированное значение вознаграждения за эпизод, которое совпадает со значением функционала:

${{G}_{0}} = \sum\limits_{i = 0}^{T - 1} {{{\gamma }^{t}}{{r}_{t}}} = \sum\limits_{i = 0}^{T - 1} {{{\beta }^{t}}\log ({{u}_{t}}).} $

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

Применяя оптимизацию градиента стратегии, PPO обеспечивает абсолютную сходимость численного решения при фиксированном исходном значении капитала x в (2.4) (см. рис. 8) к аналитическому с точностью до дискретизации.

Рис. 8.

Управление для задачи оптимального потребления

4.3. Задача стохастического кредитования (1.3). Эта задача сложнее предыдущих из-за недетерминированности среды. Данная задача не имеет аналитического решения, поэтому не удается сравнить с эталонным.

Марковский процесс принятия решений для задачи стохастического кредитования задается аналогично детерминированному случаю. Ниже представлены решения трех типов задач (1.4)–(1.6) стохастического кредитования, полученные с использованием алгоритма оптимизации градиента стратегии. Для наших трех случаев решения представлены на рис. 9–11 . В данном случае удалось добиться сходимости алгоритмов обучения с подкреплением.

Рис. 9.

Управление для задачи оптимального потребления, где коэффициент прироста капитала представлен как дискретное распределение вероятностей

Рис. 10.

Управление для задачи оптимального потребления, где коэффициент прироста капитала представлен как диффузионный процесс

Рис. 11.

Управление для задачи оптимального потребления, где коэффициент прироста капитала представлен как пуассоновский процесс

Заключение. Итак, обучение с подкреплением строит решения для детерминированных задач оптимального управления. Они совпадают с найденными посредством классических алгоритмов. Также получаются разрывные управления. Для стохастических задач оптимального управления данный подход дает сходящуюся последовательность. Однако не следует забывать, что количество итераций при обучении может быть очень большим (в нашем случае – несколько миллионов). Это имеет место, в частности, при росте количества точек дискретизации. Метод обучения с подкреплением демонстрирует свою эффективность для широкого класса задач. Тем не менее всегда нужно выбирать, когда он успешно конкурирует с традиционными аналитическими и численными методами.

Список литературы

Sewak M. Deterministic Policy Gradient and the DDPG: Deterministic-Policy-Gradient-Based Approaches. 2019.
Schulman J. Trust Region Policy Optimization. 2015. https://arxiv.org/abs/1502.05477.
Haarnoja T. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Rein-forcement Learning with a Stochastic Actor. 2018. https://arxiv.org/abs/1801.01290.
Huang S. A2C is a special case of PPO. 2022. https://arxiv.org/abs/2205.09123.
Schulman J. Proximal Policy Optimization Algorithms. 2017. https://arxiv.org/abs/1707.06347.
Zhang L. Penalized Proximal Policy Optimization for Safe Reinforcement Learning. 2022. https://arxiv.org/abs/2205.11814.
Chen X. The Sufficiency of Off-policyness: PPO is insufficient according to an Off-policy Measure. 2022. https://arxiv.org/abs/2205.10047.
Ghosh A. Provably Efficient Model-Free Constrained RL with Linear Function Approximation. 2022. https://arxiv.org/abs/2206.11889.
Song Z. Safe-FinRL: A Low Bias and Variance Deep Reinforcement Learning Implementation for High-Freq Stock Trading. 2022. https://arxiv.org/abs/2206.05910.
Kaledin M. Variance Reduction for Policy-Gradient Methods via Empirical Variance Minimization. 2022. https://arxiv.org/abs/2206.06827.
Luo Q. Finite-Time Analysis of Fully Decentralized Single-Timescale Actor- Critic. 2022. https://arxiv.org/abs/2206.05733.
Deka A. ARC – Actor Residual Critic for Adversarial Imitation Learning. 2022. https://arxiv.org/abs/2206.02095.
Цурков В.И. Динамические задачи большой размерности. М.: Наука, 1988. 287 с.
Бекларян Л.А., Флёрова А.Ю., Жукова А.А. Методы оптимального управления: учеб. пособие. М.: Наука, 2018.
Оксендаль Б. Стохастические дифференциальные уравнения. Введение в теорию и приложеия. М.: Мир, 2003.
Понтрягин Л.С. Принцип максимума в оптимальном управлении. М.: Наука, 2004.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Известия РАН. Теория и системы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал