기타등등

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

11.1 블레이드 & 소울 비무

B&S에는  PvP 즉, 유저들끼리 겨룰 수 있는 비무라는 컨텐츠가 있다.

링 안에서 상대와 일대일 무공 진검승부를 펼치는 컨텐츠이다. 

3분의 제한시간 안에 상대방 체력을 0으로 만들면 이기며, 3분 안에 승부가 나지 않으면 상대방에게 가한 피해 합산이 높은 쪽이 이긴다.

공정한 경쟁을 위해 아이템 효과 사라지고 플레이어의 스탯( 캐릭터 강함의 지표)가 표준화된다.

1. 비무 속 도전과제

(1) 거대한 문제 공간

비무는 시점마다 선택해야 하는 액션의 종류만 3가지 이다.

\(a_{skill}, a_{move}, a_{target}\)

\(a_{skill}\)는 학습한 역사(Destroyer)라는 직업 기준으로 총 44가지 선택지가 있으며 순간마다 처해있는 상태에 따라 사용 가능 스킬이 바뀐다. 평균적으로 10개 정도 선택지가 사용 가능하다.

\(a_{move}\)는 동서남북 + 움직이지 않는 옵션 => 5가지 가능

\(a_{target}\)는 상대방을 바라보거나 진행방향을 바라보는 옵션 2가지를 제공한다.

조합 수를 계산하면 10*5*2 = 100 가지 종류의 액션 선택이 가능하다.

0.1초마다 1번의 결정을 해야 하며 평균게임길이가 90초이므로 900번의 액션을 실행한다.

따라서 경우의 수는 \(100^{900}\)이다.

바둑보다 훨씬 문제공간이 크다는 것을 알 수 있다.

(2) 실시간 게임이 갖는 제약

0.1초 안에 현재 상태 데이터 받고, 정책 네트워크가 액션을 선택하고, 그 액션을 다시 환경에 보내야 한다.

그리고 상대방의 액션을 미리 예측하는 과정도 필요하다.

짧은 시간 안에 처리해야 하므로 처리속도도 중요한 이슈가 된다.

(3) 물고 물리는 스킬관계

1. 상태이상(cc기) : 상대를 상태 이상에 빠뜨리는 스킬

2. 저항: 상대방의 cc기나 데미지 딜링기에 잠시 동안 면역상태 제공

3. 탈출: 상대의 cc기에 맞았다면 탈출기를 이용해 상태 이상을 벗어날 수 있다.

4. 데미지 딜링 : 상대 체력을 빼는 데에 특화된 기술

5. 이동: 단숨에 상대에게 접근하거나 거리를 벌리는 스킬

6. No-op : 아무 액션을 취하지 않음

스킬군에 따라 가위 바위 보 관계 형성하게 된다.

- No-op < 상태 이상기

- 상태 이상기 < 저항기

- 저항기 < No-op

이는 비무에 존재하는 무수히 많은 가위바위보 관계 중 하나일 뿐이며, 비무는 일정 시간내에 계속 이어지는 가위바위보 게임이라고 볼 수도 있다.

(4) 상대방에 관계없이 robust 한 성능 

상대방이 누구든 어떤 성향을 가지든 좋은 결과를 가져오도록 해야 한다.

이를 위해 새로운 self-play 커리큘럼을 도입했다.

11.2 비무에 강화 학습 적용하기

1. MDP만들기

MDP형태로 만들기 위해 우선 이산적인 시간 단위로 쪼갠다.

논문에서는 0.1초를 1틱으로 정했다.

이보다 빠르면 연산 속도가 부족하고 느리면 전체 반응속도가 느리게 된다.

에이전트는 0.1초마다 상태를 인풋으로 받아 액션을 결정하여 환경(게임엔진)에 보낸다.

그에 따라 환경(게임엔진)은 상태 변화를 일으키고 다음 상태를 에이전트에게 전달한다.

(1) 관측치(\(O_t\))

에이전트는 틱마다 환경 안에서 현재 게임 상황에 대한 다양한 정보\(O_t\)를 관측한다.

정확하게 보면 \(O_t\)와 \(S_t\)는 차이가 있다.

\(O_t, O_{t-1}, O_{t-2}, ... O_1\)를 묶어서 상태 \(S_t\)를 정의한다.

보다 "마르코프하게" 상태를 정의하기 위함이다.

\(O_t, O_{t-1}, O_{t-2}, ... O_1\)를 묶어서 상태 \(S_t\)를 정의하는 방법은 RNN 구조의 뉴럴 네트워크를 이용하면 된다. 논문에서는 RNN의 대표적 구조인 LSTM 구조를 사용했다.

LSTM을 이용하면 틱마다 관측치 \(O_t\)를 받아 그 중에 필요한 정보는 다음 틱으로 흘려보내고, 필요하지 않은 정보는 막는 방식으로 업데이트 된다. 그렇게 흘러간 정보와 해당 틱에서의 관측치 \(O_t\)를 바탕으로 뉴럴넷이 상태 \(S_t\)를 만든다.

\(O_t\)에는 플레이어가 관측할 수 있는 모든 정보를 그대로 에이전트에게 제공했다고 보면 된다.

(2) 액션(\(a_t\))

실제 액션공간은 너무나 크며, 모든 액션이 반드시 필요하진 않다.

액션을 \(a_{skill}\)과 \(a_{move,target}\) 2가지 종류로 줄인다.

\(a_{skill}\)에는 44개의 스킬에 더하여 아무 스킬도 사용하지 않는 "no-op"선택지를 하나 추가하여 총 45개 중 하나를 선택하도록 한다.

no-op를 추가한 이유는 스킬을 아껴야 하기 때문이며 사람도 경기 도중 액션의 80% 이상이 no-op일 정도록 중요한 액션이다.

 \(a_{move,target}\)은 앞,뒤,좌,우 이동선택지와 no-move , 상대방과 반대쪽을 바라보고 움직이는 액션 총 6가지 제공한다.

에이전트는 \(a_{skill}\)과 \(a_{move,target}\) 두 종류 액션을 각각 하나씩 선택해서 환경인 게임엔진에 보내고 게임엔진은 그에 맞게 처리하고 상태변화를 일으킨다.

(3) 보상(\(r_t\))

보상 중 가장 먼저 생각할 수 있는 것은 승리여부이다.

하지만 이 보상은 한 게임에 한번 발생하는 희귀한 시그널이다.

최대 1800틱까지 길어지는 에피소드에서 한 번 존재하는 시그널을 이용해 강화하는 것은 어려운 일이다.

따라서 승패 보상을 기본으로 하되, 자주 발생하는 시그널을 더해줘야 한다.

다음과 같이 체력 차이를 이용해 보상을 준다

\(HP_t^{ag}\)는 t시점에 에이전트의 체력이고 \(HP_t^{op}\)는 t 시점에 적의 체력이다.

내 체력이 줄어들면 음의 보상을 받고, 적의 체력이 줄어들면 양의 보상을 받는다.

체력에 대한 보상은 자주 발생한다.

한 번 고려해야 하는 것은 체력에 대한 보상이 안전한 보상인가 하는 점이다.

예를 들어 살펴보자.

성향이 다른 게임 플레이어 A와 B가 있다.

A는 이길 때마다 체력을 조금 남기고 겨우 이기지만 승률이 100%이다.

B는 승률은 85%이지만 이길 때는 자신의 체력이 하나도 안 깍이고 완벽하게 상대를 압도한다.

누가 더 잘 하는 플레이어인가? 일반적으로 A이다.

하지만 체력을 보상으로 준다면 B가 A보다 보상을 더 많이 받을 수도 있다.

따라서 보상의 합을 최대화하는 것과 잘 플레이하는 것 사이에 약간의 미스매치가 발생하게 된다.

본 논문에서는 미스매치 감수하더라도 자주 발생하는 체력 보상을 이용해 학습하는 것이 더 이득이 된다.

Optimality(최적성)과 Frequency(빈도) 사이 트레이드 오프가 있다는 것이다.

제일 정확한 승패 시그널은 최적이지만 발생빈도가 너무 낮고, 자주 등장하는 체력 시그널은 최적은 아니지만 빈도가 높아 학습을 빠르게 한다.

논문에서는 승패보상과 체력보상 이 2가지를 메인으로 사용했다.

(4) 학습 시스템과 알고리즘

MDP의 기본요소에 대한 정의를 마쳤다.

다음은 학습과정에 대해 살펴본다.

학습시스템은 워커(worker)와 러너(learner)로 구성한다.

워커에서 하는 일은 다음과 같다.

각 워커는 중앙 모델DB에서 학습의 대상으로 최신 모델을 뽑고 대전 상대로는 과정 모델 중 하나를 랜덤하게 선택하여 경기를 진행한다. 경기가 끝나면 로그 파일을 중앙 리플레이 버퍼(CH08에서 DQN의 리플레이 버퍼)에 업로드 한다.

대략 100개의 워커가 1주일 동안 동시에 돌아갔으며 대략 2년에 해당하는 플레이 데이터를 확보했다.

(프로게이머와 대전을 위해서는 2주일간 학습했다)

러너는 정책 네트워크를 업데이트하는 역할을 한다.

리플레이 버퍼에서 로그를 가져와 정책 네트워크를 업데이트하며 정해진 주기마다 정책 네트워크의 복사본을 모델DB에 업로드한다.

정책 네트워크 업데이트에 사용된 알고리즘은 ACER(Actor-Critic with Experience Replay)를 사용했다.

해당 알고리즘은 A3C(Asynchronuous Advantage Actor-Critic)의 off-policy 버전 알고리즘이라고 보면 된다.

A3C는 CH09에서 언급했던 액터-크리틱 알고리즘을 여러 쓰레드를 이용해 병렬적으로 업데이트 할 수 있도록 수정한 알고리즘이다.

각각의 액터(혹은 워커)가 비동기적으로 작동하며 그라디언트를 계산하여 중앙에 보내며, 중앙에서는 그라디언트가 올 때마다 모델을 업데이트하여 다시 각각의 액터에 보내주는 방식이다.

A3C는 기본적으로 on-policy 알고리즘이다. 즉 경험을 쌓는 네트워크와 학습을 받고 있는 네트워크가 동일해야 한다는 의미이다.

ACER는 A3C에 importance sampling 기법을 사용하여 경험하는 네트워크가 계산한 그라디언트를 학습하는 네트워크 관점에서 수정하여 올바른 그라디언트를 계산하도록 해준다.

학습대상 네트워크는 크게  2개의 정책 네트워크와 2개의 액션-밸류 네트워크 총 4가지이다.

- 스킬을 결정하는 네트워크 \(\pi_{skill}\),

- 이동과 타깃팅을 결정하는 네트워크 \(\pi_{move,target}\),

- 스킬 액션의 가치를 평가하는 네트워크 \(Q_{skill}\),

- 이동과 타깃의 가치를 평가하는 네트워크 \(Q_{move,target}\)

그리고 위 4개의 네트워크가 모두 하단부를 공유한다.

특정 시점의 관측치 \(o_t\)가 들어오면 몇 개의 히든 레이어를 거쳐 LSTM에 들어간다.

그리고 LSTM에서 나온 아웃풋(상태 \(s_t\))이 4개의 네트워크 공통 인풋으로 들어가 4개의 네트워크의 아웃풋으로 나온다.

정책 네트워크가 2개라는 점을 생각해보자.

\(\pi_{skill}\)과 \(\pi_{move,target}\) 2개의 네트워크를 학습해야 한다.

여러 개의 정책 네트워크를 학습하는 방법은 3가지가 있다.

첫번째, 번갈아가며 업데이트하는 방식이다.

두번째, 두 개의 정책 네트워크가 서로 독립이라고 가정하고 아래 계산식을 적용하는 방법

세번째, 두 종류의 액션 중 하나를 먼저 선택하고 다음에 다른 하나를 선택하는 방식이다.

스킬 액션을 먼저 선택한다면 스킬정책네트워크 \(\pi_{skill}\)을 먼저 실행해서 \(a_{skill}\)를 뽑고 \(a_{skill}\)을 인풋으로 \(a_{move,target}\)을 결정한다.

수식으로 표현하면 아래와 같다.

실제 신경망으로 구현할 때는 신경망 인풋으로 상태 정보와 선택된 액션 \(a_{skill}\)을 함께 제공한다.

논문에서는 간단한 방식인 첫 번째 방식을 선택했다.

(5) 이동 정책 네트워크의 학습

이동 액션은 0.1초 동안 움직임이 적기 때문에 상태 변화에 미치는 영향이 미미하며 그로 인해 학습에 어려움을 겪게 된다.

이 문제를 해결하기 위해 아래와 같은 방법을 적용했다.

이동 액션 10개를 묶어서 하나의 액션으로 생각하는 것이다.

이동 액션을 적용할 때 이동 방향이 정해지면 해당 방향으로 동일 액션을 10번 실행하는 것이다.

이동 학습을 하는데 사용할 수 있는 데이터 양은 줄지만 단일 액션의 효과를 키움으로 학습의 질을 올린다.

(6) 학습 결과

과거의 모델에 대해 승률이 고르게 향상되는 것이 이상적이며 특정 모델에 대한 승률이 적을 경우 해당 모델을 뽑을 비율을 높여서 다른 모델에 비해 더 많이 뽑힐 수 있도록 한다. 상대적으로 승률이 좋은 모델에 대해서는 뽑을 확률을 줄이도록 한다.

11.3 전투 스타일 유도를 통한 새로운 방식의 self-play학습

다양한 스타일의 상대방을 만나 학습을 해야 승률을 높일 수 있다.

1. 보상을 통한 전투 스타일 유도

