[2020 년 9 월 3 일 업데이트: SARSA 와 Q 학습 알고리즘을 수정하여 차이점을 더 명확하게 했습니다. [2021 년 9 월 19 일 업데이트:爱吃猫의鱼 덕분에 이 게시물이 중국어로 있습니다].
최근 몇 년간 인공지능 (AI) 분야에서 흥미로운 뉴스가 발생했습니다. AlphaGo 가 고 게임에서 최고의 전문가 인간 플레이어를 누부했습니다. 얼마 지나지 않아 감독 학습 없이 인간의 지식을 바탕으로 한 알고리즘이 AlphaGo 를 100 대 0 으로 누부했습니다. OpenAI 에서 개발된 봇은 DOTA2 1v1 대회에서 최상위 전문가 게임 플레이어들을 이겼습니다. 이러한 사실을 알게 된 후에는 이러한 알고리즘 뒤의 마법—강화학습 (RL)—에 대해 호기심을 느껴야 합니다. 저는 이 게시물을 간략히 소개하기 위해 작성했습니다. 우리는 먼저 몇 가지 기본 개념을 소개한 다음, RL 문제를 해결하는 고전적인 접근법을 자세히 다룰 것입니다. hopefully, 이 게시물이 초보자들이 최신 연구의 경계에서 미래 연구를 시작할 좋은 출발점이 되기를 바랍니다.
예를 들어, 우리가 알려지지 않은 환경에 에이전트가 있고, 이 에이전트는 환경과 상호작용하여 일부 보상을 얻을 수 있습니다. 에이전트는 누적 보상을 최대화하기 위해 행동을 취해야 합니다. 현실에서는 봇이 높은 점수를 얻기 위해 게임을 플레이하거나 로봇이 물체와 물리적 작업을 수행하려는 시도를 할 수 있으며, 이러한 것들만으로는 제한되지 않습니다.
강화학습 (RL) 의 목표는 실험적 시도와 상대적으로 간단한 피드백을 통해 에이전트에 대한 좋은 전략을 학습하는 것입니다. 최적의 전략으로 에이전트는 미래 보상을 최대화하기 위해 환경을 능동적으로 적응할 수 있습니다.
이제 RL 에서 핵심 개념을 공식적으로 정의해 봅시다.
에이전트는 환경에서 행동합니다. 환경이 특정 행동을 취하는 방식은 우리가 알지 못하거나 알지 못하는 모델로 정의됩니다. 에이전트는 환경의 여러 상태 ($s \in \mathcal{S}$) 중 하나에 머물 수 있으며, 다른 상태로 전환하기 위해 여러 행동 ($a \in \mathcal{A}$) 중 하나를 선택할 수 있습니다. 에이전트가 도달하는 상태는 상태 간 전이 확률 ($P$) 에 의해 결정됩니다. 한 번 행동을 취하면 환경은 피드백으로 보상을 ($r \in \mathcal{R}$) 제공합니다.
모델은 보상 함수와 전이 확률을 정의합니다. 우리가 모델을 어떻게 작동하는지 알지 못하거나 알 수 있으며, 이는 두 가지 상황을 구분합니다:
모델을 아는 것: 완전한 정보로 계획; 모델 기반 RL 수행. 우리가 환경을 완전히 알 때, 동적 프로그래밍 (DP) 로 최적의 해를 찾을 수 있습니다. 알고리즘 101 수업에서 "최대 증가 부분 서열"이나 "여행하는 판매원 문제"를 기억하고 계신가요? LOL. 그러나 이 게시물의 초점은 아닙니다.
모델을 모르는 것: 불완전한 정보로 학습; 모델 기반 RL 또는 알고리즘의 일부로 모델을 명시적으로 학습 시도. 대부분의 다음 내용은 모델이 알려지지 않은 시나리오에 해당합니다.
에이전트의 정책 $\pi(s)$ 는 특정 상태에서 총 보상을 최대화하는 것을 목표로 하는 최적의 행동을 취할 수 있는 지침을 제공합니다. 각 상태는 대응하는 정책을 실행함으로써 이 상태에서 받을 수 있는 미래 보상의 예상 금액을 예측하는 가치 함수 $V(s)$ 와 연관됩니다. 즉, 가치 함수는 상태가 얼마나 좋은지를 정량화합니다. 정책과 가치 함수는 강화학습에서 학습하려는 것입니다.
에이전트와 환경의 상호작용은 시간 $t=1, 2, \…, T$ 에 걸쳐 행동과 관찰된 보상의 시퀀스를 포함합니다. 이 과정에서 에이전트는 환경에 대한 지식을 축적하고, 최적 정책을 학습하며, 다음에 어떤 행동을 취할지 결정하여 최선의 정책을 효율적으로 학습합니다. 시간 단계 $t$ 의 상태, 행동, 보상을 각각 $S_t$, $A_t$, $R_t$ 로 표기하겠습니다. 따라서 상호작용 시퀀스는 에피소드 (또는
마르코프 결정 과정 (MDP) 은 $\oldsymbol{\mathcal{M}} = \langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle$ 의 5 가지 요소로 구성되며, 여기서 기호들은 이전 섹션의 핵심 개념과 동일한 의미를 가지며 강화학습 (RL) 문제 설정과 잘 정렬되어 있습니다:
$\oldsymbol{\mathcal{S}}$ - 상태 집합;
$\oldsymbol{\mathcal{A}}$ - 행동 집합;
$P$ - 전이 확률 함수;
$R$ - 보상 함수;
$\gamma$ - 미래 보상에 대한 할인 계수.
알 수 없는 환경에서는 $P$ 와 $R$ 에 대해 완벽한 지식이 없습니다.
순환적 업데이트 과정은 상태 가치 함수와 행동 가치 함수에 기반한 방정식으로 더 분해될 수 있습니다. 미래 행동 단계로 갈수록, 정책 $\pi$ 를 따르면서 $V$ 와 $Q$ 를 대안적으로 확장합니다.
만약 최적의 값만 관심이 있고 정책 후 따른 기대치를 계산하지 않는다면, 정책 없이 대안적 업데이트 중 최대 보상 (returns) 에 바로 진입할 수 있습니다. 요약하자면, 최적의 값 $V_$ 와 $Q_$ 는 여기서 정의된 대로 우리가 얻을 수 있는 가장 좋은 보상입니다.
예상치 않게 벨만 기대 방정식과 매우 비슷해 보입니다.
환경에 대한 완전한 정보가 있다면 이는 계획 (planning) 문제로 바뀝니다. 동적 프로그래밍 (DP) 으로 해결 가능합니다. 불행히도, 대부분의 시나리오에서는 $P_{ss'}^a$ 나 $R(s, a)$ 를 알 수 없으므로 벨만 방정식을 직접 적용하여 MDP 를 해결할 수 없습니다. 그러나 이는 많은 RL 알고리즘의 이론적 기초를 제공합니다.
이제 RL 문제를 해결하는 주요 접근법과 고전적인 알고리즘을 살펴보겠습니다. 향후 포스트에서는 각 접근법을 더 깊이 파고들 계획입니다.
모델이 완전히 알려졌을 때, 벨만 방정식을 따르며 동적 프로그래밍 (DP) 을 사용하여 가치 함수를 반복적으로 평가하고 정책을 개선할 수 있습니다.
일반화된 정책 반복 (GPI) 알고리즘은 정책 평가와 개선을 결합하여 정책을 개선하는 반복적인 절차를 지칭합니다.
GPI 에서 가치 함수는 현재 정책의 실제 값에 더 가까워지도록 반복적으로 근사되며, 동시에 정책은 최적성에 접근하도록 반복적으로 개선됩니다. 이 정책 반복 과정은 작동하며 항상 최적성으로 수렴하지만 왜 그런가?
예를 들어, 정책 $\pi$ 가 있고 이를 탐욕적으로 행동을 취함으로써 개선된 버전 $\pi'$ 를 생성하면 $\pi'(s) = \arg\max_{a \in \mathcal{A}} Q_\pi(s, a)$ 입니다. 이 개선된 $\pi'$ 의 값이 더 좋다는 것은 보장됩니다:
첫째, $V(s) = \mathbb{E}[ G_t \vert S_t=s]$ 를 기억해 봅시다. 몬테카를로 (MC) 방법은 간단한 아이디어를 사용합니다: 환경 역학을 모델링하지 않고 원료 경험의 에피소드에서 학습하며 관찰된 평균 보상을 기대 보상의 근사로 계산합니다. 경험적 보상 $G_t$ 를 계산하기 위해 MC 방법은 $S_1, A_1, R_2, \dots, S_T$ 와 같은 완전한 에피소드 $S_1, A_1, R_2, \dots, S_T$ 에서 학습해야 하며 $G_t = \sum_{k=0}^{T-t-1} \gamma^k R_{t+k+1}$ 를 계산하고 모든 에피소드가 결국 종료되어야 합니다.
여기서 $\mathbb{1}[S_t = s]$ 는 이산적 표시 함수입니다. 우리는 한 에피소드에서 하나의 상태가 여러 번 방문될 수 있으므로 (
Monte-Carlo 방법과 마찬가지로, Temporal-Difference (TD) 학습은 모델 프리 (model-free) 이며 경험의 에피소드에서 학습합니다. 그러나 TD 학습은 불완전한 에피소드에서 학습할 수 있으므로 종료까지 에피소드를 추적할 필요가 없습니다. Sutton & Barto (2017) 는 RL 책에서 이를