(전공복습) 인공지능 3. 강화학습

차례

• 차례
• 들어가기 전에
• Online Learning
  • Model Based Learning
  • Model Free Learning
    • Passive Reinforcement Learning
      • Direct Evaluation
      • Sample Based Policy Evaluation
        • Temporal Difference Learning(TD Method)
    • Active Reinforcement Learning
      • Q-Learning
• Exploration
  • Epsilon Greedy
  • Exploration Function
  • Regret
• Feature Based Representation
  • Linear Value Function
  • Approximate Q-Learning
    • 회귀(Regresssion)
      • 최소자승법(Least Squres, 최소제곱법)
  • Policy Search
• 정리

들어가기 전에

이 글은 컴퓨터학과 이중전공생으로서 배운 것들을 다시 한번 정리하고자 남기는 글입니다. 불완전한 기억 등의 이유로 오류가 있을 수 있으며, 참조 내지 이정표로만 사용해주세요.
본 게시글은 고려대학교의 인공지능 강의를 기반으로 작성자의 추가적인 설명이 덧붙여진 글입니다. 또한 해당 강의는 UC 버클리 CS188을 기반으로 함을 밝힙니다.

Online Learning

지난번에 다룬 MDP는 실제로 에이전트가 행동을 하면서 최적의 정책을 알아내는 것이 아니다. 모든 상태와 행동에 대한 전이함수 \(T\)와 보상함수 \(R\)이 주어져 있기 때문에, 에이전트는 행동을 실제로 수행하는 것이 아니라, 그냥 계산만 하면 되고, 그 계산에 따라 정책을 만들고 행동하면 된다. 이처럼 상태와 보상에 대한 정보가 모두 주어진 것을 Offline Planning이라 한다. 실제로 움직이지 않고(Offline) 계획을 세울 수 있기 때문이다.

반면, 상태와 보상에 대한 정보가 없는 경우, 직접 행동을 수행하고 그 결과를 가지고 판단하는 수밖에 없다. 일일히 행동하면서 학습하는 것이다. 이러한 학습 방법을 Online Learning이라고 한다. 이와 관련하여 아래와 같은 고려사항들을 알아두자.

• Exploration: 상태에 대한 정보를 얻기 위해서는 기존에 하지 않았던 행동들도 해봐야 된다. 계속 같은 행동만 하면 새로운 정보를 학습하기 어려울 것이다.
• Exploitation: 그렇다고 계속 새로운 행동만 하는 것도 곤란하다. Exploration으로 얻은 정보들을 활용해서 보상을 최대화하는 행동을 선택할 필요도 있다.
• Regret: 정보가 부족한 상태에서, 최적의 선택을 하기는 어렵다. 최적의 선택으로 얻게 되는 보상과 실제로 내가 선택한 행동으로 얻은 보상이 얼마나 차이나는지 알 필요가 있다.
• Sampling: 무작위성이 가미되어 있다면, 한 번의 행동으로 전이함수를 정확히 알아낼 수는 없다. 여러번 반복해야 각 행동의 결과를 상대적으로 정확하게 예측할 수 있을 것이다.
• Difficulty: 상기한 이유로, 모든 전이 함수가 밝혀진 MDP에 비해 Online Learning은 어렵다.

Model Based Learning

경험을 통해서 정보를 수집하고, 그 정보를 기반으로 MDP를 수행하는 것을 의미한다. Model Based Learning의 수행 단계는 아래와 같다.