격투 게임에서 스타일을 가르는 주요 요소는 공격성이다.

공격성을 조절하여 3가지 유형의 에이전트를 만들었다.

공격형, 수비형, 밸런스형 에이전트이다.

공격성을 조절해서 이 3가지 유형의 에이전트를 만들기 위해 보상 조절 방법을 사용했다.

보상은 크게 메인보상과 전투 스타일 보상 2가지로 나눠서 적용했다.

메인보상은 승패보상과 체결에 관한 보상이다. 플레이를 잘 하도록 하기 위해 메인보상을 최대화하도록 학습한다.

추가적으로 전투 스타일 보상은 3가지 측면에서 보상을 조절했다.

첫번째는 체력 측면에서 보상조절이다.

공격적인 에이전트는 자신의 체력을 내주더라도 상대의 체력을 깍는 것이 중요하다. 따라서 상대방 체력 비율을 더 높게 책정한다.

수비적인 에이전트는 상대 체력을 덜 깍더라도 자신의 체력을 보존하는 것이 더 중요하다. 따라서  자신의 체력 비율을 더 높게 책정하는 것이다.

두 번째는 경기 시간에 대한 패널티이다.

공격적 에이전트는 틱마다 상대적으로 커다란 음의 보상을 받는다. 따라서 최대한 빠른 시간안에 종료시키는 것이 유리하다. 이를 위해 상대방에게 계속적으로 공격을 시도하게 될 것이다.

수비적 에이전트는 시간 패널티를 주지 않는다.

세번째는 거리에 대한 패널티이다.

공격적 에이전트는 상대방과의 거리에 비례해서 패널티를 준다.

수비적 에이전트는 거리에 대한 패널티를 주지 않아 상대방에게 다가갈 유인이 없도록 한다.

2. 새로운 self-play 커리큘럼

3가지 스타일의 3개의 러너가 존재하며 각각의 러너는 해당하는 스타일의 고유한 보상을 통해 에이전트를 학습시킨다.

3개의 러너는 각각 사용하는 보상함수만 다를 뿐 학습 알고리즘이나 업데이트 방식은 모두 동일하다.

이와 같이 self-play 도중 상대방의 다양화를 꾀하는 방법론은 강화학습의 성능을 높이기 위해 많이 사용하는 방법론이다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

10.1 알파고

여기서는 2016년 이세돌과 겨루었던 버전에 대한 논문 내용을 쉽게 재구성하여 다룬다.

알파고는 학습단계와 실시간 플래닝 2단계로 나누어 볼 수 있다.

학습단계는 실제 대국을 치르기 전에 다양한 데이터들을 활용해 학습함으로 대국에서 사용할 여러가지 케이스들을 학습하게 되는 단계이다.

실시간 플래닝은 대국 과정에서 학습했던 데이터를 활용하여 실시간으로 다양한 수를 시뮬레이션 해서 다음 수를 결정하는 과정이다.

실시간 플레닝 알고리즘으로  MCTS (Monte Carlo Tree Search)를 사용한다.

이 2단계를 차례로 살펴본다.

(1) 학습단계

학습단계는 MCTS에서 쓰일 재료를 만드는 과정이다.

MCTS 는 4가지 준비물이 필요하다.

- 사람의 기보를 이용해 지도 학습한 정책 \( \pi_{sl}\)

- 롤 아웃 정책 \( \pi_{roll}\)

- 스스로 대국하며 강화 학습한 정책 \( \pi_{rl}\)

- 밸류 네트워크 \( \nu_{rl}\)

1) 지도 학습 정책 \( \pi_{sl}\)

학습은 6단 이상의 바둑 기사 기보 데이터를 활용해 \( \pi_{sl}\) 신경망을 학습시키는 것으로 시작한다.

기보 데이터는 바둑판의 상태와 해당 상태에서 실제 바둑알을 둔 곳의 위치의 쌍으로 이루어지며 3천만 개의 데이터를 사용했다.

 \( \pi_{sl}\) 신경망은 바둑판 상태 정보 s가 인풋으로 들어오면 19*19=361 칸 중에 현재 상태에서 둘 수 있는 칸 들에 대해 돌을 놓을 수 있는 확률을 리턴한다.

예컨대 바둑판 특정상태 s에서 바둑기사가 (16, 14) 위치에 돌을 두었다면 이를 정답으로 보고, 정답과 신경망 예측값 사이의 차이를 손실함수로 정의하여 이를 줄이는 방향으로  \( \pi_{sl}\) 신경망의 파라미터를 업데이트 한다.

이렇게 학습을 한다면 3천만 개의 데이터 안에 있는 평균 전략을 학습할 수 있다.

\( \pi_{sl}\) 신경망은 정답률이 57%를 기록했다.

전문가들의 기보를 이용한 학습의 성능은 그리 좋은 것은 아니다.

이 정책을 잘 보관하여 추후 MCTS에서 활용하게 된다.

2) 롤아웃정책 \( \pi_{roll}\)

\( \pi_{sl}\) 신경망과 유사하게 바둑판의 상태 S를 인풋으로 받아 어디에 둘지 각 액션의 확률 분포를 리턴하며, 기보 데이터를 이용한 지도 학습을 하게 된다.

대신 사용된 신경망은 훨씬 작고 가벼운 네트워크이다.

\( \pi_{roll}\)은 사람 지식을 이용해 만든 수 많은 feature에 대해 선형 결합 레이어가 하나만 존재한다.

따라서 계산속도는 매우 빠르다. 다만 정확도 성능은 24.2%에 불과하다.

3) 강화 학습 정책 \(\pi_{rl}\)

강화학습을 통해 강화되는 정책을 \(\pi_{rl}\)라고 하겠다.

\(\pi_{rl}\)은 \(\pi_{sl}\)과 완벽히 똑같이 생긴 신경망이고 \(\pi_{rl}\) 파라미터들은 \(\pi_{sl}\) 파라미터를 이용해 초기화한다. 따라서 초기에는 \(\pi_{rl}\)는 \(\pi_{sl}\)과 완전히 같은 네트워크이다.

하지만 \(\pi_{rl}\)는 self-play를 통해 계속 강화된다.

self-play는 자신의 과거 모델들을 이용해 풀을 만들고, 풀에서 랜덤하게 하나를 뽑아와서 경기를 펼치는 방식이다.

알파고는 학습을 받고 있는 네트워크가 500번 업데이트 될 때 마다 해당 모델을 풀에 넣어주었다고 한다.

self-play에서 보상함수는 경기를 이기면 1, 지면 -1로 하였고 중간 보상은 없었다.

또한 강화학습시 방법론은 리턴만 있으면 학습할 수 있는 REINFORCE 알고리즘을 사용하였다.

리턴 계산에 사용되는 \(\gamma\)값은 1.0으로 정했다.

즉 한 경기 안의 모든 시점에 대해 같은 값의 리턴을 갖게 된다.

이긴 경기에서 발생한 모든 액션의 확률을 동등하게 증가시키고, 진 경기에서 발생한 모든 액션의 확률은 동등하게 감소시킨다.

128 경기의 데이터를 이용해 1개의 미니 배치를 구성하였다.

미니 배치가 매우 크기 때문에 안정적인 그라디언트 계산이 가능하다.(?)

학습이 끝난 \(\pi_{rl}\)을 \(\pi_{sl}\)과 경기를 붙이면 80% 승률로 \(\pi_{rl}\)이 이겼다.

4) 밸류 네트워크 \(\nu_{rl}\)

\(\nu_{rl}\)의 신경망 구조는 \(\pi_{rl}\), \(\pi_{sl}\) 과 동일하지만 아웃풋이 1개인 스칼라 값이다.

즉, 각 상태 (s)의 가치 밸류를 리턴하는 신경망이다.

\(\nu_{rl}(s)\)는 주어진 상태 s부터 시작해서 \(\pi_{rl}\)을 이용해서 플레이 했을 때 이길지 여부를 예측하는 함수이다.

\(\nu_{rl}\) 학습 시 손실함수는 해당 경기에서의 승패 여부와 승패 여부 예측값인 신경망 아웃풋 사이 MSE로 정의했다.

해당 신경망이 학습된 후 임의의 상태를 인풋으로 넣으면 해당 경기의 승자가 누가 될지 그 결과를 가늠할 수 있게 된다.

이 함수는 MCTS 에서 매우 중요한 역할을 수행한다.

이제까지 4가지 준비물을 살펴보았다.

본격적으로 MCTS를 살펴본다.

(2) MCTS

MCTS 기본개념을 간단히 보면,

"주어진 상황에서 결과를 예측하기 위해 수 많은 시뮬레이션을 머릿속으로 실행해보고 그 중에 결과가 가장 좋았던 액션을 선택하는 방법"이다.

MCTS 방법을 적용하기 위해서는 전제조건이 있다.

첫번째, MDP 모델을 알아야 한다. 즉 상태 전이 확률과 보상함수를 알아야 한다.

바둑의 경우는 규칙을 알고 있으므로 결국 상태전이확률과 보상함수를 알고 있다고 할 수 있다.

그래서 시뮬레이션이 가능한 것이다. 

이처럼 시뮬레이션을 통해 더 나은 정책을 만드는 과정을 플래닝 이라고 한다.

두번째, 게임 중간마다 시간적 틈이 있어야 한다. 플래닝을 진행하기 위해서는 일정 시간이 필요하다.

바둑은 차례가 도래하면 생각할 시간이 주어지는데 이 규칙이 있기 때문에 MCTS를 사용할 수 있는 것이다.

1) 선택

루트 노드에서 출발하여 리프노드 (자식이 없는 노드)까지 가는 과정이며 각 노드에서 다음 노드를 선택할 때 기준은 다음 식을 활용한다.

시뮬레이션이 진행하며 경험이 쌓일 수록 Q의 영향력이 커지고, u의 영향력은 줄어든다.

Q(s,a)는  상태s에서 액션a를 선택한 이후 도달한 리프 노드들의 리턴의 평균을 의미한다.

예를 들어 상태 \(s_{78}\)에서 액션 \(a_{33}\)을 선택하는 경험을 총 100번 했다고 가정하고 , 

각 경험 별로 도달한 리프노드를 \( s_L^1, ..., s_L^{100}\) 이라 한다면 ,

이때 \(Q(s_{78}, a_{33})\)는 다음과 같다.

여기서 밸류V 계산방법은 뒤에서 다시 언급한다.

다음은 u(s,a) 공식을 살펴본다.

P(s,a)는 사전확률(prior probability) 로 시뮬레이션 해보기 전에 각 액션에 대한 확률을 부여한다.

이 경우는 사람 기보를 이용해 학습해두었던 \(\pi_{sl}(a \vert s)\)를 사용하여 정의한다.

$$ P(s,a) = \pi_{sl}(s,a) $$

즉, 사람이라면 두었을 법한 수에 높은 확률을 부여하는 것이다.

N(s,a)는 시뮬레이션 도중 엣지(s,a)를 지나간 횟수이다. N(s,a) = 0에서 시작하여 한 번 지나갈 때 1씩 더해진다.

(실제 N(s,a)값의 업데이트는 백 프로파게이션 단계에서 이루어진다)

시뮬레이션 횟수를 증가시켜 방문횟수가 증가할 수록 N(s,a)값이 증가하므로 분모가 증가하면서 결국 u값은 작아지게 되어 선택에 영향력이 줄어들게 된다.

사전확률에 \(\pi_{rl}\) 대신 \(\pi_{sl}\)를 선택한 이유는 \(\pi_{rl}\)보다 다양한 액션을 시도하는 정책이었기 때문에 \(\pi_{sl}\)로 초기화하면 시뮬레이션 도중 다양한 수를 시도하여 다양한 경험을 쌓을 수 있기 때문이다.

2) 확장

선택단계에서 도달한 리프노드를 실제로 트리에 매달아 주는 과정이다. 또한 이 노드에서 가지치는 엣지들의 다양한 정보를 아래와 같이 초기화 해 준다.

위 3가지 값이 정의 되었기 때문에 새로 추가된 노드에서 실행 가능한 각 액션에 대해서도 Q+u 값을 계산할 수 있으며 이 노드에서 액션을 선택할 수 있게 된다. 따라서 리프 노드가 트리의 정식 노드로 확장한 것이다.

3) 시뮬레이션

확장을 통해 리프노드가 트리의 정식노드가 되었으므로 해당 노드의 가치를 평가해야 한다.

노드의 가치밸류 계산 방법은 2가지가 있다.

첫째 방법은 리프 노드 \( s_L \)부터 시작하여 게임이 끝날 때까지 롤아웃 정책\(\pi_{roll}\)를 이용하여 빠르게 시뮬레이션 해보는것이다.

롤아웃 정책을 이용하여 번갈아 두어 가면서 게임 종료시 이겼으면 +1, 지면-1이 된다. 이 시뮬레이션 결과값을 \(z_L\)로 표기한다.

시뮬레이션은 한번만 진행되며 결과값 \(z_L\)을 해당 노드 \(s_L\)의 밸류로 사용한다.

