[논문 리뷰] Bayesian Reinforcement Learning: A Survey - 2.Technical Background

[논문 리뷰] Bayesian Reinforcement Learning: A Survey - 1.Introduction

[논문리뷰] Bayesian Reinforcement Learning: A Survey - 1.Introduction

---

지난 시간엔 BRL의 전반적인 내용에 대해 다루었다. 이번 시간엔 RL과 Bayesian의 기본 개념적인 부분을 다루고 그 둘을 융합하는 과정을 소개하고자 한다.

 

 

 

2.1 Multi-Armed Bandits(MAB)

1. 

불확실성 때문에 연속적으로 무언가를 결정하는 것은 아래와 같은 큰 딜레마를 가지고 있다.

 

Exploitation

현재의 state에서 가장 reward가 높게끔하는 action

vs

Exploration

지금의 reward는 적지만 미래에 더 많은 reward를 받는 action

 

이러한 딜레마를 그나마 최소화하는 모델이 바로 stochastic multi-armed bandit(MAB)이다.

 

K-MAB 모델을 정의하기 위해 아래와 같이 정의하겠다.

K-MAB model definition

우리가 어떤 환경에서 탐색을 하고자 할 때, 처음 그 환경은 우리가 알 수 없는 distribution을 갖기 때문에 decision-maker는 {최적이라 생각하는 arm을 고르는 것}과 {true-distribution을 알기 위해 더 많은 정보를 모으는 것} 사이에서 많은 고민을 해야한다.

 

 

 

2.

Regret에 대한 정의

그림의 중간에 있는 수식을 하나씩 풀어서 말로 설명하면, 아래와 같다.

 

(최적이라 생각하는 action의 결과에 대한 reward - t시점에서의 action에 대한 결과에 대한 reward)를 T시점까지의 합

즉, T시점까지의 실행한 action에 대한 기회비용의 합

 

으로 표현될 수 있다.

 

 

이를 전 시간에 들었던 온라인 쇼핑몰 예시에 대입하여 생각해보자.

(1) 온라인 쇼핑몰을 개설하고 customer에 대한 정보가 없다는 것을 아래와 같이 표현할 수 있다.

(2) 이 때의 regret minimization(기회비용 최소화) 방법은 다음과 같다.

 -  여러 T 시점까지의 순차적인 광고(a1, a2, ..., aT) 스트리밍을 성공적으로 태워야한다.

 

 

 

3.

하지만 여기에 고객에 대한 추가적인 정보가 있으면 의사결정을 하는데 더 좋은 결과를 낼 수 있다.

그 정보라 하면 성별, 출생지와 같은 정보를 말한다.

이를 MAB에 반영한 것이 바로 contextual bandit model이다.

이 모델은 여러 다른 말로도 볼리는데, associative bandit model, bandit with side infomation model 이라고도 불린다.

각 notation에 대한 설명은 위와 같고 contextual bandit model에 대한 정의는 아래와 같다.

 

 

 

 

 

2.2 Markov Decision Process(MDP)

1. 

MDP는 MAB의 확장버전이라 볼 수 있다.

state라는 개념을 추가하여 확장한 것인데, 동적으로 action을 변경하고 system의 결과를 반영함으로써 보다 더 최선의 결과를 내는 것이다.

위 그림에서처럼 R(s,a)는 state와 action이 주어졌을 때, 즉시 받을 수 있는 reward에 대한 random variable이다.

여기서 r(s,a)는 확률변수 R(s,a)의 한 원소로써 존재하고, R(s,a)의 기대값(expectation value)는 아래와 같다.

기대값에 대한 수식에서도 보이듯이 일반적으로 알고있는 관측치 * 확률로써 기대값을 정의했다.

여기서의 q는 확률이라고 보면 된다.

그래서 우리가 얻을 수 있는 reward의 기대값은 아래와 같은 한계가 있다.

 

 

 

 

2.

Markov라는 것은 연속적으로 관찰된 것 중에 가장 최근 state에 의존하는 distribution임을 나타내는 것이다.

그래서 보통 Markov는 stationary하다고 할 수 있고 이는 시간에 따라 변하지 않는다는 뜻이기도 하다.

이 정적인 Markov policy는 state가 주어졌을 때의 action의 set의 확률분포라 볼 수 있다.

