강화학습 - 2. MDP , Dynamic process 정리

 

 

몬테카를로 

다이나믹 프로그래밍 아이디어의 결합한 방식

 

원시 경험에서 직접 학습가능

최종 결과를 기다리지 않고

에피소드가 끝날 때까지 기다리지 않고

학습된 추정치를 부분적으로 기반으로 추정치를 업데이트 한다.

 

대신 이전 학습 추정치를 기반으로 현재 추정치를 근사화하는데

이를 부트스트래핑이라 함

 

몬테 카를로 방법은 증분을 결정하기 위해

에피소드가 끝날 때까지 기다려야 하는 반면

TD 방법은 다음 단계까지만 기다리면 됨

 

프로즌 레이크 예제

 

다음 상태 전이 확률 분포의 환경 모델이 필요하지 않음

 

몬테 카를로 방법을 사용하면 에피소드가 끝날 때까지 기다린 후에야 반환을 알 수 있음

TD 방법은 한계만 기다리면 됨

 

모든 고정 정책에 대해 TD은 충분히 작은 경우 일정한 단계 크기 매개변수의 평균에서 u파이로 수렴하는 것으로 입증되었음.

 

def update_q_table(prev_staet, action., reward , nextstate, alpha, gamma):

qa = max(q[nextstate, a] for a in range(env.action_space.n))

q[(prev_state, action)] += alpha * (reward + gamma * qa - q[(prev_state, action)])

 

 

Def epsilon_greedy_policy(state, epsilon):

if random.uniform(0, 1) < epsilon:

return env.action_space.sample()

else:

return max(list(range(env.action_space.n)), key = lambda x: q[state, x])

 

 

Alpha = 0.4

Gamma = 0.999

Epsilon = 0.017

 

For I in range(8000):

r = 0

state = env.reset()

 

while True:

action = epsilon_greedy_plicy(state, epsilon)

nextstate, reward, done, _ = env.step(action)

update_q_table(state, action, reward, nextstate, alpha, gamma)

 

state = nextstate

r += reward

if done:

break

 

 

Solving the taxi problem using Q-learning

 

Import random

Import gym

From Python import display

Import time

Import matplotlib.pyplot as put

Import bumpy as np

$matplotlib inline

Env = gym.make(“Taxi-v2”)

 

env.render()

 

q = {}

For s in range(env.observation_space.n):

for a in range(env.action_space.n):

q[(s,a)] = 0.0

 

 

def update_q_table(prev_State, action, reward, next sate, alpha, gamma):

qa = max(q[nextstate, a] for a in range(env.action_space.n))

 