두번째 방법은 학습과정에서 준비해둔 밸류 네트워크(\(\nu_{rl}(s)\)를 활용하는 것이다.

(\(\nu_{rl}(s)\)는 상태 s부터 정책 \(\pi_{rl}\)로 플레이할 때 누가 이길지 예측해주는 함수이다.

노드 \(s_L\)을 인풋으로 넣으면 시뮬레이션 필요없이 \(\nu_{rl}(s_L)\)값이 계산되며 해당 값이 \(s_L\)노드의 밸류가 된다.

알파고는 위 2가지 방법을 모두 사용하여 평균을 낸 값을 해당 노드의 밸류로 택했다.

4) 백 프로파게이션(Back propagation)

백 프로파게이션은 주어진 상태s에서 액션a 선택시 새롭게 도달한 리프 노드 밸류 값을 이미 계산되어 있는 평균값 Q(s,a)에 업데이트 하는 과정이다.

지나온 모든 엣지에 대해 Q(s,a)값과 N(s,a)값을 아래와 같은 수식으로 업데이트 해 준다.

리프노드의 밸류값이 리프노드로부터 루트 노드로 전파된 것이니 역전파(백 프로파게이션)라고 부른다.

업데이트를 반복 진행하다 보면 Q는 액션의 실제 밸류로 수렴한다.

결국, 선택=>확장=>시뮬레이션=>백프로파게이션 과정을 한 번 진행하면 하나의 노드가 새롭게 추가된다.

수십개의 CPU, GPU를 사용하여 무수히 반복하여 MCTS를 돌렸다고 한다.

MCTS를 종료하고 나서 생성된 트리를 이용하여 루트노드 s 에서 액션을 선택하는 기준은 무엇일까?

위 그림에서 상태 s에서는 액션 a1, a2, a3 3개 중 하나를 선택할 때 알파고에서는 방문횟수 N(s,a)가 가장 큰 액션을 선택했다.

결국, a1 아래로 노드가 가장 많이 매달려 있으므로 a1을 선택하게 된다.

방문횟수가 많다는 것은 MCTS 도중 해당 엣지의 밸류(Q)가 좋았다는 것을 의미한다. Q가 크다는 것은 그 엣지를 지나서 도달했던 리프 노드의 가치가 높았다는 뜻이므로 합리적인 선택이다.

또한 신뢰도가 높다는 것을 의미한다. ( 예를 들면 음식점 평점이 높은 것과 함께 리슈개수가 많아야 신뢰가 간다)

10.2 알파고 제로

알파고 제로는 기보 데이터 없이 강화학습을 가능하게 방법을 고안했다.

(1) 인간을 대신한 MCTS

알파고 제로는 학습때도 MCTS를 사용한다.

학습시에 MCTS를 사용하려면 MCTS 내부를 변경해야 한다.

내부 변경사항은 뒤에 다시 설명하고,

일단 MCTS를 블랙박스로 보고 인풋으로 현재상태 s를 받으면 그에 특화된 정답 정책을 내놓는 아래 그림과 같은 모듈을 생각해본다.

해당 모듈을 이용해 self-play를 진행함으로 기보 데이터를 대채하는 데이터를 얻는다.

위 그림의 s1상태에서 MCTS를 돌리면 각 액션에 대한 확률분포 \(\pi_1(s_1)\)을 얻는다.

얻어진 확률분포를 근거로 샘플링하여 a1 액션을 선택한다.

a1을 실행하여 상태s2를 얻는다.

다시 MCTS를 돌리고 정책을 얻고 그 정책확률을 근거로 샘플링해서 a2를 선택한다.

이 과정을 게임 종료시 까지 반복하면 한 경기의 데이터가 생기며 같은 방식으로 반복하면서 수백만 경기의 데이터를 얻게 된다. 그리고 이 데이터를 이용해 정책 신경망 학습을 하게 된다.

여기서 게임 진행과정에 얻게 되는 데이터는 (\(s_t, \pi_t, z_t\)) 형식이다.

\(s_t\)는 t시점에 상태이며, \(\pi_t\)는 상태 \(s_t\)에서 진행한 MCTS가 알려주는 정답 정책이고, \(z_t\)는 게임결과값이다.

이렇게 쌓인 데이터를 이용해 신경망 \(f_{\theta}\)를 학습한다.

신경망 \(f_\{theta}\)는 정책네트워크와 밸류 네트워크를 한 번에 계산해준다.

CH09의 TD 액터-크리틱에서 사용했던 신경망과 유사하게 아랫단 레이어는 공유하며 윗단에서 갈라져 액션의 확률분포p와 밸류v를 리턴한다.

상태 \(s_t\)를 \(f_{\theta}\)에 인풋으로 넣어서 정책 네트워크 아웃풋 \(p_t\)와 밸류 네트워크 아웃풋 \(\nu_t\)를 계산한다.

정책 네트워크 아웃풋 \(p_t\)는 MCTS가 알려주는 확률분포 \(\pi_t\)와의 차이를 줄이는 방향으로 업데이트한다.

밸류 네트워크 아웃풋 \(\nu_t\)는 경기 결과값인 \(z_t\)와의 차이를 줄이는 방향으로 업데이트한다.

이를 근거로 손실함수를 구성하면 아래와 같다.

\(z_t\)와 \(\nu_t\) 사이는 MSE를 사용하여 손실함수를 구성하며, \(\pi_t\)와 \(p_t\) 사이는 크로스 엔트로피를 사용하여 손실함수를 구성한다.

위 식의 의미는 다음과 같이 풀어볼 수 있다.

MCTS가 알려준 액션 분포 \(\pi_t\)를 따라가도록 정책네트워크를 업데이트하고, MCTS를 이용해 진행한 게임결과(\(z_t\))를 예측하도록 밸류 네트워크를 업데이트 하는 것이다.

(2) 알파고 제로에서의 MCTS

알파고의 MCTS에서는 사전 준비물이 필요했다.

기보 데이터를 이용해 학습한 \(\pi_{sl}\)과 \(\pi_{roll}\), 그리고 강화 학습을 통해 얻은 \(\nu_{rl}\)이 더 이상 존재하지 않는다.

대신 아직 학습하지 않은 신경망 \(f_{\theta}(s) = (p,\nu)\) 가 있다.

이를 이용해 \(\pi_{sl}\) 대신 p를 사용하고 \(\nu_{rl}\) 대신 \(\nu\)를 사용한다.

\(\pi_{roll}\)는 사용하지 않는다.

확장단계와 시뮬레이션단계가 하나로 합쳐졌다.

확장단계에서 리프노드에서 뻗어나가는 액션의 사전확률은 \(\pi_{sl}\) 대신 \(f_{\theta}\)의 아웃풋인 p를 이용하여 초기화한다.

알파고의 MCTS에서는 시뮬레이션 단계에서 \(\pi_{roll}\)을 이용하여 얻은 시뮬레이션 결과와 밸류 함수 아웃풋 \(\nu\)의 평균을 사용했지만 , 알파고 제로에서는 리프노드 \(s_L\)의 밸류 평가시 \(f_{\theta}\)의 아웃풋인 \(\nu\)를 이용한다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

9.1 Policy Gradient

가치기반 에이전트는 결정론적이다. => 모든 상태s 에 대해 각 상태에서 선택하는 액션이 변하지 않는다는 의미이다.

학습이 종료된 후에는 해당 상태에서 Q(s,a)의 값이 가장 높은 액션을 선택하는 그리드 정책을 사용하게 되는데 학습이 종료된 상태에서는 q값이 고정되어 있기 때문에 각 상태에서 선택하는 액션이 변하지 않는 것이다.

이렇게 되면 가위바위보 게임을 한다고 할 때 특정상태에서는 계속 동일한 액션만 선택하게 되므로 상대에게 간파당하여 문제가 될 수 있다.

정책기반 에이전트는 확률적 정책을 취할 수 있다.

정책함수 정의가 아래와 같다.

$$ \pi(s,a) = P[a \vert s] $$

특정상태(s)에서 정책확률 분포에 따라 액션을 선택하게 되므로 유연한 정책을 가질 수 있다.

그리고 만일 액션 공간이 연속적인 경우, 예를 들면, 0에서 1사이 모든 실수값이 액션이 될 수 있는 상황이라면

액션이 무한하기 때문에 일일이 넣어볼 수 없어서 문제가 됩니다.

하지만 정책기반 에이전트는 \( \pi(s) \)가 주어져 있다면 정책함수 결과에 따라 액션을 계산해낼 수 있게 된다.

이번 챕터도 이전 챕터와 동일한 조건에서 뉴럴넷을 이용하여 표현한 정책 네트워크를 강화하는 것이 목적이다.

(1) 목적함수 정하기

정책 네트워크를 아래와 같이 표현한다.

$$ \pi_{\theta}(s,a) $$

여기서 \( \theta \)는 정책 네트워크의 파라미터이다.

파라미터를 미분하여 그라디언트 디센트 방식으로 업데이트 시키기 위해서는 손실함수를 정의해야 한다.

\( \pi_{\theta}(s,a) \)의 손실함수를 구하려면 먼저 정답지가 정의되어야 한다.

정책함수의 정답지를 알기 어려우므로 손실함수를 줄이는 방향이 아니라, 정책 평가 기준을 세워 그 값이 증가하도록 하는 방향으로 그라디언트 업데이트 시킨다.

정책평가함수를 \( J(\theta) \)라고 한다.

\( \theta \)를 입력으로 받아 \(\pi\) 정책을 실행하고 평가하여 점수를 리턴하는 함수이다.

해당 함수 값을 증가시키는 방향으로 그라디언트 어센트를 진행하여 강화학습을 하면 된다.

보상의 합이 큰 정책이 좋은 정책이라고 평가할 수 있다. 

정책 \(\pi\)를 고정시켜도 에피소드 실행시마다 서로 다른 상태를 방문하고 다른 보상을 받는다.

따라서 정책평가시에도 기댓값 개념이 적용된다.

그러므로 정책평가를 아래와 같이 정의 내릴 수 있다.

위 식을 보면 한 에피소드의 모든 상태에서의 누적 보상합의 기댓값이 포함되어 있으며 이것이 결국 가치함수이다.

즉, \(s_0\)의 가치 라고 볼 수 있다.

여기서 시작 상태가 고정되어 있지 않은 일반적인 경우를 고려해보면 즉, 매번 다른 상태에서 출발한다고 보면

시작상태 s의 확률분포 d(s)가 정의되어 있을 때 아래 수식으로 정의를 표현할 수 있다.

이렇게 하면 \(\pi_{\theta}(s,a)\)를 평가할 수 있다.

따라서 \(\theta\)를 수정하여 \(J(\theta)\)를 최대화하는 그라디언트 어센트 방법을 적용하면 된다.

우선 \(J(\theta)\) 의 미분 계산 방법을 접근하기 쉬운 1-Step MDP 부터 살펴본다.

(2) 1-Step MDP

1-Step MDP는 한 스텝만 진행하고 바로 에피소드가 종료하는 MDP이다.

즉, 처음상태 \(s_0\)에서 액션 a를 선택하고 보상 \(R_{s,a}\)를 받고 종료하는 것이다.

또한 처음상태 \(s_0\)는 확률 d(s)를 통해 정해진다고 가정한다.

이런 경우 정책평가함수 \(J(\theta)\)는 다음과 같다.

이 정책평가함수를 미분하면 아래 유도과정을 거쳐 기댓값 연산자를 사용할 수 있게된다.

결국 아래와 같이 기댓값 연산자를 사용하여 표현할 수 있다.

미분과정을 기댓값 연산자를 사용할 수 있다는 것이 증명되었으므로 "샘플 기반 방법론"을 이용해 계산한다.

따라서  정책 \(\pi_{\theta}(s,a)\)로 움직이는 에이전트를 환경에 가져다 놓고, 에피소드를 반복적으로 수행시키면서 

위 값을 모아 평균을 내면 된다.

\(\nabla_{\theta}log\pi_{\theta}(s,a)\)는 신경망 정책네트워크의 그라디언트를 통해 계산될 수 있으며,

\( R_{s,a}\)는 상태s에서 액션a를 선택하고 얻은 보상을 관측하면 된다.

위 공식의 유도과정을 통해 샘플기반 방법론으로 그라디언트 어센트 방법을 적용할 수 있다는 것이 증명됨으로 계산과정이 간단해진 것이다.

(3) 일반적인 MDP에서의 Policy Gradient

앞에서는 1Step-MDP에서의 Policy Grdient 계산법을 보았다. 일반적인 MDP로 확장하면 아래와 같이 식을 표현할 수 있다.

\(R_{s,a}\)가  \(Q_{\pi_{\theta}}(s,a)\)로 바뀌었다.

즉, 일반적 MDP에서는 하나의 에피소드가 여러스텝으로 구성되어 있으므로 해당 스텝에서의 보상만 고려하는 것이 아니라 해당 스텝에서의 누적보상합의 기댓값 (리턴의 기댓값)을 고려해야 하는 것이다.

위 식을 Policy Gradient Theorem 이라고 부른다.

정리하면, \(\pi_{\theta}(s,a)\) 정책을 따르는 에이전트가 반복적인 에피소드 경험을 통해 얻어낸 데이터를 기반으로 목적함수(정책평가함수) \(J(\theta)\)의 그라디언트를 계산하여 최적의 정책을 찾아내는 방법론을 policy gradient라고 한다.

9.2 REINFORCE 알고리즘

REINFORCE 알고리즘은 policy gradient를 이용해 실제로 학습하는 방법 중 가장 기초적이고 기본적인 알고리즘이다.

(1) 이론적 배경

원 수식의 \(Q_{\pi_{\theta}}(s,a)\) 자리에 특정 시점 t의 리턴값 \(G_t\)가 들어갔다.

Q 밸류 정의 식은 아래와 같다.

$$Q_{\pi}(s,a) = E[G_t \vert s_t = s, a_t = a]$$

즉, \(G_t\) 샘플을 여러 개 얻어 평균을 내면 그 값이 Q밸류가 되는 것이다.

이 정의를 고려해볼 때, 위 식의 바깥에 기댓값 연산자가 있기 때문에 괄호 안에 \(G_t\)를 적용해도 큰 차이가 없다는 논리이다.

2번의 A=>B=>C 반복은 더 이상 \(\theta\)의 변화가 없거나 성능의 향상이 없을 때까지 진행하면 된다.

(2) REINFORCE 구현

파이토치의 미분기능을 이용하려면 loss함수의 정의가 있어야 한다.

Policy Gradient 방법에서는 손실함수 대신 목적함수(정책평가함수) \(J(\theta)\)가 최대값을 가질 수 있도록 \(\theta\)를 업데이트 해야 한다.

따라서 구현상에서 필요한 것은 목적함수의 정의이다.

위에서 언급한 REINFORCE 알고리즘 수식은 다음과 같다.

여기서 미분 전의 공식은 미분기호를 제거한 아래의 수식이 된다.

실제로는 파이토치의 옵티마이저를 이용해 그라디언트 디센트 방법을 사용하여 결과적으로 그라디언트 어센트효과가 나오도록 해야 하므로 손실함수 위치에 들어갈 함수는 음의 부호를 추가하여 아래와 같다.

이 공식이 바로 손실함수 대신 정의하게 될 목적함수이다. 

위 공식은 손실함수 위치에 대입될 공식이므로 이후 손실함수 또는 Loss라고 부르도록 한다.

이제부터 구현에 필요한 소스를 살펴본다.

Policy 클래스의 forward를 통해 나오는 결과 아웃풋은 좌측액션 확률과 우측액션 확률 값 2개를 리턴하게 된다.

2개의 확률정보를 근거로 m.sample에서 좌측이동 또는 우측이동 액션을 선택하게 된다.

확률이 큰쪽 액션이 무조건 선택되는 것이 아니다. 확률이 큰쪽의 액션이 뽑힐 확률이 더 높도록 한다는 것이 sample 함수 역할이다.

선택된 액션정보를 환경 env의 step함수에 입력하면 그 결과로 다음상태 정보와 보상, 종료여부 등의 정보를 리턴한다.

여기서 얻어진 보상과 Policy forward를 통해 얻은 확률정보를 에피소드 종료까지 Policy클래스에 저장해둔다.

에피소드 종료 이후 저장해놓은 보상과 확률정보를 히스토리에서 역으로 꺼내면서 미분을 진행하고 모든 미분이 종료한 후 옵티마이저의 step함수를 이용해 \(\theta\)를 업데이트 시킨다.

9.3 액터-크리틱

액터-크리틱은 정책 네트워크와 밸류 네트워크를 함께 학습하는 방법이다.

Q 액터-크리틱(가장 간단한 방법) , 어드벤티지 액터-크리틱, TD 액터-크리틱 3가지 종류가 있다. 

(1) Q 액터-크리틱

Policy Gradient 식은 다음과 같다.

그리고 이 공식을 베이스로 하여 REINFORCE 알고리즘 공식은 아래와 같다.

계산하기 어려운 \( Q_{\pi_{\theta}}(s,a)\) 대신 계산 가능한 \(G_t\)로 변경하였다.

하지만 Q엑터-크리틱에서는 Policy Gradient 공식의 Q를 그대로 사용하여 정책 최적화를 하려고 한다.

실제 \( Q_{\pi_{\theta}}(s,a)\)를 모르기 때문에,

CH08 가치기반 에이전트에서 살펴본 딥Q러닝 방식을 도입해 Q를 계산해낸다.

결국 이 방식을 구현하기 위해서는 ,

1) 정책 네트워크 \(\pi_{\theta}\) 필요 ==>  실행할 액션 a를 선택하는 액터