다른말로 풀어 쓰면, 어떤 상태(state)가 주어졌을 때, 그 상황에 대응할 수 잇는 action들의 집합에 대한 distribution이라 할 수 있다는 말이다.

 

이것은 곧 deterministic하다고 말할 수 있다.

왜냐하면 모든 history에 대해 한가지 action에 의존하는 확률분포이기 때문이다.

그래서 deterministic policy는 state집합에서 action의 집합을 mapping하는 것으로 볼 수 있다.

 

이제부터 notation이 많이 나오는데 한 번 정리할 필요가 있을 것 같다.

Notation	의미
	Policy
	Markov Chain by policy mu
	Reward distribution by policy mu
	Reward when state s by policy mu --> reward distribution의 한 원소로 표현
	state와 action을 한 쌍으로 보는 변수 z
	z 변수에 대한 density
	시점 T에 대한 모든 z 변수의 집합

 

 

 

3.

Markov chain에 대한 수식이라 볼 수 있다.

자세히 뜯어보면 초기값에 나머지 확률들을 곱한 것으로 볼 수 있는데, Chain을 걸듯이 계속해서 곱해나가는 꼴이다.

policy를 $\mu$라고 했을 때,

초기 확률 * 모든 시점 T에 대해 {(t-1)번째 state와 action이 주어졌을 때, t번째에서 state와 action이 발생할 확률}

=

policy=$\mu$ 일때, Markov chain의 확률분포

라고 볼 수 있다.

 

 

4.

그리고 RL을 공부하다보면 trajactory라는 단어가 자주 보이는데, 직역하면 "(탄두의) 궤적" 이라는 뜻을 가지고 있다.

이와 관련된 글을 stackoverflow(https://ai.stackexchange.com/questions/7359/what-is-a-trajectory-in-reinforcement-learning)에서 발견했는데 정리하면 다음과 같다.

강화학습은 sequential하게 학습하면서 그때그때마다의 정보를 반영하는 학습 방법이다.

RL process(참조: https://www.researchgate.net/figure/Reinforcement-learning-schematic-Reinforcement-learning-RL-can-be-formulated-as-a_fig4_322424392)

그러면서 (s1, a1, r1), (s2, a2, r2), (s3, a3, r3), .... 등과 같이 어떤 로그?라는 것이 남는데 이런 일련의 과정을 trajectory라고 하며, 또는 path라는 표현을 쓰기도 한다.

 

 

 

5.

우리는 이러한 path의 결과값에 대한 것들을 함수로써 아래와 같이 표현할 수 있다.

path 결과값

각 ξ에 대해 ρ(ξ)라는 return값이 주어지고, ξ는 random variable로 기대값은 아래와 같이 나타낼 수 있다.

path의 결과값에 대한 기대값

path의 결과값과 그에 대한 기대값에서 γ(Gamma: 감마)는 discount factor로써, 오래된 reward의 가치를 적게 주기 위한 factor라고 볼 수 있다.

 

 

 

 

6.

이 때, policy가 mu로 주어졌을 때의 기대값은 아래와 같이 정의할 수 있다.

expected return of a policy mu

한 편, 위의 식에서 ρ ̅(ξ)는 5번에서 정의한 것처럼 random variable인 ρ(ξ)의 기대값이다.

그러므로 η(μ)에 대한 해석은 policy μ를 적용했을 때의 현재부터 기대되는 reward에 대한 기대값으로 볼 수 있다.

 

한 편, 이와 비슷하게 state에 대한 결과의 기대값도 아래와 같이 구해볼 수 있다.

expected return of a state under policy mu

이 수식을 풀어서 해석하자면, policy가 mu이고 state가 S일 때의 reward에 대한 sum으로 볼 수 있다.

그리고 D(s)의 기대값은 policy mu의 value function이라고도 불린다.

 

이 수식을 풀어서 설명하자면, 일단 total expected discounted reward로 볼 수 있다.

agent가 처음 시작할 때, state s, action a, policy mu가 주어졌을 때의 식임을 알 수 있다.

 

 

 

위의 두 식을 사용하여 아래의 total expected discounted reward에 대한 벨만 방정식을 구할 수 있다.

Bellman equation for V^mu