단단한 강화학습 Chapter5_몬테 카를로 방법 (Monte Carlo Methods)

Chapter 5에서는 Value Function을 추정하고 최적의 Policy를 찾는데 활용할 첫번째 "학습" 방법을 다룹니다.

 

이전 Dynamic Programming에서는 환경에대한 모델링을 알고있었기 때문에,

내가 어떤 State에서 어떤 행동을할때 얼마만큼의 확률로 어떤 State에 도달하는지 알수 있었고, 그에대한 Reward도 파악할 수 있었습니다. 즉, P(s,r | s`,a)를 알고있기 때문에 이를기반으로 Policy Evaluation과정을 진행할 수 있었습니다.

 

이러한 방식은 환경을 이미 다 알고 그안에서 에이전트가 어떻게 행동할지 결정한다는 점에서

Learning방식이라기보다는 Planning방식이라고 책에서는 구분짓습니다.

Learning이라고 구분짓는 방식은 환경을 모른다고 가정하고, 환경과의 상호작용으로부터 발생한 경험에 의존하여 에이전트의 행동을 결정하게됩니다.

 

그중에서도 Monte Carlo Method는 표본이득의 평균값을 이용해서 가치함수값을 추정하는 알고리즘을 말합니다.

 

 

◆목차

◎ 몬테카를로 예측 (Monte Carlo Prediction)

◎ 몬테카를로 행동가치 추정 (Monte Carlo Estimation of Action Values)

◎ 몬테카를로 제어 (Monte Carlo Control)

◎ 시작 탐험 없는 몬테카를로 제어 (Monte Carlo Control without Exploring Starts)

◎ 중요도 추출법을 통한 비활성 정책 예측 (Off-policy Prediction via Importance Sampling)

 

 

 

◎ 몬테카를로 예측 (Monte Carlo Prediction)

- What is the Monte Carlo Prediction?

이전 Dynamic Programming에서는 환경에 대한 모든 정보, 즉, State Transition Probability와 그에대한 Reward를 이미 알기때문에, 해당 State s에대한 V(s)값을 그저 여러번의 Iteration을통해 근사시킬 수 있었습니다.

 

하지만 실제 에이전트는 대부분 환경모델에 대한 정보가 없기에, 위와같은 접근이 불가능합니다.

즉, 직접 환경과 부딫혀보고 이를 평균내어보면서 V(s)를 찾을 수 밖에 없게됩니다.

 

Monte Carlo Method는 그중 가장 기본이 되는 방식으로,

시뮬레이션 표본의 평균을 통해 가치함수를 추정하는 방식을 말합니다.

 

State S에 대한 가치함수 G를 계산하고싶다고 할때,

 

St에 도달하는 모든 경우의 수는 결국, Terminal State T까지도달할 것이고,

각각의 Gt는 아래 처럼 주어질 것입니다.

Monte Carlo Method는 이때 St에 도달하는 모든 경우의 수에 대한 G(St)의 평균을 계산하는 방식입니다.

 

크게 최초접촉 MC방식(First-visit MC Method)과 모든접촉 MC 방식 (Every-visit MC Method)으로 나눌수 있는데,

에피소드 내에 최초 접촉(visit)한 State에 대해서 

에피소드간 더하여 평균을 내는 것을 최초접촉 MC방식(First-visit MC Method)라고 하고,

해당 State에 몇번 접촉(visit)했는지 유무와 관계없이 접촉한 순간부터 Terminal State까지의 모든 Reward에대한 Gt의 평균을 내는 것을 모든접촉 MC 방식 (Every-visit MC Method)이라고 합니다.

 

예시는 아래와 같습니다.

최초접촉 MC 예시

모든접촉 MC 예시

 

- Practical Aspects of MC

책에서는 Monte Carlo방식, Model Free로 접근하는 방식이 환경에 대한 정보를 알 수 있을때도 유용하게 쓰일 수 있다는 내용을  블랙잭 게임을 예시로 정리해두고 있습니다. (풀이는 Skip)

 

MC가 DP보다 대부분의 상황에서 유용한 이유는,

일반적으로, 환경에 대한 모든 State Transition Probability와 Reward Function을 정의하는 것은 상당히 까다롭기 때문입니다. 정의된 환경에 모든 State에 대해 Probability와 Reward를 정의해주는 일 보다, 그저 샘플게임을 생성하여 이를 평균내는 일에 훨씬더 Cost가 적게 듭니다.

 

 

- Incremental MC Update

즉, Vπ(s) = E(Gt)가 되는데, 이를 좀더 효과적으로 쓸 수 있는 방법에 대해 다뤄보겠습니다.

 

만약 MC 가치 평가를 모든 Gt에 대해 평균을내고 일일이 업데이트하면, 기존의 모든 Gt를 메모리에 저장하고 있어야 하므로, 매우 메모리에 비효율적인 요소로 작용하게 됩니다.(RL Agent가 지속적으로 학습하는데 한계점으로 작용)

 

이 문제는 간단한 방식으로 이를 Online 평균기법으로 변환하여 해결할 수 있는데,

예전에 블로그에서 정리했던 점증적 구현(Incremental Implementation) 아이디어를 사용합니다.

https://roboharco12.tistory.com/54

단단한 강화학습 Chapter2_(1) _다중선택(Multi-armed Bandits)

 

이런 방식으로 업데이트하면, 바로 직전 Sample의 V(s) 값과 새롭게 관측되는 값만 V(s)(=Gt) 값만 파악하면 되므로, 가치함수를 업데이트할때 효율적으로 업데이트가 가능해집니다.

새롭게 관측되는 Gt 값을 이용해 기존 State Value V(s)를 Update

 

보통 이 Incremental한 Format에서

Step Size에 해당하는 1/N(s)를 고정된 Step Size,  α로 표현하는데, 이 역시

https://roboharco12.tistory.com/54

단단한 강화학습 Chapter2_(1) _다중선택(Multi-armed Bandits)

비정상 문제의 흔적 (Tracking a Nonstationary Problem) 파트에서 정리했던 바 있습니다.

 

 

+

고정된 Stepsize로 Update를 하는 이유는,

Nonstationary Problem일 경우 1/N(s)을 사용하는게 잘 작동하지 않기 때문도 있지만,  

또 한가지 다른 이유를 첨언하자면, 현실에서는 N(s)를 세는것 조차 어려운 경우도 많기 때문입니다.

S가 이산적이지 않은 경우는 심지어 셀 수도 없구요, 이산적이라 하더라도 세기가 어려운경우가 훨씬 많습니다.

 

고정된 Stepsize, α는 이러한 부분을 고려하지 않고도 해당 State에 대한 Value값을 Update할 수 있게 해줍니다.

 

 

 

 

- 보강 다이어그램(Backup Diagram)으로 바라본 MC, DP

보강다이어그램의 일반적인 개념은 제일 위쪽에 갱신할 루트 노드를 보여주고, 그 아래에 모든 State전이와 Action 노드를 보여주는 것입니다. 이때 루트노드 이후에 나타나는 모든 행동 노드의 보상과 기대 가치가 루트 노드를 갱신하는데 기여합니다.

 

아래 보강 다이어그램 그림을톻해,

DP와 MC의 구체적인 차이에대해 비교해보도록 하겠습니다.

 

 

위 그림을 살펴보면,

 

DP 다이어그램 같은경우, 해당 State Value를 Update하는데 가능한 모든 Transition을 이용하고, Terminal State까지 포함하지 않는 반면,

MC 다이어그램 같은 경우, Sample의 단일 전이과정을 이용하고, Terminal State까지 도달한 전과정을 포함한다는 차이를 명확히 구분할 수 있습니다.

 

한가지더 위 보강다이어그램에서 확인할 수 있는 DP와 MC의 주된 차이는, 바로 Bootstrap의 여부입니다.

https://velog.io/@kjb0531/%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5%EC%97%90%EC%84%9C-Bootstrapping%EC%9D%98-%EC%9D%98%EB%AF%B8

강화학습에서 Bootstrapping의 의미

 

강화학습에서 Bootstrapping이란, 예측값을 이용해 또다른 예측값을 이용하는 것을 의미하는데,

(즉, Known값이 아니라, Prediction값을 Known값이라 치고 또 다른 Prediction값을 예측하는)

 

 

DP에서는 어떤 상태의 가치 추정값을 갱신할때,

그 상태로부터 파생되는 상태의 "가치 추정값"을 기반으로,

"해당 추정값"을 Update하므로, 그 자체로 Bootstrapping의 성격을 띕니다.

 

그러나 MC에서는 하나의 State 에 대한 추정이 다른 어떤 State에 대한 추정으로 부터 영향을 받지 않습니다.

각 State에 대한 추정이 서로 독립적이라는 특성을 가지고 있기 때문입니다.

즉, MC 방식은 DP와다르게 Bootstrapping을 하지 않습니다.

 

MC에서는 얼마나 주변 상태가 존재하는지 여부와 관계없이

하나의 상태에 대한 가치를 Update 할 수 있기 때문에(해당 State에 방문하는 Sample개수만 많으면 되니까),

하나 또는 일부 상태에 대해서만 가치를 추정하려고 할때, MC 방식은 매력적으로 보일 수 있습니다.

관심있는 State에 대해 우선적으로 많은 표본 Episode를 만들고, 다른 상태는 제외한채 이 상태들에 대해서만 이득의 평균을 계산할 수 있기 때문입니다.

 

이러한 사실은 DP에 비해 MC가 비교우위를 갖는 또다른 포인트중 하나입니다.

 

 

 

 

◎ 몬테카를로 행동가치 추정 (Monte Carlo Estimation of Action Values)

앞서

https://roboharco12.tistory.com/51

DRL_Introduction_(3) Value Based Approach_1

에서 언급했듯,

Value Function에는 State Value Function 뿐 아니라 Action Value Function도 존재합니다.

 

DP에서처럼 환경모델을 활용할 수 있는 경우 State Value Funciton을 활용해도 충분히 유용하지만,

그렇지 못할때는 Action Value Function을 추정하는 것이 훨씬더 유용합니다.

State Transition Probability를 모르기 때문에, One Step Ahead Search가 보통은 불가능하기 때문입니다.

(One Step Ahead Search: 한 State에서 다음 State로 가능한 모든 Action 경우의 수에 대한 확률을 찾아주는 것)

 

 

이러한 이유로, MC의 주된 목표는 q*를 추정하는 것이 됩니다.

 

Action Value에 대해 Policy Evaluation 문제를 MC로 푸는 것은,

앞서 State Value에 대해 다루었던 방식과 동일합니다.

똑같이 최초접촉(First-Visit)방식과 모든접촉(Every-Visit)방식으로 구분지을 수 있고, Incremental한 Update방식이 가능합니다.

 

유일한 문제는 State-Action쌍에 대한 가치함수이므로, State에 대한 가치함수일때보다 수많은 쌍이 생겨

모든 State-Action에대해 접촉이 발생하지 않을 수도 있다는 점입니다. 만약 Policy가 Deterministic하다면,

해당 정책의 각 State에서 Optimal하지않은 Action에 대한 접촉은 이루어지지 않을 것이기 때문입니다.

 

이것을 방지하는 한가지 가정은,  Deterministic하지않은, Probabilistic한 Policy임을 가정하는 것입니다.

에피소드가 하나의 State-Action쌍에서 시작하고, 이후 접촉하게될 모든 State-Action쌍이 선택될 확률이 0이 아니라는 점을 명시함으로서, 무한번의 Episode에 대해 빠짐없이 모든 State-Action쌍을 무한번 방문하는 것을 보장할 수 있습니다.

이를 책에서는 시작탐험(Exploring Starts)의 가정이라고 합니다.

 

시작 탐험을 가정하는 것 자체는 유용하긴하지만, 일반적으로 크게 도움이 되지는않습니다.

특히나 실제 환경과의 상호작용으로부터 직접 학습하는 경우에는 더욱 그렇습니다.

 

 

◎ 몬테카를로 제어 (Monte Carlo Control)

 

 

주어진 Policy에 대한 가치함수를 V, 또는 Q를 추정하는 것을 Evaluation,

GPI(Generalized Policy Iteration)과정을 통해 Evaluation과 Improvement를 번갈아 진행하는것을 Control이라 합니다.

 

Policy Evaluation 과정을

환경모델을 통해 각 State의 Value를 업데이트하는것이 DP,

시뮬레이션의 여러 샘플들을 통해 산술평균값을 각 State의 Value로 업데이트하는 것이 MC라고 할 수 있습니다.

 

그리고, MC에서 Action Value를사용함으로서, Policy Improvement과정에서 별도의 One Step Ahead Search가 필요하지 않으며, 그저 주어진 qπ에 대해 탐욕적으로 최대의 행동가지치값을 같는 Action을 선택하도록 함으로서 간단하게 진행할 수 있습니다.

 

DP 포스팅에서 State Value로 논의했던 바와 같이,

Policy Improvement과정을 통해 Improvement된 πk+1은 항상 (Uniformly) πk 보다 더 좋거나, 똑같이 좋다는 것을 보장합니다. 이에 따라 전체과정이 최적 정책과 최적 가치함수로 수렴한다는 것도 보장됩니다.

 

 

 

 

 

 

DP에서와 마찬가지로 MC에서역시 Policy Evaluation은 점근적으로만 가치함수의 참값에 수렴할 뿐, 정확한 Evaluation값을 한번에 알수는 없습니다. 책에서는 무한번에 에피소드를 피하면서 수렴하는 두가지 보정방법을 제시합니다.

 

하나는 각각의 Policy Evaluation에서 qπk를 모두계산하는게아닌, 근사하는 것입니다.

측정과 가정을 통해 추정오차의 크기와 확률에 대한 경곗값을얻고, 이러한 경곗값이 충분히 작음을 보장하기위해 각각의 정책평가 과정에서 충분한 단계를 거치는 것입니다.(단, 이런방식은 너무많은 에피소드를 요구할 수 있습니다)

 

다른 하나는 DP에서처럼 완벽한 Evaluation이 이루어지기전에 Improvement를 진행하는 것입니다.

가장 극단적인 경우로서 Value Iteration을 예시로 DP에서 다뤘었습니다.

MC에서의 Value Iteration은 Sample이 아닌, Episode마다 Improvement를 진행해준 것이 자연스럽습니다.

각각의 Episode이후에 관측된 이득이 정책 평가에 활용되고 나면, Episode에서 마주치는 모든 상태에서 정책은 향상됩니다.

 

이러한 과정을 따르고, 시작탐험(Exploring Starts) 가정을 적용한 MC알고리즘을 Monte Carlo with Exploring Starts 줄여서 몬테카를로 ES라고 합니다.

 

 

 

 

 

◎ 시작 탐험 없는 몬테카를로 제어 (Monte Carlo Control without Exploring Starts)

https://roboharco12.tistory.com/59

단단한 강화학습 Chapter5_(1)_몬테 카를로 방법 (Monte Carlo Methods)

앞선 포스팅에서,

MC에서는 State-Action쌍에 대한 Q Value의 평균을 내어 경우의 수가 한참 많기때문에

자칫 모든 Action이 접촉(Visit)되지 않을 가능성을 내포하고 있고,

시작탐험(Exploring Starts)이라는 가정을 통해 무한번의 Episode에서 모든행동이 무한번 접촉되도록 보장 하였습니다.

 

그러나 시작탐험만으로는 이러한 보장을 매우 제한적인 경우에만 할수 있습니다.

시작탐험외에 이 문제를 해결하기 위한 또다른 접근법으로 On-Policy(활성 정책)과 Off-Policy(비활성 정책)이 있습니다.

 

On-Policy 방식은 기존 하던 방식처럼, 실제 Policy로부터 Episode에 기록된 State, Action, Reward를 이용하는 반면,

Off-Policy 방식은 실제 Policy가 아닌 Policy를 사용하여 Value를 Update하는 방식을 말합니다.

 

책에서는, 두 방식 각각에서 모든 행동에 접촉을 보장하는 방법을 설명하고있습니다.

On-Policy에서는 ϵ- Greedy정책을, 그리고 Off-Policy에서는 Importance Sampling에대해 각각 다루고 있는데요,

이 섹션에서 On-Policy를 먼저 다루고 다음섹션에서 Off-Policy에 대해 다뤄보도록 하겠습니다.

 

Agent는 Policy에 따라 Action을 결정하는데, 이때 Action-Value인 Q가 가장 큰 Action을 선택하는 것을 Greedy-Policy라 하고, 이때 이따금씩 전체 Action집합중에 Uniformly Ramdom하게 Action을 선택하는 것을 ϵ- Greedy정책이라 합니다.

 

 

 

state s에서 가능한 행동 a∈|A(s)|에 대해  ϵ- Greedy정책은 아래와 같습니다.

 

그리고 위와같이 정의된 ϵ- Greedy정책은 ϵ- Soft 정책보다 항상 더 좋은 결과를 보장합니다.

ϵ- Soft 정책이란,  정책 π가 모든 State-Action쌍에 대해 π(s|a)  >=  ϵ / |A(St)|  관계를 항상 만족하는 정책으로, 

ϵ-Greedy 정책은 ϵ- Soft 정책의 종류중 하나가 되며, 그중 가장 성능이 좋은 정책이라고 정리해볼 수 있습니다.

이에대한 증명은 아래 수식으로 책에서 정리되고 있습니다.

 

 

π`가 ϵ-Greedy 정책, π가 ϵ-Soft 정책이라고 할때, 

마지막 합의 기호는 1이 되는 음이아닌 가중치를 적용한 평균. 그렇기 때문에 이값은 분명히 최댓값에 대한 평균보다 작거나 같아야 한다 (옮긴이)

 

◎ 중요도 추출법을 통한 비활성 정책 예측 (Off-policy Prediction via Importance Sampling)

이제 Off-Policy 기법으로 넘어가보도록 하겠습니다.

앞서 Off-Policy 방식은 실제 Policy가 아닌 Policy를 사용하여 Value를 Update하는 방식이라고 했습니다.

이를 조금더 구체화시켜보도록 하겠습니다.

 

모든 학습 제어에서는 어떤 행동에 이어지는 최적행동에 따라(Greedy Policy에 따라) Qπ(s,a)를 학습하려 합니다.

하지만, 이렇게 할경우 모든 행동에 접촉하지 못하기에, 모든 행동을 접촉하려면 Qπ(s,a)에 대한 학습을 포기해야하는 상황이 벌어집니다.

 

Off-Policy 학습에서는 이 두가지 Trade Off를 효과적으로 해결할 수 있습니다.

학습 대상이 되는 Policy를 Target Policy π, 그리고 임의로 정한 정책을 Bahavior Policy b라고 할때,

 

Target Polocy π에 대한 Qπ(s,a)를 추산하는 과정을

Target Policy π뿐 아니라 임의의 정책 b를 통해서도 추산이 가능하도록 할 수 있습니다.

정리하면, "Behavior Policy b를 통해 얻은 데이터로 Target Policy π를 학습시키는 것"이 목표가됩니다.

 

 

 

이에대한 가장 일반적인 방법이바로 Importance Sampling인데요,

Importance Sampling이란, 두 정책 간의 확률 비율(π(s_t, a_t) / b(s_t, a_t))을 가중치로 부여함으로서 이를 해결하는 방법을 말합니다.

 

무슨말이냐면,

어떤 Episode에서 아래와같은 Trajectory를 가진 다고 했을때,

Target Policy π를 따를때 이러한 Trajectory가 형성이 되었을 확률은

임의의 Behavior Policy b를 따를 때 이러한 Trajectory가 형성이 되었을 확률은 단지 π기호를 b로 바꿔주면 되는 것이므로,

 

결과를 살펴보면, p(Sk+1|Sk,Ak) Term이 똑같은 것을 알 수 있는데 이를 통해 비율을 계산하면 이 State Transition Probability Term을 고려안해도 되는 형태가 됩니다.

이 결과가 의미하는것은, Sum of Reward에 대한 기대값 Gt를 추출할때 State Transition Probability를 굳이 추산하지않더라도 Gt를 수학적으로는 파악할 수 있다는 것을 의미합니다.

 

 

이러한 Importance Sampling은 크게 두가지 방식이 있는데,

하나는 기본 중요도 추출법(Ordinary Importance Sampling)이고, 다른 하나는 가중치 중요도 추출법(Weighted Importance Sampling)입니다.

 

 

기본 중요도 추출법은 두 정책 간의 확률 비율(π(s_t, a_t) / b(s_t, a_t))을 사용하여 반환값(Gt)을 조정합니다. 이 방법에서는 각 반환값에 가중치를 곱하여 조정된 반환값을 얻습니다. 기본 중요도 추출법의 한계점 중 하나는 큰 가중치가 반환값에 과도한 영향을 미칠 수 있다는 것입니다. 이로 인해 반환값의 분산이 커지고, 학습이 불안정해질 수 있습니다.

 

가중치 중요도 추출법은 기본 중요도 추출법의 한계를 극복하기 위해 개발된 방법입니다. 이 방법에서는 가중치를 정규화하여 합계가 1이 되도록 조정합니다. 이렇게 하면 큰 가중치가 반환값에 과도한 영향을 미치는 것을 방지할 수 있습니다.

가중치 중요도 추출법은 반환값의 분산을 줄이는 효과가 있으며, 학습이 더 안정적으로 이루어질 수 있습니다. 이 방법을 사용하면, Behavior Policy로부터 수집된 데이터를 이용해 Target Policy를 업데이트하는 과정이 더 효율적이고 안정적이게 됩니다.

 

 

 

 

 

 

 

 

 

 

기본 중요도 추출법(Ordinary Importance Sampling)과

가중치 중요도 추출법(Weighted Importance Sampling)에 대해서

수식으로 살펴보겠습니다.

 

Gt는 시간 스텝 t에서의 반환값(각 보상의 미래 합계)이고, V(s)는 상태 S에서의 가치함수(상태 S에서 기대되는 반환값)입니다. 즉, V(St) = E(Gt)입니다.

 

 

 

 

 

일반적인 Ordinary Importance Sampling을 사용하여 반환값 Gt를 조정하는 경우, 다음과 같은 식이 적용됩니다.

 

Gt_IS = Π(π(s_t, a_t) / b(s_t, a_t)) * Gt

 

이 식에서 Gt_IS는 Importance Sampling을 사용하여 조정된 반환값을 나타냅니다. 이렇게 조정된 반환값은 원래의 반환값 Gt에 두 정책 간의 확률 비율의 곱을 곱한 것입니다. 이 곱셈은 시간 스텝 t부터 T까지의 모든 스텝에 대해 수행됩니다.

V(s)는 상태 s에서의 기대 반환값입니다. Importance Sampling을 사용하여 V(s)를 계산하는 경우, 다음과 같은 식을 사용할 수 있습니다.

 

V(s) = E[Gt_IS]

 

책에서는 다음과같은 수식 하나로 정리해두고있습니다.

 

 

 

 

가중치 중요도 추출법(Weighted Importance Sampling)은 큰 가중치에 대한 분산이 커지는 현상을 막기위해

가중치를 Normalization하여 곱해주는 기법을 의미합니다.

 

Gt_IS를 정규화된 가중치로 표현하려면, 가중치 합을 사용해 값을 정규화해야 합니다.

이때 가중치 W_t를 아래와같이 정의한후,

W_t = Π(π(s_t, a_t) / b(s_t, a_t))

 

Gt_IS를 정규화된 가중치로 표현하기 위해, 반환값 Gt와 가중치 W_t를 사용하여 가중 평균을 계산해주면

Gt_IS_normalized = W_t * Gt / Σ(W_t)

 

 

책에서는 

수식으로 정리해두고 있습니다.

 

(책 Notatation이 알아먹기가 어려워서.. 그냥 따로 정리했습니다)