2) w로 파라미터화 된 밸류 네트워크 \(Q_w\) 필요 ==> 선택된 액션 a의 Q밸류를 평가하는 크리틱 

(2) 어드밴티지 엑터-크리틱

위 공식은 Policy gradient 공식이다.

여기서 \(Q_{\pi_{\theta}}(s,a)\)를 살펴보자. Q밸류가 큰 값을 가지게 되면 또는 변동성이 심해지면 학습 성능이 떨어진다. 그 부분을 방지하기 위해 아래와 같은 방법을 도입한다.

빨간 박스 안에 수식의 의미는 다음과 같다.

\(Q_{\pi_{\theta}}(s,a)\)는 상태 s에서 액션 a를 실행하는 것의 밸류이고, \(V_{\pi_{\theta}}(s)\)는 상태s의 밸류이다.

따라서 \(Q_{\pi_{\theta}}(s,a) - V_{\pi_{\theta}}(s)\)의미는 상태s에 있는 것보다 액션a를 실행함으로 추가로 얼마의 가치를 더 얻게 되는지를 계산한 수식이다.

계산 결과값을 어드밴티지(advantage) \(A_{\pi_{\theta}}(s,a)\)라고 부른다.

이처럼 어드밴티지 A를 사용하여 policy gradient를 계산하면 분산이 줄어들어 훨씬 안정적인 학습이 가능하다.

실제로 어드밴티지를 활용하여 구현하려면 신경망이 모두 3가지가 필요하다.

- 정책함수 \(\pi_{\theta}(s,a)\)의 신경망 \pi

- 액션-가치함수 \(Q_w(s,a)\)의 신경망 w

- 가치함수 \(V_{\phi}(s)\)의 신경망 \(\phi\)

위 3가지 신경망을 모두 학습해야 한다.

밸류 네트워크 \(Q_w, V_{\phi}\)들은 모두 TD방식으로 학습한다.

어드벤티지 액터-크리틱은 Q 액터-크리틱에 비해 그라디언트 추정치의 변동성을 줄여줌으로 학습 효율에 이점이 있다.

(3) TD 액터-크리틱

어드벤티지 액터-크리틱는 구현을 위해서 3개의 신경망을 구성해야 하는 단점이 있다.

신경망의 수를 줄이기 위해 고안한 방법이 TD 액터-크리틱 이다.