1. 정보가 없는 상태로 행동하면서 각 \(s\)와 \(a\)에 따른 \(s'\)과 보상을 기록한다.
2. 이 기록을 기반으로 전이함수 \(\hat T\)와 보상함수 \(\hat R\)을 추정한다.
3. 추정한 \(\hat T\)와 \(\hat R\)을 가지고 MDP를 수행한다.

위 예제를 함께 살펴보자. 4번의 훈련을 통해, 각 상황에서의 \(s\), \(a\), \(s'\)을 수집했다. 우선 전이함수 \(\hat T\)를 추정해보자.

• \(\hat T(B, \mathrm {east}, C)\): 4번의 훈련 과정에서, \(B\) 상태에서 동쪽으로 이동하면 항상 \(C\)로 이동했다. 즉 이 확률은 \(1\)이다.
• \(\hat T(C, \mathrm {east}, D)\): 4번의 훈련 과정에서, \(C\) 상태에서 동쪽으로 이동하면 3번은 \(D\)로 이동했지만, 1번은 \(A\)로 이동했다. 따라서 이 확률은 \(0.75\)이다.
• \(\hat T(C, \mathrm {east}, A)\): 위와 마찬가지의 경우이므로, \(0.25\)이다.
• 그 외의 케이스도 위와 같이 계산 가능하다. 주어진 \(s\)와 \(a\)에서, \(s'\)으로 이동한 결과가 몇 퍼센트를 차지하는지 확인하면 되는 셈이다.

이번에는 보상 \(\hat R\)을 추정해보자.

• \(\hat R(B, \mathrm {east}, C)\): \(B\)에서 동쪽으로 이동하여 \(C\)로 가면 보상은 항상 \(-1\)이다.
• \(\hat R(C, \mathrm {east}, D)\): \(C\)에서 동쪽으로 이동하여 \(D\)로 가면 보상은 항상 \(-1\)이다.
• \(\hat R(D, \mathrm {exit}, x)\): \(D\)에서 탈출하여 학습을 종료하면 보상은 항상 \(+10\)이다.

Model Free Learning

위의 경우처럼 정보를 수집하고 그 정보를 바탕으로 모형(Model, 모델)을 만들어가는 방법을 Model Based Learning이라 한다. 여기서 모형이라 함은 결국 전이함수 \(\hat T\)와 보상함수 \(\hat R\)을 의미한다.
하지만, 전이함수와 보상함수를 구하려고 하지 않고, 다른 방식으로 각 상태의 기댓값을 계산할 수도 있다. 이러한 방법은 Model Free Learning이라고 한다.

Model Based Learning과 Model Free Learning을 이해하기 위해, 학생들의 평균 연령(기댓값)을 계산하는 문제를 해결한다고 하자.

• Offline Planning: \(E[A] = \sum\limits_a P(a) \cdot a\)로, 연령과 그 연령의 비중(확률)의 가중합이다. 즉, 일반적으로 정보가 주어졌을 때 기댓값을 계산하는 방식으로 계산한다.
• Model Based: \(E[A] \approx \sum\limits_a \hat P(a) \cdot a\)로, 이때 그 연령이 차지하는 비중을 추정한 값인 \(\hat P(a) = {\mathrm{num}(a) \over N}\)라고 할 수 있다. 즉, Offline Planning과 같은 방식으로 값을 계산하되, 알지 못하는 \(P(a)\)를 추정해서 계산하는 것이다.
• Model Free: \(E[A] \approx {1 \over N} \sum\limits_a a\)로, 명시적으로 \(P(a)\)를 추정하지 않고, 기댓값을 구하기 위에 다른 방법을 취한 것이다.

Passive Reinforcement Learning

고정된 정책 \(\pi(s)\)를 입력으로 하여, 각 상태의 보상 기댓값을 계산하는 방식이다. 행동을 별도로 선택하지 않고 주어진 정책에서 제시하는 행동만을 수행하기 때문에서 수동적(Passive)이라고 칭한다. 즉, 일종의 Policy Evaluation이라 볼 수 있다. 고정된 정책을 가지고 그 정책을 따랐을 때의 Value를 계산하기 때문이다.

Direct Evaluation

단순하게 정책에 따라 움직이고, 그 결과를 평가한다. 매 학습 단계마다 주어진 정책 \(\pi(s)\)에 따라 움직인다. 그리고 그 결과 최종적으로 얻은 보상들을 평균내어 각 상태에 더한다.

위 예제를 살펴보자. 각 상태의 값들은 어떻게 계산된 값일까?

• \(B\): Episode 1은 \(B\)에서 시작하여 \(+8\)을 획득한다. Episode 2도 마찬가지이다. 따라서 \(B\)의 보상 기댓값은 \(+8\)이다.
• \(E\): Episode 3과 4에서 각각 \(+8\)과 \(-12\)를 얻게 된다. 이들의 평균은 \(-2\)이다.
• \(C\): Episode 1, 2, 3에서 \(C\)의 값은 \(+9\)이다(\(+8\)이 아님에 주의하라. \(C\)에 도달하기 이전의 보상은 고려하면 안 된다). Episode 4에서 \(C\)의 값은 \(-11\)이다. 이들을 평균내면 \(+4\)가 된다.

이처럼 Direct Evaluation은 매우 직관적이며 간단하면서도 제대로 된 값을 계산해낸다. 하지만, 상태 간의 연결 관계를 고려하지 않는다. 자신이 얻게 되는 최종적인 보상이 순서를 고려하지 않고 모두 합산되기 때문에 각 상태는 독립적으로 계산되고, 따라서 학습 시간이 오래 걸린다.

Sample Based Policy Evaluation

상기한 것처럼, Direct Evaluation은 간단하고 직관적인 방법이지만 그만큼 비효율적이다. Passive Reinforcement Learning은 결과적으로 Policy Evaluation을 하는 것이기 때문에, 그냥 Policy Evaluation을 수행하면 안될까? 그러지 못하는 이유는 우리가 선택한 방법이 Model Free Learning이고, 따라서 전이함수 \(T\)와 보상함수 \(R\)을 추정하지 않기 때문이다.
그렇다면 이러한 정보를 추정하지 않고 Policy Evaluation을 하는 방법은 없을까? 바로 표집(Sampling)을 하는 것이다. 학습 과정에서 구한 표본(Sample)들로 Policy Evaluation을 하는 것이다.

• \[\mathrm {sample}_i = R(s,\pi(s),s'_i) + \gamma V_{k}^{\pi} (s'_i)\]
• \[V_{k+1}^{\pi} (s) = {1 \over N} \sum\limits_i \mathrm{sample}_i\]

즉, 직접 행동을 통해(Online) 얻은 값을 \(T\)와 \(R\) 대신 사용하는 것이다. 다만, 여기에는 실제로 행동을 수행해야 결과를 얻을 수 있는 Online Learning에서 여러 개의 표본을 어떻게 구할 것인지에 대한 문제가 있다.

Temporal Difference Learning(TD Method)

Temporal Difference는 우리말로 하면 대략 시간차 정도의 뜻으로 이해할 수 있다. Sample Based Learning에서 문제가 되는 부분은 Online Learning에서 어떻게 여러 개의 표본을 확보하냐는 점이었다. 학습 도중 실시간으로 \(V^\pi(s)\)를 업데이트하도록 하면 기댓값을 계속 갱신시켜 나갈 수 있다.

• \[V^\pi(s) \leftarrow (1-\alpha) V^\pi (s) + \alpha \cdot \mathrm{sample}\]
  • 매 단계마다, 새로운 표본을 얻어서 \(\alpha\) 만큼의 비중으로 기존 기댓값에 반영하는 것이다. 당연히 \(\alpha < 1\)이고, 커질수록 기존 값보다는 새로이 얻어진 표본을 중요하게 생각할 것이라는 뜻이다.

위 식을 보면, 기존 값에는 계속 \(1-\alpha\)가 곱해진다는 것을 알 수 있는데, 따라서 초기의 값은 계속해서 그 영향력이 감소하고, 최근에 다시 계산된 값이 큰 의미를 가진다는 것을 알 수 있다. 이를 Expotential Moving Average라 한다.

그러나, TD Method를 위시한 Passive Reinforcement Learning의 문제점은, 방법론 자체가 고정된 정책을 가지면서도 Model Free이기 때문에 새로운 정책을 얻을 수가 없다는 점이다. 계산된 보상의 기댓값을 통해서 새로운 정책을 얻어내려면 Policy Extraction이 필요한데, 전이함수 \(T\)와 보상함수 \(R\)을 모르는 채로는 Policy Extraction을 할 수 없기 때문이다.

Active Reinforcement Learning

Active Reinforcement Learning은 정해진 행동을 하지 않고 에이전트가 행동을 결정한다는 점에서 Passive Reinforcement Learning과는 다르다.

Q-Learning

Q-Learning은 Sample Based Q-Value Iteration이라 할 수 있다. Sample Based Policy Evaluation이 \(T\)와 \(R\)을 추정하는 대신 Online Learning을 통해 얻은 표본을 활용하는 것처럼, Q-Learning도 비슷한 방식을 거치는데, 사실상 TD Method에서 Policy Evaluation 대신 Q-Value Iteration을 한다는 차이점만 있을 뿐이다.

• \[Q(s,a) \leftarrow (1-\alpha) Q(s,a) + \alpha \cdot \mathrm{sample}\]

최적이 아닌 행동을 하는 중에도 Q-Learning을 위한 값들은 최적을 향해 갱신되는데, 이처럼 현재 정책과 목표 정책이 다른 상태로 학습하는 것을 Off-Policy Learning이라 한다.

Exploration

위에서 언급한 것처럼, 강화학습을 위해서는 새로운 행동을 하는 것(Exploration)과 기존에 알던 최선의 행동을 하는 것(Exploitation) 사이의 조절이 필요하다. Exploration은 가지 않았던 지름길을 찾는 과정이고, Exploitation은 기존의 가장 효율적인 길을 계속 이용하는 과정이다. 단순히 계속 최적의 행동만 반복하도록 한다면 Exploitation에 치우치게 되므로 Exploration을 위한 테크닉이 필요하다.

Epsilon Greedy

Epsilon Greedy란, 낮은 확률(\(\epsilon\))로 무작위적으로 행동하고, \(1-\epsilon\)의 확률로 정책대로 행동하는 것을 의미한다. 가끔씩 무작위적으로 행동함으로써, 기존에 가지 않았던 새로운 길을 찾도록 유도할 수 있다.
하지만, Epsilon Greedy의 단점 중 하나는, 학습이 된 상태에서도 \(\epsilon\)의 존재 때문에 계속 이 상태 저 상태를 전전하며 자원을 낭비할 수 있다는 점이다. 이러한 문제를 해결하기 위해 \(\epsilon\)의 값을 시간에 따라 낮추거나, 후술할 Exploration Function을 사용할 수 있다.

Exploration Function

Epsilon Greedy는 매 스텝마다 무작위적 행동의 가능성이 동일하다. 즉 완전 무작위(Uniform Random)하게 작동한다. 하지만, 이미 많이 방문해서 잘 아는 상태를 탐험하는 데에 무작위적으로 움직일 필요는 없다. 안 가본 길을 가볼 때에야 Exploration이 큰 의미를 갖지만, 이미 잘 아는 길은 그냥 최적의 정책(Exploitation)대로 가면 된다.
이러한 점을 고려한 방법이 바로 Exploration Function이다. 유틸리티 \(u\), 해당 상태의 방문 횟수 \(n\), 임의의 양수 \(k\)에 대해, Exploration Function은 \(f(u, n) = u + {k \over n}\)으로 정의할 수 있다. 이 함수의 의미는, 기본적으로는 유틸리티에 기반해 움직이되, 방문 횟수가 적은 상태에 추가적인 보정을 하는 것으로 이해할 수 있다.

Regret

Regret은 쉽게 이야기해 실수를 정량화한 것이라 보면 된다. 학습 과정에서, 우리는 최적인 정책에 맞게 행동했을 때 얻게 되리라고 기대하는 보상과, 실제로 우리가 얻게 되는 보상의 간극을 발견할 수 있다. 기본적으로 이는 Online Learning의 학습 과정 자체도 보상이 매겨지는 실제 행동이기 때문이다.
따라서, Regret을 최소화한다는 것은 단순히 효율적인 정책을 찾는 것을 넘어서서, 효율적인 정책을 효율적으로 찾는 것을 의미한다. 예를 들어 보자. 무작위적으로 탐험해도 우리는 언젠가 최적의 정책을 구할 수 있다(Off-Policy Learning). 그러나, Exploration Function을 도입하고 적절한 Exploration과 Exploitation의 비중을 유지한다면 더 적은 실수로 최적의 정책을 찾을 수 있을 것이다.

Feature Based Representation

지금까지 알아본 것은, 정보가 완전히 주어지지 않은 세계에서의 기계학습을 통한 Online Learning 방법이었다. 결국 우리가 구해야 하는 것은 최적의 정책(Policy) \(\pi^*\)이고, 이를 위해서는 Q-Value를 구해야 하는데, 모든 상태에서 모든 행동의 Q-Value를 구한다는 것은 실질적으로 어렵다. 현실 세계의 문제들은 매우 많은 상태와 선택지들을 가지기 때문이다.
이때, 실질적으로 같거나 유사한 상태들은 하나로 합쳐서 볼 필요가 있다. 아래 그림을 보도록 하자.

위 이미지의 세 상태는 사실상 같다고 봐도 되는 상태들이다. 하지만 엄밀히 말해서, 에이전트의 위치, 음식이나 캡슐의 유무 따위가 조금이라도 바뀌면 다른 상태로 판정된다. 실질적으로 선택에 아무런 영향을 끼치지 못하는 상황에서도 그렇다.

이처럼 유사한 상태들을 하나의 상태로 판정하면 구해야 하는 Q-Value의 양을 줄일 수 있다. 이를 위해서, 상태를 구분하는 데에 모든 요소를 사용하지 않고 특정한 특징(Feature, 피처)들만 추출하여 사용할 수 있다. 팩맨의 예시에서는 팩맨과 유령 사이의 거리, 음식의 개수 등이 특징이 될 수 있을 것이다.

Linear Value Function

피처들을 이용한다면 V-Function이나 Q-Function을 피처들의 선형 결합으로 나타낼 수도 있다. 예를 들어 아래와 같이 말이다.

• \[V(s) = w_1f_1(s) + w_2f_2(s) + ... w_nf_n(s)\]
• \[Q(s, a) = w_1f_1(s, a) + w_2f_2(s, a) + ... w_nf_n(s, a)\]

위 식에서 \(f(s)\)는 피처의 값을 결정하는 피처 함수이고, \(w\)는 학습을 통해 결정되는 피처의 중요도(가중치)이다. 이렇게 상태를 단순화하면 사실상 같은 여러 상태들을 하나로 묶을 수 있지만, 피처를 잘 결정하지 않으면 이질적인 상태들이 하나로 묶이고 정작 비슷한 상태들은 따로 묶이게 되는 일이 나타날 수도 있다.

Approximate Q-Learning

그렇다면 이렇게 피처들의 선형결합으로 표현된 Q-Function은 어떻게 최적화할 수 있을까? 전이 \((s, a, r, s')\)가 일어날 때마다, Q-Function을 갱신해줄 수 있는데, 그 공식은 아래와 같다.

• \[\mathrm{diff} = \left[ r + \gamma \max_{a'}Q(s', a') \right] - Q(s, a)\]
  • 이번 행동으로 얻은 Q-Value와 기존에 계산된 Q-Value의 차를 의미한다.
• \[Q(s, a) \leftarrow Q(s,a) + \alpha \cdot \mathrm{diff}\]
  • 이 식은 실제 Q-Learning을 위한 공식이다.
• \[w_i \leftarrow w_i + \alpha \cdot \mathrm{diff} \cdot f_i(s,a)\]
  • 이 식은 Q-Learning을 근사하기 위해 가중치를 업데이트하는 방법이다.
  • 마지막에 \(f_i\)가 곱해진 이유는 유의미한(켜져 있는) 피처들의 웨이트를 조정하기 위해서다.

회귀(Regresssion)

이러한 선형함수의 근사를 위해서는 첫 시간에 이야기하기도 했던 회귀(Regression)를 활용할 수 있다. 간단한 선형회귀의 예시는 \(\hat y = w_0 + w_1f_1(x)\)이다. 위에서 봤던 Feature Based Representation처럼 피처를 결정하는 함수 \(f\)와 그 가중치 \(w\)로 이루어져 있다.

최소자승법(Least Squres, 최소제곱법)

그렇다면 회귀의 값은 어떻게 최적화할 수 있을까? 바로 최소제곱법을 이용해서이다. 최소제곱법은 잔차(Residual)의 제곱을 최소화하는 방법인데, 이게 무슨 소리일지 한번 생각해보자.

하나의 피처를 가진 선형 회귀에 대해, 우리는 직선을 하나 생각할 수 있을 것이다. 실제 점들은 그 직선 위에 있을 수도 있고, 그렇지 않을 수도 있다. 이때, 그 직선이 바로 모형(Model, 모델)이고, 특정 \(x\)에 대하여 그 직선이 갖는 \(\hat y\)값이 바로 예측(Prediction)이 된다. 실제 \(y\)는 관측값(Observation) 내지는 Ground Truth라고 한다. 이때, 같은 \(x\)에 대해 예측값과 관측값의 차이를 오차(Error) 내지는 잔차(Residual)이라고 한다.
오차가 적을수록 좋은 모델이라고 할 수 있다. 각 \(x\)값에 대해, \(y\)값을 가깝게 예측한다는 뜻이기 때문이다. 하지만 단순히 잔차를 전부 더하는 것으로는 모델의 성능을 계산할 수 없다. 어떤 잔차는 양수겠지만, 어떤 경우 잔차는 음수이기 때문이다. 따라서 이들을 더하면 상쇄되는 부분이 생긴다. 이를 막기 위해서, 잔차들을 제곱한 후 더할 수 있는데, 이 값이 작을수록 정확한 모델이라고 할 수 있다. 이게 바로 최소제곱법이다.

Policy Search

마지막으로, 한 가지 지점을 생각해보자. 우리의 목적은 최적의 정책을 발견하는 것이다. 즉, 일반적으로 어떤 행동을 할지 결정하는 것이 제일 중요하다. 때때로 Feature Based Policy는 이를 잘 해내지만, 정작 Value와 Q-Value는 엉망진창으로 계산할 수도 있다. 즉, 우리의 정책이 Q-Value들의 대소관계는 기가 막히게 맞혔지만, 정작 그 Q-Value들의 실제 값은 전부 틀렸을 수도 있다는 것이다.
이때, 사용할 수 있는 것이 Policy Search이다. Q-Learning 등을 활용하여 적당히 괜찮은 정책을 찾고, 피처를 조정함으로써 파인튜닝을 해나가는 방법이 바로 Policy Search이다. 하지만 일일히 피처를 결정하고, 가중치를 변화시키면서 최적의 정책을 찾는 것은 매우 많은 학습(우리는 여전히 Online Learning 중이다)을 필요로 한다.따라서 항상 최적의 방법을 찾기 위해서는 트레이드오프가 필요하다는 점을 명심해야 한다.

정리

오늘은 상태와 보상에 대한 정보가 완전히 주어지지 않은 상태에서 사용할 수 있는 Online Learning 방법에 대해서 알아보았다.
상태와 보상에 대한 정보를 일일히 추정하면 Model Based, 추정하지 않고 바로 Value나 Q-Value를 구하면 Model Free라고 부른다. Model Free Learning은 미리 정해진 정책대로만 행동하느냐, 모든 행동을 다 해보느냐에 따라 Passive 또는 Active하다고 불렀다.
또한, 실질적으로 모든 상태에 대해 다 Q-Value를 계산할 수는 없으니 비슷한 상태들을 하나로 묶기 위한 Feature Based Representation 방법도 있었다. Feature Based Representation은 선형회귀로 나타낼 수 있고, 최소제곱법을 통해 계산해낼 수 있다.

다음에는 간단한 확률론과 나이브 베이지언에 대해 알아볼 것이다.

• 2024 18
• 2023 143