q[(prev_state}, action}]  += alpha * (reward + gamma * qa - q[(prev_state, action)]

 

def epsilon_greedy_policy(state, epsilon):

if random.uniform(0, 1) < epsilon:

return env.action_space.sample()

else:

return max(list(range(env.action_space.n)), key = lambda x: q[state, x])

 

 

Alpha = 0.4

Gamma = 0.999

Epsilon = 0.017

 

for I in range(8000):

r = 0

state = env.reset()

 

while True:

action = epsilon_greedy_policy(state, epsilon)

nextstate, reward, done, _ = env.step(action)

 

update_q_table(state, action, reward, nextstate, alpha, gamma)

 

state = nextstate

 

r += reward

 

if done:

break

 

print(“total reward” , r)

 

env.close()

 

State = env.reset()

total_reward = 0

 

While True:

action = max(list(range(env.action_space.n)), key = lambda x: q[state, x])

display.clear_output(wait=True)

display.display(plt.gcf())

env.render()

 

state, reward, done, _ = env.step(action)

total_reward += reward

print(“Episode Reward = “, total_reward)

 

time.sleep(0.5)

 

if done:

break

 

env.close()

 

 

Markov decision process(MDP)

 

Markov property와 Markov chain 에 대해 알아야 함

 

Markov property란 미래는 과거가 아닌 현재에만 의존하는 조건

Markov chain은 다음 상태를 예측하기 위해 이전 상태가 아닌 현재 상태에만 의존하는 확률 모델로 미래는 과거로부터 조건부 독립임을 말하는 모델들을 말한다.

 

이 때 Markov chain은 Markov property를 엄격히 따른다.

 

대표적인 예시로 날씨 예측이 있음

오늘의 날씨가 습하다면 곧 비가 온다는 근거가 되지만,

과거에 날씨가 흐렸다는 것은 미래 비가 올 가능성에 대한 근거가 되지 못한다.

즉 오로지 현재 상태만을 가지고 다음에 올 상황을 예측하는 것을 Markov chain이라 한다.

 

MDP의 이해를 돕기 위해 Transition과 Transition probability 용어에 대해 간략히 설명하자면, Transition은 한 상태에서 다른 상태로 이동하는 것을 말한다.

 

Transition probability은 한 상태에서 다른 상태로 이동할 경우 확률을 말한다.

 

Transition probabiblities를 테이블 형태로 정리할 수 있으며 이를 markov table이라 하며 transition probability이 있는 상태 다이어그램(state diagram) 형태의 마르코프 체인으로도 표현이 가능하다.

 

 

The Markov decision process

 

Markov decision process는 markov chain의 확장으로 의사 결정 상황을 모델링하기 위한 수학적 프레임워크를 제공한다.

MDP는 거의 모든 강화학습 문제를 모델링 할 수 있다.

 

 

MDP 의 다섯 요소

Statet 상태: 에이전트가 실제로 있을 수 있는 상태의 집합

Actions: 한 상태에서 다른 상태로 이동하기 위해 에이전트가 수행할 수 있는 행동의 집합

Transition probability 전환 확률: 어떤 동작을 수행하여 한 상태에서 다른 상태로 이동할 확류

Reward probability 보상확률: 에이전트가 어떤 행동을 수행하여 한 상태에서 다른 상태로 이동하여 얻을 수 있는 보상의 확률

 

Discount factor: 현재 및 미래 보상의 중요성을 제어하는 보정값

 

 

Reward and Returns

 

에이전트는 즉각적인 보상 대신 환경으로부터 받는 보상의 총량(누적 보상, cumulative rewards)를 최대화하려고 한다.

 

에이전트가 환경으로부터 받는 보상의 총량을 반환이라고 함.

 

Episodic and Continuous tasks

 

Episodic task는 종료 상태가 있는 작업을 의미

RL에서 에피소드는 초기 상태에서 최종 상태까지 agent-envrionment 상호 작용으로 간주

예를 들어 자동차 경주 게임에서 게임을 시작(초기 상태)하고 게임이 끝날 때까지 플레이(최종 상태)까지를 에피소드라고 한다.

게임이 끝나면 게임을 다시 시작하여

다음 에피소드를 시작하여 이전 게임에서 있었던 위치와 관계없이 초기 상태에서 시작한다.

따라서 각 에피소드는 서로 독립적임.

 

Continuous task 는 종료 상태가 없는 연속적인 작업을 의미한다.

예를 들어, 개인 보조 로봇에는 최종 상태가 없다.

 

Discount Factor

에이전트의 목표는 return 을 극대화하는 것이다

Episodic task의 경우 return을 다음과 같이 정의할 수 있다.

 

여기서 T는 에피소드의 마지막 상태이다.

하지만 continuous task의 경우 최종 상태가 없으므로 반환을 다음과 같이 정의 하면 합계는 무한대가 된다.

 

그렇다면 절대 멈추지 않으면 어떻게 수익을 극대화 할 수 있을까

이를 해결하기 위해 discount factor라는 개념을 도입했다.

Episodic task와 continuous task에 대한 통합 개념에서 다음과 같이 discount factor로 return을 정의할 수 있다.

 

Discount factor는 미래 보상과 즉각적인 보상에 얼마나 많은 중요성을 부여할지 결정한다.

 R 계수의 값은 [0, 1] 범위에 있다. (1보다 클 경우 현재보다 미래가 중요하다는 의미가 되므로 markov chain이 아니게 된다.)

R =0 이면 즉각적인 보상(현재)이 더 중요하며, r = 1이면 향후 보상이 더 중요함을 의미한다. R은 하이퍼파라미터(사용자가 직접 세팅하는 값)이며 일반적으로 0.2에서 0.8 사이 값을 넣는다.

 

Policy function(파이)

Policy function은 각 상태에서 수행할 행동을 의미한다. (States 에서 행동으로 매핑) 우리는 궁극적으로 각 상태에서 수행할 올바른 행동을 지정하는 최적의 정책을 찾아야 한다.

 

Value Function (State value function)

Value function 은 에이전트가 정책으로 특정 상태에 있는 것이 얼마나 좋은지 지정한다.

다음과 같이 가치 함수를 정의 할 수 있다.

Time stamp t에서 정책 파이에 따라 상태 s에서 시작하는 예상 e을 반환 Rt

 

State Value Function 상태 가치 함수는 정책에 따라 다르며 우리가 선택한 정책에 따라 달라진다.

이렇게 나타낼 수 있기에 가치함수 기반 RL을 테이블 솔루션 방법이라고 부르는 이유이다. 

 

이 두 States 의 value를 기반으로 에이전트가 정책에 따라 해당상태에 있는 것이 얼마나 좋은지 알 수 있다.

앞의 표를 기준으로 State 2에 있는 것이 값이 높기 때문에 좋다는 것을 알 수 있다.

 

State - Action value Function (Q function, Q(s,a))

에이전트가 정책 파이가 있는 상태에서 특정 작업을 수행하는 것이 얼마나 좋은지 지정한다. Q 함수(Q function)는 정책을 따르는 상태 s에서 a을 취하는 가치를 나타낸다.

 

가치함수와 Q 함수의 차이점은 가치 함수는 State 에 대한 기대값을, Q 함수는 어느 State에서 Action의 기대값을 나타낸다.

상태 값 함수와 마찬가지로 Q 함수는 표 (Q 테이블)에서 볼 수 있다. 두 가지 상태와 두 가지 동작이 있다고 가정해 보자.

Q 테이블은 다음과 같다.

 

가치 함수와 Q 함수의 차이점은 가치 함수는 State 에 대한 기대값을, Q 함수는 어느 State 에서 Action의 기대값을 나타낸다.ㅁ상태 값 함수와 마찬가지로 Q 함수는 표에서. 볼 수 있다.

두 가지 상태와 두 가지 동작이 있다고 가정해 보자.

Q 테이블을 다음과 같다.

 

Q 테이블은 가능한 모든 상태 조치 쌍의 값을 보여준다.

이 표를 보면 State1에서 Action1을 수행하고 State2에서 Action2를 수행하는 것이 가치가 높기 때문에 더 나은 옵션이라는 결론에 도달 할 수 있다.

 

Recursive Relationships in Value Function

강화학습 전반에 걸쳐 사용되는 가치 함수의 기본 속성은 다음과 같은 재귀 관계를 만족한다는 것이다.

 

 

Bellman Equation and Optimality

미국 수학자 Richard bellman의 이름을 딴 bellman 방정식은 MDP를 푸는데 도움이 된다. MDP를 해결한다는 것은 실제로 최적의 정책과 가치 함수를 찾는 것을 의미한다.

서로 다른 정책에 따라 다양한 가치함수가 있을 수 있다.

다양한 가치 함수 중에서 최적 가치 함수는 다음과 같이 모든 가치 함수와 비교하여 최댓값을 산출하는 함수로 구할 수 있다.

 

유사하게, 최적 정책은 최적의 가치 함수를 초래하는 정책이다. 최적가치 함수는 다른 모든 가치함수에비해 높은 값을 가지므로 Q 함수의 최댓값이 된다.

따라서 최적 가치 함수는 다음과 같이 Q 함수의 최댓값을 취함으로써 쉽게 계산할 수 있다.

 

Bellman 방정식의 value function은 아래와 같다.

 

아래 그림은 상태의 가치와 후속 상태의 가치 사이의 관계를 표현한 것이다. 각각의 흰 원은 상태를 나타내고 각각의 어두운 원은 상태-행동 쌍을 의미한다. 맨 위에 있는 루트 노드인 상태 s에서 시작하여 에이전트는 정책 파이에 따라 일련의 작업(다이어 그램에 3개가 표시됨) 중 하나를 수행할 수 있따.

이들 각각에서 환경을 확률 p에 의해 주어진 반응에 따라 보상 r과 함께 여러 다음 상태 중 하나인 s’로 응답할 수 있다.

Bellman 방정식은 모든 가능성에 대해 평균을 내며 각 가능성에 대해 발생 확률에 따라 가중치를 부여한다.

시작 상태의 값은 예상된느 다음 상태의 값과 그 과정에서 예상되는 보상을 더 한 값과 같아야 한다.

 

 

Value iteration은 처음 시작시 랜덤 한 함수로 초기화한다.

당연히 랜덤 값 함수는 최적값 함수가 아닐 수 있으므로 최적 값 함수를 찾을 때 까지 반복적인 방식으로 새롭게 개선된 값 함수를 찾는 알고리즘이다.

이를 통해 최적의 가치 함수를 찾으면 최적의 정책을 쉽게 도출할 수 있다.

 

Policy iteration

Policy iteration은 무작위 정책으로 시작한 다음 해당 정책의 가치함수를 찾는다.

가치함수가 최적이 아니면 새로운 개선된 정책을 찾도록 최적의 정책을 찾을 때 까지 이 과정을 반복하는 알고리즘이다.

정책 반복할때 정책 평가와 정책 개선이라는 두단계를 거친다.

정책 평가는 무작위로 추정한 정책의 가치함수 평가하는 단계와 정책개선은 가치함수를 평가하여 최적이 아닌 경우 새로운 개선정책을 찾는 단계이다.

 

Step

1. 먼저 랜덤 정책을 초기화한다.
2. 그런 다음 해당 무작위 정책에 대한 가치 함수를 찾고 최적인지 확인하기 위해 평가한다. 이를 정책 평가라고 한다.
3. 최적이 아닌 경우 정책 개선이라는 새로운 개선 정책을 찾는다.
4. 최적의 정책을 찾을 때까지 이 단계를 반복한다.

 

Frozen Lake Problem

MDP를 DP로 푸는 대표적인 예시이다.

집에서 사무실까지 이어지는 얼어붙은 호수가 있고 사무실에 가려면 얼어붙은 호수 위를 걸어야 한다. 하지만 얼어붙은 호수에는 구멍이 있으므로 구멍에 갇히지 않도록 얼어붙은 호수 위를 걷는 동안 조심해야 한다.

S는 집이자 시작 위치, F는 걸을 수 있는 얼은 호수 위, H는 조심해야 할 구멍, G는 목표이자 사무실이다.

 

• 이 환경에서의 에이전트의 목표는 H에 갇히지 않고 S에서 G로 가는 최적 경로를 찾는 것이다
• 에이전트가 얼어붙은 호수 위를 올바르게 걸으며 보상으로 +1점을 주고 구멍에 빠지면 0점을 주어 에이전트가 올바른 행동을 결정할 수 있도록 한다.
• 에이전트는 이제 최적의 정책을 찾으려고 노력할 것이다.
• 최적의 정책은 에이전트의 보상을 극대화하는 올바른 경로를 취하는 것을 의미한다.
• 에이전트가 보상을 최대화 하는 경우 분명히 에이전트는 구멍을 건너뛰고 목적지에 도달하는 방법을 배우고 있는 것이다.

 

문제를 MDP로 모델링 할 수 있다.

• States: 상태 집합이며 여기에는 16개의 상태가 있다.
• Actions: 가능한 모든 액션 세트(왼쪽, 오른쪽, 위, 아래)
• Transition probabilties(전이 확률): 행동을 수행함으로써 한 상태에서 다른 상태로 이동할 확률
• Rewards probabilities: 행동 a를 수행하여 한 상태에서 다른 상태로 이동하는 동안 보상을 받을 확률

 

 

Import gym

Import numpy as np

Import IPython import display

Import matplotlib.pyplot as plt

Import time

%matplotlib inline

 

env = gym.make(“FrozenLake-v0”)

Env = env.unwrapped

 

env.render()

 

def value_iteration(env, gamma=1.0):

value_table = np.zeros(env.observation_space.n)

 

no_of_iterations = 10000

threshold = 1e-20

 

for I in range(no_of_iterations):

updated_value_table = np.copy(value_table)

 

for state in range(env.observation_space.n):

next_states_rewards = []

for next_sr in env.P[state][action]:

trans_prob, next_state, reward_prob, _ = next_sr

next_states_rewards.append((trans_prob * (reward_prob + gamma * updated_value_table[next_state])))

 

Q_value.append(np.sum(next_states_rewards))

 

value_table[state] = max(Q_value)

 

if(np.sum(np.fabs(updated_value_table - value_table)) <= threshold):

print(“value iteration converged at iteration# %d.” % (I+1))

break

 

return value_table

 

 

 

Def