\(V_{\phi(s)\) 신경망을 고려해볼 때 손실함수는 아래와 같다.

손실함수를 TD 에러(\(\sigma\))라고 부른다.

상태s 에서 액션a를 선택했을 때 손실함수 기댓값은 아래와 같이 구할 수 있다.

결과적으로 \(\sigma\)의 기댓값이 어드밴티지 A(s,a)이다. 

즉, A(s,a)의 불편추정량이 \(\sigma\)이다.

의미를 풀어서 보면, \(\sigma\)값은 같은 상태s에서 같은 액션a를 선택해도 상태전이가 어떻게 일어나느냐에 따라 매번 다른 값을 얻게 된다. 이 값을 모아서 평균을 내면 그 값이 A(s,a)로 수렴한다는 의미이다.

결국, 어드밴티지 정책네트워크 식을 다음과 같이 변환할 수 있다.

결국 신경망은 Q밸류네트워크가 제외된 정책\(\pi\) 네트워크(C단계) 와 V밸류 네트워크(D단계) 2개로 구성하였다.

대신 정책네트워크 계산(C단계)과 밸류 네트워크 계산(D단계)시 \(\sigma\)가 포함되며 해당 값은 B단계에서 계산식을 통해 계산되어 상수가 된다.

새로운 하이퍼파라미터 n_rollout을 추가했다. 밸류네트워크가 평가를 대신해 주기 때문에 액터-크리틱 기반 방법론은 학습시 리턴을 필요로 하지 않는다. 따라서 리턴을 관측할 때까지 기다릴 필요 없이 하나의 데이터가 생기면 바로 네트워크를 업데이트 할 수 있다. 여기서 한 틱의 데이터 발생시 업데이트 할지, n틱의 데이터 쌓였을 때 모아서 업데이트할지를 나타내는 변수가 n_rollout 이다. 여기 예재에서는 10개 데이터가 쌓였을 때 네트워크를 업데이트 시킨다.

ActorCritic 클래스는 정책함수 pi와 가치함수 v를 가지고 있다.

가치함수는 학습시에 클래스 내부적으로만 사용되므로 메인에서 호출하지는 않는다.

정책함수 pi는 상태s를 인풋으로 받아 정책네트워크를 통해 액션별 선택 확률의 의미를 가지는 값들을 리턴한다.

이 확률 정보를 이용해 Categorical 클래스의 sample함수를 호출함으로 액션을 선택하고 환경 env에 전달함으로 다음스탭으로 이동하면서 다음상태값과 보상을 받는다.

여기서 나온 결과값을 ActorCritic 클래스의 버퍼에 n_rollout 만큼 저장해둔다. (여기서는 10)

n_rollout 만큼 데이터를 적재 후 train_net 함수에서 적재된 데이터를 꺼내어 학습을 진행한다.

ActorCritic 클래스의 pi함수는 정책 네트워크, v함수는 밸류 네트워크에 해당한다.

두 네트워크는 맨 아래 H1 레이어를 공유하도록 구현했다. 따라서 H1은 정책 네트워크 업데이트할 때, 밸류 네트워크 업데이트할 때도 항상 업데이트 된다.

make_batch함수는 텐서들을 리턴하기 전에 데이터를 적재했던 버퍼 data를 초기화하고 있다.

즉 버퍼는 batch size 만큼만 적재해서 학습에 사용하게 된다.

train_net 함수의 loss 변수에는 정책 네트워크의 손실함수와 밸류 네트워크의 손실함수를 더하여 한 번에 업데이트를 진행한다.

정책 네트워크 손실함수 :  -torch.log(pi_a) * delta.detach()

밸류 네트워크 손실함수 :  F.smooth_l1_loss(self.v(s), td_target.detach())

여기서 detach()함수의 용도를 살펴보면,

파이토치의 backward 과정에서 상수로 인식되어 backward 대상에서 제외(detach) 시키도록 하기 위한 용도이다.

(4) Policy gradient 알고리즘 정리

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

이번 장부터는 강화학습과 신경망을 접목시키는 방법에 대해서 설명한다.

* 액션을 정하는 기준에 따라 에이전트를 3종류로 나눌 수 있다.

1. 가치기반 에이전트 - 가치함수에 근거하여 엑션을 선택한다. (정책함수가 따로 없는 경우도 있다.)

 SARSA  나 Q러닝에서 학습했던 에이전트가 가치기반 에이전트들이다.

2. 정책기반 에이전트 - 정책함수 \( \pi (a \vert s) \)를 보고 직접 액션을 선택한다.

가치함수를 따로 두지 않으며 따라서 가치를 평가하지도 않는다.

3. 액터-크리틱 - 가치함수와 정책함수 모두 사용한다.

이번 장에서는 신경망을 이용하여 가치 기반 에이전트를 학습하는 내용을 다룬다.

8.1 밸류 네트워크의 학습

우선, 정책\( \pi \)가 고정되어 있을 때, 신경망을 이용해 \( \nu_{\pi}(s) \)를 학습하는 방법에 대해 살펴본다.

위 그림과 같은 신경망으로 이루어진 가치함수 \( \nu_{\theta}(s) \)가 있다.

이 신경망을 "밸류 네트워크" 라고 부른다.

\( \theta \)는 신경망의 파라미터를 의미하며

신경망에 포함된 파라미터가 100만개라면 \( \theta \)는 길이가 100만인 벡터를 말한다.

손실함수는 아래와 같이 정의된다.

해당 손실함수를 최소화 하는 방향으로 \( \theta \)를 업데이트하도록 학습하면 된다. 여기서 하나 생각해야 할 것이 어떤 S에 대해서 손실함수의 최소화 처리를 할 것인가 ?

현재 규모가 큰 MDP 라는 전제조건이 있으므로 주어진 MDP 상에 존재하는 모든 상태 S에 대해 최소화처리는 쉽지 않다.

그래서 손실함수를 약간 변형하여 정의한다.

기댓값 연산자는 정책함수 \( \pi \)를 이용해 방문했던 상태 s에 대해 손실함수를 계산하라는 의미이다.

이 값은 실제로 계산할 수 있다. 정책 \( \pi \)를 이용해 데이터를 모으고 그 데이터를 이용해 학습하면 된다.

정의된 손실함수 \(L(\theta)\) 를 \( \theta \)에 대해 편미분을 통해 그라디언트를 계산한다.

미분 결과식은 아래와 같다.

위 식은 \( \nu_{true}(s) \)는 현재 모델에 존재하는 실제 상수값이므로 다음 공식을 이용해 유도된다.

수식을 간소화하기 위해 상수2는 생략되었는데 해당 값은 스텝사이즈 역할을 하게 되므로 추후 \( \alpha \)값을 이용해 조절된다.

위의 미분결과식을 실제 계산하기 위해서는 정첵\( \pi \)를 근거로 액션을 취하는 에이전트를 통해 상태 s 샘플을 뽑는다.

충분히 반복해서 실행하면서 아래 우변 수식을 계산하여 평균을 내면 결국 좌변 즉 손실함수의 \( \theta \)에 대한 미분에 근사한 결과를 갖게 된다.

손실함수의 \( \theta \) 에 대한 미분을 계산했다면 그 결과값을 이용해서 \( \theta \)값을 아래의 수식을 이용해 업데이트 한다.

이 과정의 반복을 통해 손실함수가 최소화가 되는 \( \theta \)를 구할 수 있게 된다.

다시 말해, 실제 밸류함수에 근사한 밸류 함수를 구할 수 있게 되는 것이다.

여기서 문제는 \( \nu_{true}(s) \)를 알 수 없다는 것이다. 즉 정답을 모르니 신경망을 통한 학습을 할 수 없게 되는 것이다.

이러한 경우 이전 챕터에서 언급했던 MC 방법의 리턴과 TD 방법의 TD타깃을 활용할 수 있다.

1. 첫번째 대안 : 몬테카를로 리턴

챕터 5 에서 몬테카를로 방식을 이용해  테이블의 t 시점의 밸류값을 업데이트 하는 수식이 아래와 같다.

이 수식에도 정답자리에 \( G_t \)를 사용했는데 이유는 가치함수의 정의가 리턴 \( G_t \)의 기댓값이기 때문이다.

동일한 이유로 손실함수의 \( \nu_{true}(s) \) 대신에 \( G_t \)를 사용할 수 있으며 식은 아래와 같다.

따라서 \( \theta \)업데이트식은 아래와 같다.

충분히 반복적으로 에피소드를 실행해가면서 한 에피소드가 끝날 때마다 모인 샘플상태 s들의 리턴값을 활용해 손실함수의 파라미터 \( \theta \)를 업데이트해 나간다. 

전체적인 강화학습과정은 MC의 특성을 그대로 가지고 있게 된다. 즉 하나의 에피소드가 끝나야 업데이트가 진행되므로 실시간 업데이트는 불가능하며, 리턴의 분산이 크다는 점 등이 특성이다.

2. 두번째 대안 : TD 타깃

앞에서 언급한 \( G_t \) 자리에 TD타깃을 대입하면 된다. 따라서 손실함수는 아래와 같다.

또한 파라미터 업데이트 식은 아래와 같다.

업데이트 식에서 TD타깃 부분은 상수이다. 업데이트할 당시의 \( \theta \)파라미터 값을 이용해 \( \nu_{\theta}(s_{t+1}) \)값이 계산되어지며 상수가 되므로 미분시 0이 되면서 미분 대상에서 제외된다.

8.2 딥 Q러닝

가치기반 에이전트는 명시적 정책 \( \pi \)가 따로 없다.

대신, 액션-가치함수 q(s,a)를 이용해 밸류를 계산하고 각 상태에서 q가 가장 높은 액션을 선택하는 정책을 사용하게 된다.

챕터6의 Q러닝에서 이미 언급한 내용이다. 다만 전제조건이 규모가 큰 MDP라는 것으로 변경되었다. 따라서 테이블 기반 방법론으로 Q값을 저장 및 업데이트 할 수 없으며 신경망을 이용해서 q(s, a)표현한다.

1. 이론적 배경

벨만 최적 방정식과 이를 이용한 테이블 업데이트 수식은 아래와 같다.

업데이트 수식의 빨간 부분을 정답 부분이라고 볼 수 있다.

따라서 손실함수는 아래와 같이 정의된다.

해당 손실함수의 미분을 진행한 후 파라미터 \( \theta \) 업데이트 수식은 아래와 같다.

이 수식을 이용해서 \( \theta \) 파라미터를 계속 업데이트 하면 \( Q_{\theta}(s,a) \)는 점점 최적의 액션-가치함수 \( Q_{*}(s,a)\) 에 가까워질 수 있다.

설명한 손실함수 결과값 최소화 처리과정을 전체 강화학습과정에 함께 넣어 학습절차를 아래 설명한다.

환경에서 실제로 실행할 액션을 선택하는 부분은 3-A, 

TD 타깃 값을 계산하기 위한 액션을 선택하는 부분은 3-C 이다.

( 3-C에서 선택한 액션은 실제로 실행되지 않으며 업데이트를 위한 계산에만 사용된다 => Off-policy 학습 특성 =>

실행할 액션을 선택하는 행동 정책은 \( \epsilon \)- greedy \( Q_{\theta} \)(3-A)단계 이고, 업데이트시 사용되는 정책은 greedy \(Q_{\theta} \) (3-C) 로 서로 다르다 )

파이토치로 구현할 때 기억해야 할 부분이 있다.

3-D 단계는 실제 구현시 손실함수만 정의해주고 손실함수에 대한  minimize 함수를 호출해주면 파이토치 라이브러리가 알아서 그라디언트를 계산하여 \( \theta \) 파라미터를 업데이트 해준다.

2. 익스피리언스 리플레이와 타깃 네트워크

Deep Q러닝을 기본으로 하는 DQN 알고리즘에서 안정적인 학습과 성능을 위해 추가로 사용된 2가지 방법론이 있다. 

2-1 익스피리언스 리플레이

"겪었던 경험을 재사용하면 더 좋지 않을까?" 질문에서 시작된 아이디어이다.

경험은 에피소드를 의미하며 에피소드는 여러 개의 상태전이로 구성된다.

t시점에서의 상태전이는 아래와 같이 표현할 수 있다.

$$ e_t = ( s_t, a_t, r_t, s_{t+1}) $$

해석하자면 "상태 \(s_t\)에서 액션 \(a_t\)를 선택했더니 보상 \(r_t\)를 받고 다음 상태 \(s_{t+1}\)로 이동했다"는 의미이다. 

이렇게 하나의 상태전이를 하나의 데이터로 볼 수 있다.

이런 상태전이 데이터를 최근기준으로 n개를 버퍼에 저장해두고 학습할 때 이 버퍼에서 정한 개수만큼 임의로 상태전이 데이터를 뽑아서 학습에 사용한다는 것이 리플레이 버퍼 개념이다.

이 방법은 상태전이 데이터를 재사용함으로 효율성을 올려주고, 랜덤하게 상태전이 데이터를 추출하면서 데이터 사이 상관성을 줄여주어 결과도 좋게 나온다(?)고 주장 한다

이 방법은 off-policy 알고리즘에만 사용할 수 있다.

리플레이 버퍼에 저장되어 있는 상태전이 데이터들은 과거의 정책에 따라 생성된 데이터이고 그것을 이용해 현재의 타깃정책을 개선하려고 하기 때문이다.

2-2 별도의 타깃 네트워크

Deep Q 러닝에서 손실함수 \(L(\theta)\)의 의미는 정답과 추측 사이의 차이이며, 이 차이를 줄이는 방향으로 \(\theta\)가 업데이트 된다.

자세히 보면, 위그림에서 보듯 Q 러닝의 정답부분은 \( \theta\)에 의존적이다. 학습하면서 신경망을 통해 \(\theta\)가 업데이트 되고 결국 정답에 해당하는 값이 변경된다. 이처럼 신경망 학습과정에서 정답이 변하는 것은 학습 성능을 떨어뜨린다.

이 문제점을 해결하기 위해 타깃 네트워크 방법이 등장했다.

정답을 계산할 때 사용하는 타깃 네트워크와 학습을 받고 있는 Q 네트워크로 구성된다.

그리고 정답을 계산할 때 사용되는 타깃 네트워크의 \(\theta\) 파라미터들을 일정 기간 변경하지 않는다 (얼린다).

 => 얼린 파라미터를 \(\theta_i^{-}\)라고 표기한다.

그 사이 Q네트워크의 \(\theta\)는 계속 업데이트를 진행한다.

일정주기, 예를 들면, Q네트워크에서 1천번 \(\theta\)를 업데이트 시킨 후 타깃네트워크의 \(\theta_i^{-}\)에 현재 시점의 Q네트워크의  \(\theta\)를 업데이트 시킨다.

이 방법을 적용시 성능이 대폭 개선되었음을 확인할 수 있었다.

3. DQN 구현

아래 그림과 같이 카트 위에 막대를 세워놓고 카트를 잘 움직여서 넘어지지 않도록 균형을 잡는 카트폴 문제를 직접 구현해본다.

이 문제에서 카트를 에이전트로 볼 수 있으며 이 경우 에이전트의 액션은 좌로 이동, 우로 이동 2가지로 구성된다.

각 스텝(?) 마다 +1의 보상을 주는 것으로 하여 가능한 오래 균형을 잡으면, 즉 목적에 부합되면 보상이 최대가 되도록 한다.

종료시점은 막대가 수직으로부터 15도 이상 기울어지거나 카트가 화면 끝으로 나가면 종료되는 것으로 한다.

카트 상태 S는 아래와 같은 항목으로 구성된 길이 4인 벡터이다.

S=(카트의 위치정보, 카트의 속도정보, 막대의 각도, 막대의 각속도)

위의 조건 하에 구현을 진행한다.

gym은 OpenAI GYM 라이브러리를 의미한다.

collections 라이브러리의 deque 자료구조에 선입선출 특성을 이용해서 리플레이 버퍼 구현한다.

ReplayBuffer 클래스는 크게 보면 put함수와 sample함수로 구성된다.

put함수는 최신 상태전이 데이터를 버퍼에 넣어주는 함수이며,

sample함수는 버퍼에서 배치크기 (여기서는 32)만큼 데이터를 뽑아서 미니배치를 구성하는 함수이다.

그리고 하나의 데이터는 (s, a, r, s_prime, done_mask)로 구성된다.

done_mask는 현재상태의 종료여부로 종료는 0, 나머지 상태에서는 1의 값을 갖는다.

ReplayBuffer 는 collections.deque 클래스를 이용했기 때문에 버퍼가 꽉 찬 상태에서 데이터가 더 들어오면 자동으로 가장 먼저 들어온 데이터가 버퍼에서 밀려난다.

위에서 구현된 Q네크워크의 구조는 아래 그림과 같다.

질문]

Q 네트워크 결과로 크기 2인 벡터값이 나오도록 구성하였는데 왜 크기가 2인 벡터일까?

밸류가 나와야 하지 않나? 즉, 스칼라값이 나와야 하지 않나?

=> 벡터의 0번째는 좌로이동시 q밸류값, 1번째는 우로이동시 q밸류값을 의미하는 것으로 판단되며 만일 0번째 값이 크다면 좌로 이동하는 액션의 밸류가 큰 것으로 판단하여 좌로 이동 액션을 선택하게 된다. 1번째 값이 크다면 그 반대의 경우로 판단할 수 있을 것이다.

하나의 에피소드가 끝날때마다 train함수가 호출되며 함수 내부에서는 버퍼에서 10개의 미니배치(한개당 32개의 데이터로 구성)를 얻어와서 학습을 진행한다.

train함수내부 설명

(1) s,a,r,s_prime,done_mask=memory.sample(batch_size) =>

소스 초기에 batch_size=32로 셋팅했으므로 결과 행렬들은 32 크기로 묶어서 리턴된다.

예를 들어, 상태 s는 크기가 4인 벡터로 정의했으므로 sample함수를 통해 리턴되는 s는 32 * 4 크기의 행렬로 리턴된다.

(2) q_out = q(s) =>

q(s)는 Qnet.forward함수 호출하여 결과로 구성한 신경망의 Output 을 리턴한다.

앞에서 언급했듯이 구성한 신경망의 결과로 크기가 2인 벡터가 나오게 되므로 미니배치 32 * 4의 input이 들어갔으므로 결과로 나오는 Output은 32 * 2 행렬이 된다.

결과값의 의미는 좌로 이동시(0) / 우로 이동시(1) 액션밸류 q를 의미한다. 

(3) q_a = q_out.gather(1, a) =>

해당 소스를 이해하려면 먼저 gather함수의 동작을 이해해야 한다.

A.gather 함수는 간단히 말하면, A행렬 중에서 복수개의 특정 위치의 값들을 한번에 추출해주는 역할을 한다.

복수개의 특정위치의 값들을 추출하려면 복수개의 특정위치 정보를 gather함수에게 넘겨주어야 하는데 이 부분을 좀 더 설명한다.

예를 들어 설명한다.

A => [[10,11,12],[13,14,15],[16,17,18]]의 (3 * 3 ) 인 2차원 텐서라고 가정하자.

gather함수를 이용해서 텐서의 원소 중 10과 12 , 14와 13, 17과 18값을 추출하고 싶을 때 원소 위치를 지정하는 방법은 아래와 같다.

B => [[0, 2],[1, 0],[1,2]]

이렇게 (2*2) 인 텐서를 구성하고 첫번째 줄의 원소에는 A텐서 첫번째 줄에서 뽑고 싶은 원소 index를 기록한다.

10값이 첫번째 줄의 0번 인덱스에 위치하므로 B텐서의 첫번째 줄에 0을 입력한 것이다.

12값이 첫번째 줄의 2번 인덱스에 위치하므로 B텐서의 첫번째 줄 두번째 요소에 2를 입력한다.

14값은 A텐서 두번째 줄에 1번 인덱스에 존재하므로 B텐서에 두번째 줄에 1을 입력한다.

13값은 A텐서 두번째 줄에 0번 인덱스에 존재하므로 B텐서 두번째 줄의 두번째 요소에 0을 입력한다.

17값은 A텐서 세번째 줄에 1번 인덱스에 존재하므로 B텐서 세번째 줄에 1을 입력한다.

18값은 A텐서 세번째 줄에 2번 인덱스에 존재하므로 B텐서 세번째 줄의 두번째 요소에 2를 입력한다.

C = A.gather(1, B)

gather 함수 첫번째 매개변수는 A텐서의 차원 중 몇차원의 값을 추출할 것인지를 지정하는 것이다.

여기서는 A텐서가 2차원인 상황이며, gather 첫번째 매개변수가 1이므로 A텐서 2차원 원소들 추출할 것을 지정하는 것이다.

gather함수는 실행결과로 B텐서에 기록된 위치정보를 이용해 A텐서에서 해당 위치의 원소 값들을 모아서 새로운 텐서로 리턴하게 된다.

결과 텐서 C는 

C =>[[10, 12],[14, 13],[17, 18]]

epsilon-greedy 정책에 의해 선택되어진 액션정보를 담고 있는 행렬 a (32 * 1) 를 gather함수의 두번째 인자로 전달한다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

이제부터 상태가 무수히 많은 규모가 큰 MDP를 푸는 법에 대해 논의한다.

7.1 함수를 활용한 근사

상태가 많아지면 테이블의 사이즈가 기하급수적으로 커지므로 테이블 기반 방법론을 사용할 수 없게 된다.

새로운 접근법이 필요하다.

예를 들면, 상태값을 입력시켜 결과값으로 가치값을 리턴하는 함수를 구할 수 있다면, 

상태값과 가치값을 저장하는 테이블 방식보다 함수 정보만 가지고 있으면 되므로 메모리 사용이나 시간상 많은 이점이 있을 것이다.

하지만, 정확하게 실제 가치값을 도출해 내는 함수를 구하기는 어려우므로  근사함수를 구해서 사용할 수 있다.

실제 값에 가장 가깝게 근사하도록 함수 파라미터를 구하는 법으로 주로 "최소 제곱법"을 사용합니다.

1. 함수 복잡도에 따른 차이

함수의 차수가 높을 수록 아래 그림과 같이 실제 결과값과 거의 일치하게 근사시킬 수 있다.

하지만 실제 데이터에는 노이즈가 섞여 있으므로 실제 데이터값에 정확하게 피팅하면 오히려 구하고자 하는 평균치 데이터(가치밸류)와는 멀어질 수도 있게 된다. 즉, 높은 차수의 다항함수를 사용하는 것이 무조건 정확하다고 볼 수는 없다.

2. 오버피팅과 언더피팅

오버피팅 :  근사함수를 정할 때 , 너무 유연한 함수를 사용하여 노이즈까지 피팅해 버리는 현상

언더피팅 : 실제 모델을 담기에 함수의 유연성이 부족하여 주어진 데이터와의 에러가 큰 상황

위 그림에서 빨간선은 근사함수이며 녹색선이 실제 모델 함수이다.

좌측그림은 언더피팅, 우측그림은 오버피팅을 나타낸다.

3. 함수의 장점 - 일반화

이미 경험한 데이터들을 바탕으로 실제 모델 함수에 근사한 함수를 잘 구성한다면 경험하지 않은 데이터를 근사함수에 입력하였을 때 실제 데이터와 오차가 적은 결과값을 리턴하게 될 것이다. 이런 함수의 특징을 일반화라고 한다.

이 특징때문에 잘 근사된 함수를 사용하게 되면 데이터를 저장하기 위한 공간을 대폭 줄일 수 있게 된다.

7.2 인공 신경망의 도입

1. 신경망

신경망의 본질은 매우 유연한 함수이다. 함수에 포함된 프리 파라미터의 개수를 통해 함수의 유연성을 제어한다.

(근래 커다란 신경망의 프리 파라미터가 1000억개를 넘어가기도 한다)

이러한  특징을 가지고 있는 신경망을 이용해서 상태별 가치값을 계산되도록 하려는 것이 Deep RL 학습의 중심 아이디어이다.

위 그림은 길이 3인 벡터를 인풋으로 받아 2층으로 쌓여있는 히든레이어를 통과시켜 결과값 하나를 도출해내는 신경망을 나타낸다.

함수로 표현하면 y = f(\(x_1, x_2, x_3\)) 형태이다.

히든레이어들은 노드로 구성되어 있으므로 신경망의 최소단위를 노드라고 할 수 있다. 따라서 노드를 이해하면 신경망 이해에 도움이 된다.

위그림은 하나의 노드만 떼어내어 표현한 것이다.

(1) 인풋 (\(x_1, x_2, x_3\))을 \(w_1x_1 + w_2x_2+w_3x_3 + b\)의 형태로 선형결합시킨다.

(2) g(x)라는 비선형 함수를 적용한다. (예를 들면, RELU함수 => g(x) = max(0, x))

여기서 선형결합의 의미는 인풋값들을 조합하여 새로운 피처(특징값)를 만드는 과정이다.

또한 비선형함수 적용은 인풋과 아웃풋의 관계가 비선형일 수 있기에 필요한 과정이다.

2. 신경망의 학습 - 그라디언트 디센트

제공된 데이터를 근거로 신경망 함수의 w 파라미터를 구하는 방법으로 그라디언트 디센트 방법을 사용한다.

실제 모델의 함수를 F(x)라 하고 근사함수를 f(x)라 하면 두 함수의 차이를  줄이는 것이 최종 신경망 학습의 목표이다.

이를 위해 아래와 같은 두 함수의 차의 제곱을 함수로 구성할 수 있다. 

$$ L(w) = \{ F - f \}^2 $$

여기서 L(w)을 손실함수(loss function)라고 한다.

이 손실함수값을 최소화하는 것이 결국 신경망의 목표가 되는 것이다.

해당 신경망 모델에 100개의 w 파라미터가 존재한다고 가정할 때, 

파라미터 별로 편미분을 통해 해당 파라미터 항이 함수 전체에 미치는 영향을 파악한다.

위 식은 함수의 각 파라미터에 대해 편미분하여 벡터를 만든 것이고, 이를 그라디언트 라고 한다.

계산된 그라디언트를 이용해 손실함수를 최소화 하는 방향으로 아래 수식처럼 파라미터를 조금씩 업데이트 해 나간다.

이런 과정을 그라디언트 디센트(경사하강법) 방법이라고 한다.

여기서 편미분결과를 반영하는 비율 \( \alpha \)를 러닝레이트 또는 스텝사이즈라고 한다.

보통 러닝레이트 값은 1보다 작은 값으로 셋팅합니다.

그라디언트 디센트 방법을 반복하면서 파라미터값을 업데이트 시켜가면 결국 손실함수가 최소가 되는 방향으로 파라미터들이 조정되는 것이고 결국 실제 데이터 모델에 근사한 함수를 구성할 수 있게 되는 것이다.

3. 간단한 확인

간단한 함수로 예를 들어 위의 과정을 살펴보겠다.

아래와 같은 근사 함수 \( f_w \)가 있다.

초기 w파라미터는 랜덤하게 셋팅한다.

\( w_1 = 0.5, w_2 = 1.2 \) 라고 하자.

그리고 학습을 위해 주어진 경험치 데이터는 \( (x_1, x_2, y) = (1, 2, 1) \) 이다.

즉, 

$$ f_w(1,2) = 1 $$

만족하도록 w를 조정하는 것이 목표이다.

현재 상황에서 손실함수 L(w)는 아래와 같이 정의된다.

각 파라미터별로 편미분하면 아래와 같다.

구해진 그라디언트 벡터를 이용해 w 파라미터를 업데이트 한다(이때, 런닝레이트 \( \alpha \) = 0.01)

업데이트 된 w 파라미터를 이용해 \( f_w^{'}(1,2) \) 값을 계산했을 때 아래 결과에서 보듯이 w 파라미터 업데이트 전보다 실제결과값 1에 가까워졌다.

위 과정을 계속 반복하여 w파라미터를 업데이트함으로 실제 결과값에 점차로 가까워게 되며 결국 실제모델에 가까운 신경망함수를 얻게 되는 것이다. (이때 주의할 사항은 오버피트 이다)

4. 파이토치를 이용한 신경망 구현

간단한 실제 모델을 주고, 신경망 학습을 통해 근사함수를 구하는 과정을 파이토치를 활용해 구현해본다.

실제모델은 아래와 같다.

위 식에서 노이즈 U(-0.2, 0.2)는 -0.2에서 0.2 사이값을 실제값에 균등분포 시킨다는 것을 의미한다.

또한, 신경망의 모델은 아래와 같다.

인풋과 아웃풋은 각각 스칼라값 하나이고, 총 3개의 히든 레이어를 갖고 있으며 각 레이어에는 128개의 노드가 포함되어 있다. 또한 각 레이어에는 활성홤수 ReLU가 포함되어 있다.

이제부터, 위의 모델을 파이토치로 구현한다.

forward 함수에서 레이어별로 활성함수 ReLU 를 적용하고 있다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

본 챕터를 진행하기 전에 2가지 전제조건을 다시한번 언급하면,

1. 작은 모델(상태집합과 액션집합이 작다)

2. MDP를 모른다 (보상함수와 전이확률분포를 모른다)

이런 조건 하에서 그리드 월드 환경에서 최고의 정책을 찾는 방법을 3가지 소개한다.

1) 몬테카를로 컨트롤,

2) SARSA

3) Q 러닝

1. 몬테카를로 컨트롤

CH04 에서 언급한  MDP를 알 때 최적 정책함수 구하는 방법 중 정책이터레이션 방법이 있다.

위 그림이 정책 이터레이션 방법을 구조화 시킨 것이다.

하지만, 모델 프리 상황에서는 정책이터레이션을 그대로 사용할 수 없다.

이유는 2가지이다.

첫번째, 보상과 전이확률을 모르기 때문에 정책평가단에서 반복적 정책평가를 사용할 수 없다.

벨만 기대 방정식 2단계 공식을 보면 아래와 같다.

위 식을 통해 상태별로 반복적 정책 평가가 이루어지는데 공식 중에

보상 \( r_s^a \)와 전이확률 \( P_{ss^{'}}^{a}\)을 모르기 때문에 계산을 할 수 없게 된다.

두번째, 만일 첫번째 문제를 해결해서 각 상태의 밸류를 알고 있는 상태라고 가정할 때,

전이확률 \( P_{ss^{'}}^{a}\)을 모르기 때문에 그리드 정책을 수행할 수 없다.

즉, 다음상태의 리턴 기댓값이 큰 상태로 이동하는 정책을 수립해야 하는데 각 액션이 정해진 상태에서 다음상태로 이동을 예측할 수 없기 때문에 밸류를 계산할 수 없어서 그리디 정책을 수립할 수 없다.
따라서 모델 프리 상황에서 정책 이터레이션을 적용하려면 몇 가지 변형을 주어야 한다.

변형 1 : 
반복적 정책평가 방법에 앞에서 언급했던 MC를 적용하는 것이다.
MC는 MDP를 모를 때 밸류를 계산하는 방법이므로 적용가능하다.

변형 2:
정책개선단계에서 \( \nu(s) \) 대신 액션가치함수 q(s, a)를 이용한다.

q(s,a)를 알게 되면 MDP정보를 몰라도 q(s,a)가 큰 액션을 선택해 나가는 그리디 액션을 선택할 수 있다.

위 2가지 내용을 종합하면,

몬테카를로 방법을 이용하여 q(s,a)를 계산하고 평가된 q(s,a)를 이용해 새로운 그리디정책을 만들고, 이 정책에 대해 다시 MC를 이용하여 q(s,a)를 계산하는 일련의 과정을 반복하는 방법으로 MDP를 몰라도 최적의 정책을 찾을 수 있다.

마지막으로 여기에 추가되어야 하는 것이 있다.

에이전트가 최적의 정책을 찾으려면 MDP 상에 많은 상태를 충분히 탐색해야 한다.

만일 학습과정에서 도달해보지 못한 상태가 있는데 그 상태가 가장 좋은 상태인 경우 최적의 정책을 못찾게 되는 것이다.

하지만, 모든 액션을 완전히 랜덤하게 선택하면 모든 상태를 방문할 확률은 높지만 최적의 정책을 찾지는 못 할 것이다.

따라서 랜덤의 정도를 정해주는 \( \epsilon \) - greedy 방법론을 적용한다.

변형 3: greedy  대신 decaying \( \epsilon \) - greedy 방법론 적용

위 수식에서 \( \epsilon \) = 0.1 이라면, 

90%  확률로 q(s,a)값이 가장 높은 액션 a를 선택하고, 나머지 10% 확률로 랜덤하게 액션을 선택한다.

이 내용을 활용하여 학습을 진행할 수록 랜덤확률을 줄이고 파악된 정보를 이용해 최적의 정책을 찾아갈 수 있도록 \( \epsilon \)값을 줄여나가는 방법을 추천한다.

decaying \( \epsilon \)-greedy 방법론:

초기 학습과정에는 수집된 정보가 많지 않기 때문에 \( \epsilon \)값을 높게 주어 많은 상태를 접할 수 있도록 하며, 점차로 \( \epsilon \)값을 낮추어 학습에서 얻은 정보를 활용하여 최적의 액션을 선택할 수 있도록 유도한다.

또한 학습과정에 성능이슈를 줄이기 위해 정책평가단계에서 가치테이블에 값들을 한번만 계산하고 정책개선 단계로 넘어가도록 한다. (간소화된 정책 이터레이션)

2. TD 컨트롤 1 (SARSR)

정책평가 단계에서 MC 대신 TD를 사용하는 정책 이터레이션 방법이다.

위 그림은 TD컨트롤을 SARSA 라고 부르는 이유를 설명하고 있다.

SARSA는 정책평가 단계에서 MC대신 TD를 사용하여 평가를 진행한다.

각 상테에서 다음 상태로 이동해가면서 액션가치함수 q를 업데이트 시키게 된다.

이때 업데이트 식은 아래와 같다.

여기서 빨간색 부분인 \( R + \gamma Q(S^{'}, A^{'}) \) 을 TD타깃으로 볼 수 있다.

결국 이 부분을 스텝별로 계산해가면서 업데이트 하게 되면  정책개선 단계에서 활용하여 더 좋은 정책을 선별할 수 있게 된다.

3. TD 컨트롤 2 (Q러닝)

Q러닝 설명 전에 타깃정책과 행동정책, Off-Policy 와 On-Policy 개념을 설명한다.

타깃정책 : 강화하고자 하는 목표가 되는 정책이다. 학습의 대상이 되는 정책이며 업데이트 됨에 따라 점점 강화되는 정책이다.

행동정책 : 실제로 환경과 상호 작용하며 경험을 쌓고 있는 정책을 의미한다.

On-Policy : 타깃정책과 행동정책이 일치하는 경우를 의미(현재까지 논의되었던 모든 상황)

Off-Policy : 타깃정책과 행동정책이 일치하지 않는 경우를 의미 (간접경험을 통해 실력을 향상시키는 방법- 예를 들면, 게임을 하고 있는 친구의 행동을 관찰하면서 실력을 향상시키는 상황)

3.1 Off-Policy 학습의 장점

(1) 과거의 경험을 재사용할 수 있다.

일반적인 On-Policy 방법론에서는 타킷정책과 행동정책이 일치해야 한다.

SARSA 를 사용한다고 가정할 때 에이전트의 초기 정책 \( \pi_0 \)를 이용하여 하나의 에피소드를 진행해나가며 행동가치함수 q를 업데이트하고 이를 활용해 정책을 \( \pi_1 \)로 수정한다. 새로 수립된 정책을 가지고 다시 처음부터 경험을 쌓아 가야 한다. 

여기서 새로 수립된 정책 \( \pi_1 \)정책이 타깃정책이며 실제 행동을 취했던 정책이 \( \pi_0 \)정책인데 On-Policy정책에서는 타깃정책과 행동정책이 일치해야 하므로 \( \pi_1 \)정책을 강화하기 위해서는 \( \pi_1 \)정책을 사용하여 액션을 통해 경험을 쌓아가야 한다.

하지만 Off-Policy 방법론은 타깃정책과 행동정책이 다르므로 \( \pi_1 \)정책을 강화하기 위해 \( \pi_0 \)정책을 근거로 액션을 선택하며 경험을 쌓은 정보를 재활용할 수 있다.

(2) 전문가들의 정책을 액션정책으로 활용할 수 있다.

보통은 랜덤정책으로 초기화하고 학습을 진행하면서 조금씩 유의미한 학습이 이루어지도록 하게된다. 따라서 초기에 유의미한 학습이 이루어지기까지 상당한 양의 학습이 필요하게 된다.

만일 초기에 전문가들의 정책을 적용하여 학습을 시작하게 되면 학습속도를 높일 수 있게 된다.

(3) 일대다, 다대일 학습이 가능하다

동시에 여러 개의 정책을 학습키는 경우, Off-Policy 학습을 이용하면 1개의 정책만 경험을 쌓게 하고, 그 결과 데이터를 이용해 동시에 여러 개의 정책을 학습시킬 수 있다.

반대로 동시에 여러 개의 정책이 각각의 경험을 통해 얻은 데이터를 모아서 1개의 정책을 업데이트 할 수도 있다.

3.2 Q러닝의 이론적 배경 - 벨만 최적 방정식

위 식은 \( q_{*}(s,a) \)의 정의를 식으로 표현한 것으로 상태집합 S와 행동집합A가 주어진 MDP 상황에서 존재하는 모든 정책 중에 가장 좋은 정책을 따를 때의 가치함수를 의미한다.

또한, \( q_{*} \)를 알게 되면 상태마다 \( q_{*} \)의 값이 가장 높은 액션을 선택하면 그것이 가장 좋은 정책, 최적 정책이 된다.

수식으로 표현하면 아래와 같다.

결국 최적정책을 찾기 위해서 최적의 액션가치함수 \( q_{*} \) 를 찾으면 된다.

이제 \( q_{*} \) 를 찾는 방법을 설명한다.

기본이 되는 수식은 아래의 벨만 최적 방정식 0단계이다.

이 식을 근거로 Q러닝의 업데이트 식은 아래와 같다.

앞에서 언급한 SARSA 의 업데이트식과 비교해보면 아래와 같다.

빨간색 글자 부분이 Q러닝과 SARSA  업데이트식의 차이부분이다.

위 식에서 알 수 있듯이 밸류 업데이트 수식은 비슷하지만 아래의 표에서 보는 것처럼 SARSA는 On-policy방식이고, Q러닝은 Off-Policy방식이다.

SARSA와 Q러닝이 다른 이유는 기초가 되는 수식이 다르기 때문이다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

보상과 전이확률을 모르는 상황을 모델프리( Model - free) 라고 부른다.

모델 프리 상황에서 정책 \( \pi \)가 주어졌을 때 밸류 평가 방법 즉, Prediction 문제를 푸는 2가지 방법

몬테카를로와 Temporal difference 를 소개한다.

작은 모델 MDP에 대해 다루기 때문에 이전 챕터에서 사용했던 테이블 룩업 방법론을 적용하여 문제를 풀어간다.

1. 몬테카를로 학습

몬테카를로 방법론 - 직접 측정하기 어려운 통계량을 구하고자 할 때 여러 번 샘플링하여 그 값을 가늠하는 기법

위 공식은 상태가치함수의 정의이다.

공식을 풀이해보면 정책 \( \pi \)가 주어진 상황에서 t 시점의 상태 \( s_t \)의 밸류는 t 시점의 리턴의 기댓값이다.

리턴을 얻어내기 위해 직접 에피소드를 종료시점까지 실행하여 리턴값을 얻어내고 이 과정을 반복하여 얻어낸 리턴의  평균을 냄으로 리턴 기댓값을 계산해 내는 것이 몬테카를로 학습의 중요 개념이다.

바둑게임을 예시로 들어보면,

임의의 시점에 바둑판의 상황을 캡쳐해놓고 이 상황이 얼마나 좋은 상황인지 밸류를 평가하려면 실제로 그 상황에서 부터 게임 종료까지 진행해보고 승패 여부에 맞게 보상을 주고 이 과정을 수만 번 반복함으로 리턴 기댓값을 계산해 냄으로 캡쳐한 상황의 밸류를 평가할 수 있다.

 1.1 몬테카를로 학습 알고리즘

보상과 전이확률을 모르는 그리드 월드를 이용하여 몬테카를로 학습 알고리즘을 살펴본다.

실제로 보상은 -1, 전이확률은 100% 라고 정해놓고 그 내용을 에이전트가 모르는 상태에서 몬테카를로 학습을 진행한다고 가정한다.

(1) 테이블 초기화

위 그림의 오른쪽 테이블에서 보이는 것처럼 각 상태별로 N(s)와 V(s) 2개의 값이 필요한데

N(s)는 학습하는 동안 해당 상태를 방문한 횟수 이며,

V(s)는 해당 상태 방문시 마다 얻게된 리턴 누적 합을 의미한다.

초기에는 각 상태별로 2값을 모두 0으로 셋팅한다.

(2) 경험쌓기

에이전트는 주어진 \( \pi \) 정책하에 \( s_0 \) 상태부터 시작하여 종료상태까지 액션과 그에 따른 보상을 받으면서 에피소드를 진행해 나간다. 이를 기호로 표기하면 아래와 같다.

이렇게 하나의 에피소드가 종료되면 각 상태에 대한 리턴은 아래와 같이 계산할 수 있다.

감마 \( \gamma \)와 보상은 실행해 나가면서 에이전트가 알게된 숫자값이다. 결국 각 상태별 리턴은 숫자값이 되는 것이다.

(3) 테이블 업데이트

위 그림의 경로로 하나의 에피소드가 끝난 후 (2)에서 제시한 수식으로 상태별 리턴값을 계산하여

상태별 N(s)와 V(s)값을 업데이트 한다. (위 그림 우측테이블)

(4) 상태 밸류 계산

  경험쌓기와 테이블 업데이트를 충분히 반복한 후 각 상태별로 리턴(V(s))의 평균값을 계산하면 그 값이 상태 밸류가 된다.

(5) 조금씩 업데이트하는 버전

   (4)번 까지의 방법은 에피소드를 충분히 반복한 이후 (예를 들면, 10만번 반복 실행) 밸류를 계산할 수 있었다.

이번 방법은 하나의 에피소드가 끝날때마다 밸류를 조금씩 업데이트 시켜주는 방법이다.

방법은 아래 공식과 같이 \( \alpha \) 라는 개념을 추가하여 기존 값에 새로 계산된 리턴값을 얼마의 비율로 섞어줄지를 지정할 수 있도록 한 것이다.

이렇게 되면 N(s)를 저장해 둘 필요가 없다.

위 공식을 조금 변형하면 아래 식이 된다. 이후에 몬테카를로 학습에서는 아래의 식을 사용한다.

2. Temporal Difference 학습

MC 학습(몬테카를로 학습)은 최소한 하나의 에피소드가 끝나야 밸류를 업데이트할 수 있는 구조이다.

하지만 실제 세계에서는 종료 조건이 명확하지 않은 MDP도 많다.

이처럼 종료하지 않는 MDP 에서 밸류를 구할 수 있는 방법이 Temporal Difference 학습방법이다.

Temporal Difference의 기본 개념은 아래와 같다.

"추측을 추측으로 업데이트 하자!!"

한 스텝이 지나고, 조금이라도 시간이 흐르면 좀 더 정확한 추측을 할 수 있게 되는 것이고 이를 이용하여 이전 스텝의 밸류를 업데이트 활용하는 방식이다.

2.1 이론적 배경

위 공식은 벨만 기대 방정식 0단계 수식이다.

위 공식을 풀이해보면,

\( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \)을 여러 번 뽑아서 평균을 내면 그 평균은 \( \nu_{\pi} (s_t) \)에 수렴한다는 의미이고, 

\( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \)을 풀이해보면, 

\( s_t \) 상태에서 받게 되는 보상 \( r_{t+1} \)과 다음 상태( \( s_{t+1} \)의 밸류를 합한 값을 의미한다.

여기서 \( \nu_{\pi}(s_{t+1}) \) 값이 다음 스텝으로 이동 시 상태밸류 값이고 이것은 사실 에피소드가 끝나기 전 까지는 예상치라고 볼 수 있을 것이다.

이전에도 언급했듯이 , 반복적으로 수행하다 보면 위 예상치에 보상을 더하기 때문에 점차 실제 상태밸류에 수렴해간다

여기서 \( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \) 값을 "TD 타깃" 이라고 부른다.

MC학습에서는 각 상태별 리턴을 여러 개 모아 평균을 내어 밸류를 측정했듯이,

TD에서는 TD타깃 \( r_{t+1} + \gamma \nu_{\pi}(s_{t+1}) \)을 여러 개 모아 평균을 내어 밸류를 측정한다.

2.2 TD 학습 알고리즘

MC 학습과 동일한 조건에서 TD학습 알고리즘을 설명한다.

 (1) 초기화

에이전트를 \( s_0 \) 상태부터 경험을 쌓게 한다.

하나의 에피소드 경로는 아래와 같다

이런 상태에서 TD학습이 MC학습과 차이나는 부분은 2가지이다.

1) 다음 스텝으로 이동한 직후 이전 스텝의 밸류를 아래 수식으로 업데이트 해준다.

이전의 MC 학습 시 공식과 비교하면, 

2) MC학습에서 리턴값을 이용했던 위치에 TD타깃이 대입되었다고 보면 된다.

위 방법으로 하나의 에피소드에 수식을 적용해보면 

위 과정을 에피소드를 반복적으로 수행하면서 진행해나가면 테이블에 상태밸류값은 수렴하게 된다.

3. MC (몬테카를로) & TD 비교

3.1 학습시점 측면

MC는 Episodic MDP (종료가 있는 MDP) 에서만 적용할 수 있다.

TD는 Episodic MDP 와 Non-Episodic MDP (종료가 없는 MDP) 에서도 적용할 수 있다.

따라서  모든 종류의 MDP에서 적용이 가능하다는 측면에서 TD가 좀 더 낳은 방법이다.

3.2 편향성(Bias) 측면

위 공식은 MC의 근간이 되는 수식과 TD의 근간이 되는 수식이다.

MC의 밸류는 리턴들을 여러 개 모아 평균을 내는 방법론으로 샘플이 모일 수록 실제밸류에 반드시 수렴하게 된다.

즉, 편향되지 않는 안전한 방법이다.

TD는 현재의 밸류 추측치를 다음 스텝의 밸류 추측치로 업데이트 해주는 방법이다.

위 벨만 기대 방정식 공식에서 사용되는 것은 \( \nu_{\pi} (s_{t+1}) \) 이지만 실제 사용되는 값은 V(\(s_{t+1}\)) 이다

\( \nu_{\pi} \) : 정책 \( \pi \)의 실제 가치를 의미하며

V : 학습과정에서 업데이트하고 있는 테이블 안에 쓰여있는 값으로 \( \nu_{\pi} \)와 같아지기를 바라는 값

따라서 

이고, 현실에서 사용되는 TD타깃 \( r_{t+1} + \gamma V(s_{t+1}) \)는 편향되어 있다.

편향의 의미를 해석하자면, TD타깃은 샘플을 무한히 모아서 업데이트해도 실제 가치에 다가간다는 보장이 없다는 뜻이다. 하지만 몇 가지 조건을 붙이면 실제로 의미있게 동작한다. 그 부분은 뒤에서 다시 언급한다.

데이터의 편향성 측면에서 보았을 때는 편향되어 있지 않은 MC학습법이 우세하다.

3.3 분산 (변동성)(Variance) 측면

- MC 학습 과정에서 나오는 리턴값은 변동성이 크다

- TD학습과정에서 나오는 TD타깃은 변동성이 작다

1) MC 학습 과정에서 나오는 리턴값은 변동성이 크다

MC학습에서 하나의 리턴값을 얻으려면 하나의 에피소드가 종료되어야 하며 하나의 에피소드 과정에는 많은 확률적 과정이 들어가 있다. 쉽게 말해 수많은 동전 던지기가 실행되면서 에피소드가 진행된다는 의미이다.

따라서 그만큼 리턴 결과 값은 변화가 클 수 있다는 것이다.

2)TD학습과정에서 나오는 TD타깃은 변동성이 작다

TD학습과정에서 밸류값을 업데이트 하기 위해서는 한 스텝만 이동하면 되므로 확률적 과정이 상당히 적게 들어간다.

액션 선택과정과 액션선택 후 다음 상태로 전이하는 과정, 이렇게 2과정이 확률적 과정이라고 보면 된다.

따라서 그만큼 결과값의 변동성이 MC 보다는 작을 수 있다는 것이다.

3.4 종합

요즘 강화학습은 종료상태가 있건 없건 사용가능한 TD학습을 많이 적용하고 있다.

4. MC와 TD의 중간 성격을 지닌 학습방법

4.1 n스텝 TD

이 방법은 여러 스텝을 진행하여 각 스텝별 보상을 받은 후 그 다음스텝의 V(\(s_{t+n}\)) 값을 이용하여 밸류를 계산할 수 있다는 개념이다.

이 개념을 수식으로 표현하면 아래와 같다.

N을 무한대로 했을 경우 식은 아래와 같다.

이 경우 결국 리턴계산식과 동일하다.

TD 학습방법에서 n이 무한대인 특수한 경우가 MC라는 것을 알 수 있다.

이 내용을 하나의 스펙트럼으로 표현하면 아래와 같다.

위 그림에서 좌측 끝단은 TD-zero (N=1인 경우의 TD타깃을 이용하여 업데이트하는 방법론),

우측 끝단은 MC 학습을 의미한다.

N이 커질수록 MC 성격에 가까워지게 된다.

즉, 추측값인 TD타깃의 값이 작아지고 보상의 비중이 늘어가게 되어 결국 편향성은 줄어들고, 확률적 과정이 점차 많이 포함되므로 변동성은 점차 커지게 된다.

결국, TD 학습을 적용할 때 N을 얼마로 할 것인지가 주요한 결정이 될 것이다.

유명한 A3C 알고리즘 논문은 N = 5로 하여 적용하였다.

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

간단한 그리드 월드 MDP 상황을 예시로

정책 \( \pi \)가 주어졌을 때 각 상태의 밸류를 평가하는 prediction문제와

최적의 정책 함수를 찾는 control 문제를 푸는 방법에 대해 설명한다.

2가지 전제조건이 있다.

1. 작은문제 ( 상태집합(S)과 액션집합(A)의 크기가 작은 문제 )

2. MDP에 대해 알고 있다. (즉, 보상과 전이확률을 알고 있다)

이 전제조건이 만족하기에 테이블 기반 방법론을 활용하여 문제를 풀어나간다.

(테이블 기반 방법론 이란 - 모든 상태 s 혹은 상태와 액션의 페어(s, a)에 대한 테이블을 만들어서 값을 기록해 놓고 그 값을 조금씩 업데이트하는 방식)

1. 밸류 평가하기 - 반복적 정책 평가

풀어야 할 문제와 상황은 다음과 같이 정리할 수 있다.

4방향 랜덤이라는 정책함수 \( \pi \)가 주어졌고 이때 각 상태 s에 대한 가치함수 \( \nu(s) \)를 구하는 전형적인 prediction 문제이다.

이 문제는 테이블 값들을 초기화한 후, 벨만 기대 방정식을 반복적으로 사용하여 테이블에 적어 놓은 값을 조금씩 업데이트해 나가는 반복적 정책 평가 방법론을 사용하여 풀게 된다.

보상은 모든 상태에서 -1 이다.

전이확률 \( P_{ss^{'}}^a \) 은 100%이다( 예를 들면, 좌측 이동 액션을 선택한 경우 다음 상태는 100% 좌측상태로 이동하기 때문)

\( \gamma \) 는 편의상 1 로 정한다

(1) 테이블 초기화 과정

테이블 빈칸은 상태별 밸류 \( \nu(s) \)를 기록해야 하기 때문에 상태 개수만큼 필요하다.

임의의 값 0으로 초기화한다. 추후 반복적 정책평가를 진행하면서 각 상태의 밸류들은 특정값으로 수렴해 갈 것이다.

(2) 상태의 값을 업데이트하는 과정

\( s_5 \) 상태의 밸류를 좀 더 정확하게 업데이트 하려면 , 정책이 주어져 있고 MDP를 알고 있으므로

아래의 벨만 기대 방정식 2단계 공식을 이용해서 상태밸류를 계산할 수 있다.

이 수식은 현재 상태 s의 가치를 다음에 도달하게 되는 상태 \( s^{'} \)의 가치로 표현한 식이다.

이 식을 토대로 위 그림의 파란색 셀( \( s_5 \) )의 밸류를 노란색 셀의 밸류를 이용해 업데이트 한다.

위의 벨만 기대 방정식을 그리드 월드에 맞게 풀어 적으면 아래와 같다.

$$ \nu_{\pi}(s_5) = \pi( 좌|s_5) ( r_{s_5}^좌 + \gamma ( P_{s_{5}s_{4}}^{좌} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{좌} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{좌} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{좌} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 우|s_5) ( r_{s_5}^우 + \gamma ( P_{s_{5}s_{4}}^{우} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{우} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{우} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{우} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 상|s_5) ( r_{s_5}^상 + \gamma ( P_{s_{5}s_{4}}^{상} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{상} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{상} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{상} \nu_{\pi}(s_9) ) ) $$

$$ \quad\qquad + \pi( 하|s_5) ( r_{s_5}^하 + \gamma ( P_{s_{5}s_{4}}^{하} \nu_{\pi}(s_4) + P_{s_{5}s_{6}}^{하} \nu_{\pi}(s_6) + P_{s_{5}s_{1}}^{하} \nu_{\pi}(s_1) + P_{s_{5}s_{9}}^{하} \nu_{\pi}(s_9) ) ) $$

이 식에 실제 값을 대입해보자

$$ \nu_{\pi}(s_5) = 0.25 \times ( -1 + 1 \times ( 1 \times 0 + 0 \times 0 + 0 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 1 \times 0 + 0 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 0 \times 0 + 1 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times ( 0 \times 0 + 0 \times 0 + 0 \times 0 + 1 \times 0 ) ) $$

정리하면,

$$ \nu_{\pi}(s_5) = 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

$$ \quad\qquad + 0.25 \times ( -1 + 1 \times 0  ) $$

결과값은, 

$$ \nu_{\pi}(s_5) = -1 $$

따라서 테이블의 파란색 셀, 즉 상태 \( s_5 \)의 밸류를 -1로 업데이트한다.

여기서 노란색 셀의 밸류들이 초기에 임의의 값으로 지정했기 때문에 그 값을 이용해 계산된 파란색 셀의 값도 정확한 값이 아니다. 하지만 실제 값인 보상값이 포함되어 계산되었기 때문에 초기 임의의 값보다는 실제값에 조금 가까워졌다고 볼 수 있다.

이런 과정을 상태를 이동해가며 계속 반복적으로 진행하다 보면 점차 상태들의 밸류값들이 실제값에 가까워진다.

(3) 모든 상태에 대해 (2)의 과정 적용

(2)의 과정을 마지막 상태를 제외한 15개 상태에 대해서 진행하여 위 그림의 오른쪽과 같은 결과를 얻는다.

가장자리 상태의 업데이트 계산은 바깥을 향하는 액션은 제외시킨다

예를 들면, \( s_0 \) 상태에서 보면 좌, 상 이동은 선택액션에서 제외되어야 한다.

(2)과정의 수식을 \( s_0 \) 상태에 적용해서 나열하면 다음과 같다.

$$ \nu_{\pi}(s_0) = \pi( 우|s_0) ( r_{s_0}^우 + \gamma ( P_{s_{0}s_{1}}^{우} \nu_{\pi}(s_1) + P_{s_{0}s_{4}}^{우} \nu_{\pi}(s_4) ) ) $$

$$ \quad\qquad + \pi( 하|s_0) ( r_{s_0}^하 + \gamma ( P_{s_{0}s_{1}}^{하} \nu_{\pi}(s_1) + P_{s_{0}s_{4}}^{하} \nu_{\pi}(s_4) ) ) $$

정리하면,

$$ \nu_{\pi}(s_0) = 0.5 \times ( -1 + 1 \times (1 \times 0 + 0 \times 0 ) ) $$

$$ \quad\qquad + 0.5 \times ( -1 + 1 \times (0 \times 0 + 1 \times 0 ) ) $$

$$ \nu_{\pi}(s_0) = 0.5 \times ( -1 + 1 \times 0 ) $$

$$ \quad\qquad + 0.5 \times ( -1 + 1 \times 0 ) $$

$$ \nu_{\pi}(s_0) = 0.5 \times -1 + 0.5 \times -1 $$

$$ \nu_{\pi}(s_0) = -1 $$

결과값은, 

$$ \nu_{\pi}(s_0) = -1 $$

정책이 정해져 있는 상태에서 (여기서는 4방향 랜덤한 액션 선택 정책) 마지막 상태를 제외한 모든 상태에 대해서 반복적인 정책평가를 진행하다보면 각 상태별로 특정값에 수렴해간다.

예를 들어, 상태 \( s_0 \)의 수렴값이 -59.4 가 나왔다.

즉, 이 값은 상태 \( s_0 \)의 가치밸류가 -59.4 라는 의미이고 현재 상황에서 의미는 4방향으로 무작위로 움직이다 보면 평균적으로 대략 60번은 움직여야 종료 상태에 도달하게 된다는 뜻이다.

2. 최고의 정책 찾기 - 정책 이터레이션

최적의 정책을 찾는 방법은 정책 이터레이션과 밸류 이터레이션 방법이 있다.

이 중 정책 이터레이션은 정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할 때까지 반복하는 방법론이다.

정책 이터레이션은 2단계로 구성된다.

1단계 ) 정책평가단계: 임의의 정책으로 \( \pi \)를 고정해놓고 반복적 정책 평가 방법을 사용하여 각 상태의 밸류를 계산한다.

2단계 ) 정책개선단계: 1단계에서 계산해 놓은 상태별 밸류값 \( \nu(s) \)을 이용하여 그리디 정책을 생성한다. 

여기서 그리디 정책이란 현재상태에서 바로 앞의 이익을 최대화하는 선택을 하도록 하는 정책을 의미하며 현재 상황에 적용하면 현재 위치한 상태에서 4방향의 다음 상태를 선택할 때 상태밸류 \( \nu(s) \)값이 최대인 상태로 이동을 선택하도록 하는 정책을 의미한다.

1단계=>2단계=>1단계=>2단계... 반복적으로 진행하다보면 정책평가 결과인 가치밸류가 변하지 않고 그리디정책도 변화하지 않는 상태에 도달하게 된다.

이때가 최적의 정책과 최적 가치에 도달한 것으로 판단하면 된다.

그리디 정책 선택이 정책 개선을 의미하는 이유는,

\( \pi_{greedy} \) : 현재 상태에서 바로 다음 상태 이동만 그리디 정책으로 움직이고 그 후 상태 이동은 기존 정책으로 움직이는 정책

\( \pi \) : 기존 정책

위 2가지 정책 중 상태밸류가 높은 쪽은 당연히 \( \pi_{greedy} \) 정책이다. 이 논리를 t 시점뿐만이 아니라 t+1, t+2, .. 모든 시점에 대해 적용하면 결국 모든 상태에서 그리디 정책을 선택하는 것이 정책개선 효과가 있다고 판단할 수 있다.

- 정책평가 방법 간소화 하기

위에서 언급한 정책 이터레이션 방법은 1단계 정책평가 과정에서 정책을 평가하기 위해 반복적 정책평가방법을 사용하며 그 부분에서 상당한 시간을 소요하게 된다.

우리의 목적은 최적정책을 찾기 위해 정책을 평가하는 것이므로 정확한 값을 도출해내지 않더라도 큰 문제는 없다.

상태밸류값이 변하지 않을 때까지 반복평가하는 것이 아니라 예를 들면, 5번만 반복평가를 해도 그리드 정책을 선택에 문제가 없다는 것이다.

이런 논리를 적용하여 정책 이터레이션에서 1단계 정책평가는 1번만 계산하는 것으로 한다.

3. 최고의 정책찾기 - 밸류 이터레이션

밸류 이터레이션도 테이블 기반 방법론을 사용한다.

각 셀은 최적 정책 \( \pi^{*} \)의 밸류인 \( \nu_{*} (s) \) 를 의미하게 된다.

초기에는 셀의 값들을 0으로 초기화한다.

MDP를 알고 있으므로 ( 보상과 전이확률값을 알고 있음을 의미 )

벨만 최적 방정식 2단계 공식을 사용해 각 셀의 최적밸류를 구한다.

예를 들어 \( s_5 \) 상태의 최적 밸류를 계산하면 아래와 같다.

같은 방식을 모든 셀에 적용한다.

각 셀의 밸류가 특정값에 수렴할 때까지 위의 방법을 반복적으로 수행한다.

최적 정책을 찾는 것이 목표인데 최적 밸류를 먼저 계산했다. 

이유는 MDP를 모두 알고 있는 상황에서는 최적 밸류를 계산하는 것이 최적 정책을 찾는 빠른 방법이다.

최적 밸류를 모두 계산해놓으면 임의의 상태에서 다음 상태 이동은 밸류가 가장 큰 셀로 이동하는 것이 최적 정책이다.

즉, 최적 밸류에 대한 그리디 정책이다.!!

의견 => 정책 이터레이션에서 계산 간소화를 위해 주어진 정책에서 상태밸류 계산시 반복적으로 계산하지 않고 1번만 계산하고 그리디 정책을 선택했다. 이 논리를 밸류 이터레이션에도 적용할 수 있을까?

즉, 최적 정책을 찾기 위해 최적밸류가 수렴할 때까지 반복적 계산이 필요할까 ? 하는 질문이다.

밸류 계산은 1번만 한 상태에서 그리디 정책을 적용하면 어떨까?

질문을 남겨두고 다음챕터로 넘어간다.