reinforcement learning (Q-learning algorithm) [algorithm] by 바죠

reinforcement learning (강화 학습)
https://en.wikipedia.org/wiki/Reinforcement_learning
https://en.wikipedia.org/wiki/Q-learning
https://en.wikipedia.org/wiki/State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action
http://hunch.net/~beygel/deep_rl_tutorial.pdf

강화학습은 machine learning의 한 방법으로서 최근 각광받고 있다. 보상이 동작들 보다 훨씬 뒤에 나타나는 경우에 대한 문제 풀이이다. 예를 들어 바둑과 같은 경우이다. 주어진 환경하에서 무슨 행동을 하여야 최종적으로 최고의 보상을 받을 수 있을까? 이 문제를 푸는 것이다. 아주 일반적인 문제이다. 이러한 문제들에 대한 일반적인 문제풀이 방식이 있을까?

우선 환경이 있다. 상태가 있고 그 상태에서 특정 행동을 하면 환경은 새로운 상태를 주게 된다. 아울러 보상을 주게 된다. 이 보상은은 최종 보상이 될 수도 있다. 물론, 최종 보상이 아닐 수도 있다. 이런식으로 여러 가지 에피소드들이 가능하다. 많은 에피소드들을 통해서 어떻게 행동하면 최종적으로 최고의 보상을 얻을 수 있을까?

상황은 조금 달라도, 아마도 매우 많은 사람들이 고민해 보았던 문제일 것이다.

기술적으로 이 분야의 역사는 깊다고 한다. 하지만, 실제 구현에서 놀라운 결과를 내기 시작한 것은 최근의 일이다. 실질적인 구현에서 기술적 발전이 있었다고 한다. 발전에 기여한 방법의 변형은 알고나면 매우 간단한 것이다. 하지만, 그것이 알려지지 전까지는 해당 분야가 꼼짝을 못하고 있었던 것이다.  매우 큰 기대를 갖게하는 일이 알파고 제로의 출현이다.
http://incredible.egloos.com/7372719

이전의 알파고와 달리 알파고 제로는 백지상태(tabula rasa)로부터 스스로 바둑의 정석을 학습한다.
사람들이 둔 기보를 보고 이기는 방법을 배우는 지도학습을 하지 않는다.
바둑의 승패와 관련된 룰만 가르쳐 주고 경기에서 이기는 방법을 스스로 학습하는 것이다. 스스로 바둑을 두어 보고 이기는 방법을 찾는 것이다.  사람들이 수행했었던 경기를 보고 배우는 것이 아니다. 어쩌면 사람들이 모르는 정석이 있을 것이다. 실제 알파고 제로는 사람들이 발견하지 못했었던 정석들을 스스로 찾아낸 것이다. 다시 말해서, 사람들을 능가하게 된 것이다.   





-------------------------------------------------------------------------------------------------------------------


frozen lake 예제를 이용한 알고리듬 이해.

우선 16개의 상태가 있다.

(1,1) 위치에서 시작하여 (4,4)위치에 도달하면 성공하는 게임이다. agent는 현 상태(state)만 볼 수 있다. next state를 볼 수 없다. 행동을 하면 볼 수 있다. 행동하지 않으면 정보를 얻을 수 없다는 것을 가정한다. 행동할 때마다 대부분 reward가 0이다. 다만, 목표에 도달할 때, reward(1)가 있다.  물론, 홀에 빠질 때, reward(-1)를 주고 게임이 끝난다.
action :  right, left, up, down 4 가지 행동들이 가능하다. 많은 상태들에서 그렇다. state, reward를 환경이 제공한다. 게임이 끝난는지 아닌지도 환경이 제공한다.  대부분의 상태들은 reward(0) 를 준다. 결국, 게임은 state, action, reward, next state, done 와 같은 식으로 돌아간다. 매 상태마다 게임이 끝인지 아닌지를 done이라는 변수를 통해서 체크할 수 있다.
문제에서 사용한 가정과 문제풀이 상황 등은 충분히 일반적인 것들로 받아들여질 수 있다.


Q-learning (몇 가지 행동들을 취하므로써 reward들의 값들을 상태들에 대해서 구하고자 하는 것이다. 최적의 행동 선택 학습 알고리듬이다. 동작-가치 함수= Q)
https://en.wikipedia.org/wiki/Q-learning

모든 상태들에 대한 Q값을 초기화한다.
행동들을 수행함으로써 배우고자 한다. 상태들의 Q 값을 update하는 방식이다.
현재 상태, 작업을 한 이후
Q  <------------ r
처럼 당연히 현 상태에서의 reward가 Q 값으로 적혀야 할 것이다. 현 상태의 reward를 얻고자 했었다.
Q  <------------   r   +   max _a' Q (s', a')
                         현재 상태로 부터 reward, r,   미래의 action들 중에서 가장 큰 Q 값을 주는 것 선택한다.

당연히 이 값도 일종의 reward이다. 게임이 끝나는 경우 단순하게 reward 값만을 얻게된다. done=yes가 되고 next state가 없기 때문이다. done=no 이면 당연히 게임은 진행중이다. 따라서 next state를 state로 변환한다.
nexst state는 state로 변환될 것이다.

결국, 모든 상태들마다 Q 값들이 정의 갱신될 것이다. 이렇게 간단한 문제의 경우, 상태들이 나열되고 해당 Q값들을 전시할 수 있다. 즉, Q-table이 만들어진다. 예상되는 최종적인 reward들이 만들어지는 것처럼 보인다.

for each s, a initialize table entry Q=0

s ---> s'
Q update 현재 상태

r 그리고 s' 상태의 max _a' Q(s',a')를 이용해서 update함,

exploitation and exploration (E & E) : epsilon-greedy

epsilon=0.1
if random_value <epsilon:
   a = random action
else
   a=argmax Q(s,a)   최고 Q값을 주는 action 선택

explotation and exploration : decaying epsilon-greedy

학습 초기 random action으로 진행, 후기에는 random action을 많이 사용하지 않고, 최대값을 주는 action 위주로 진행한다.

for i in range (1000)
   epsilon=0.1/(i+1)
   if random_value < epsilon
       a=random action
    else
       a=argmax  Q(s,a)   특별한 action 선택, 최고 Q 값을 주는 action 선택함.


-------------------------------------------------------------------------------------------------------------------
exploitation and exploration : add random noise

a=argmax Q(s,a) + random_values/(i+1)

1 등이 아니라,  이번에는 2 등 또는 3 등도 한 번 시도해보자는 뜻.

Learning Q(s,a) with  discounted reward

Q  <------------- r   +    0.9 * max _a' Q(s',a')
상을 받는 것 중에서, 빨리, 즉시 받는 것을 더 존중한다는 뜻. 
상태들에 따라서 Q 값들이 기울기를 가지면서 생성되게 만들어준다.
목적지에 가까운 상태들이 큰 Q 값을 가지게된다.

Windy frozen lake
nondeterministic case

Q(s,a) <---------- (1-alpha) Q(s,a) + alpha *(r+gamma*max _a' Q(s',a'))  또는
Q(s,a) <----------- Q(s,a) +alpha*(r+gamma*max _a' Q(s',a') -Q(s,a) )
learning rate : alpha

Q-learning algorithm

Q--0
s
a (E&E 방식으로 선택)
Q를 업데이트함, alpha 사용


-------------------------------------------------------------------------------------------------------------------

Q-table (?)
상태마다 모두 table 을 만들 수 없다. 왜나혀면, array size가 너무 커지는 문제 발생한다.
실제 문제들에서 Q-table을 사용하는 것은 사실상 불가능하다. 결국, 사람들은 network을 사용하게 된다.
network을 사용하면서 문제가 발생한다. 동작-가치 함수 Q 값을 만드는데 실패하게 된다.
동작-가치 함수 Q 값을 잘 표현하는데 실패한다.  DQN 방법으로 극복으로 이 문제를 극복한다.

Q-function approximation

state, s
action, a     layer ---- layer ----- layer ----      quality (reward) for all actions

state, s, action a -----> q-value,
state, s  -------------------->  q-values for all  actions
         s           --->                   Ws

y = r + gamma * max _a' Q(s',a')

cost(W) = (Ws-y)**2

Ws = Q(s,a|theta)  ~ Q(s,a)

min theta \sum {Q(s,a|theta)-(r+max Q(s,a|theta))}^2

-------------------------------------------------------------------------------------------------------------------

y_j = r_j
    또는
        r_j + gamma * max Q(phi(j+1), a'; theta)

(y_j-Q(phi(j+1),))**2


reinforcement + NN
diverge 문제가 있음.

이 문제 해결 방법: DQN
DQN : Deep, Replay, Separated networks


Q-network training
observation --> input size
action  --->  output size

Ws, Q-prediction

(Ws-y)^2

(Qpred-y)^2
                         다음 상태에서 얻을 수 있는 최고값.
y = r + gamma *max Q(s')
label/target

network이 학습함.

Q table의 경우 잘 동작함. Q network의 경우 발산

Q network의 발산 문제점을 극복하는 방법.
DQN 방법으로 극복함.
DQN: Deep, replay, separated networks

random sampling
nonstationary targets
separate target network, target network, main network

Sample을 모을 때는 최근의 transition을 선택하는게 아니라 replay memory에 저장된 transition 중 무작위로 minibatch size만큼의 sample을 선택한다.
다양한 상황에서 얻은 transition을 sample로 사용하므로 특수한 상황에 치우치지 않은 Q-value를 얻어낸다는 것이다.

DQN에서 사용하는 Q networks는 사실 2개이다.
하나는 target Q network이고 다른 하나는 Q network이다.
target Q network를 별도로 두는것이 특징이다.
두 networks는 weight parameter만 다르고 완전히 같은 network이다.
target network는 계속 update되는 것이 아니라 주기적으로 한번씩 update하도록 되어 있다. 연속적인 것을 사용하는 것이 아니다.

타겟 신경망의 가중치는 고정되고, 단지 주기적으로나 천천히 기본적인 Q-network의 값들을 업데이트 한다. 이런 방식에서 학습이 더 안정적인 방식에서 진행할 수 있다.

DQN 2013
DQN 2015

policy gradient
Q-function is very complicated.
optimal policy
reinforce algorithm
J(theta)
gradient _theta J


CNN with a variant Q-learning
Experience replay

Experience Replay

개념적으로는 미니배치(mini-batch)와 유사하다. 먼저 게임 과정의 전이 <s, a, r, s’>들을 모두 replay 메모리에 저장한다.
학습단계에서 최신 전이들을 하나씩 사용하는 대신, replay 메모리에서 랜덤으로 여러개를 선택해서 학습하는 방식이다.

epsilon-greedy exploration

기본적으로는 가장 높은 Q값을 가지는 action을 선택하고, 일정 확률(epsilon)로 랜덤으로 액션을 선택하도록 하는 방법이다. 딥마인드의 경우 학습이 진행되면서 epsilon의 값을 1에서 0.1로 점진적으로 감소시켰다. 따라서 학습 초기에는 무작위로  action을 선택할 확률이 높고, 학습이 진행되어 Q함수가 수렴하게 되면 exploration(탐험적인 활동)은 고정된 비율로만 진행된다.



이미지 출처: 구글 이미지
agent, enviroment

state
action
reward
next state

retarded reward

find  pi(s)              find Q(s,a)
a ~ pi(s)                a=arg max_{ a' } Q(s,a')

Q^* (st,at)   =  max_{pi}  E()

approximate Q^* function

Q_theta (s,a|theta) ~ Q^*(s,a)
and choose theta to minimize ||Q_theta (s,a|theta) -(rt +gamma*Q())   ||

pi* (s) = arg a max Q^*(s,a)

Deep RL

use depp NNs to represent
value function
policy
model

현재 상태에 대한 모델의 큐함수
다음 상태에 대한 모델의 큐함수

상태가 입력, 큐함수가 출력인 인공신경망 생성

state         ----->     target
next_state  ---->      target_val

둘 중 하나:
target[i][action[i]] = reward[i]

target[i][action[i]] = reward[i] + gamma * argmax (target_val[i])

state  vs target   : fitting

현 상태
action

next_state, reward, done, info
if done

state, action, reward, next_state, done

score, epsiode
for each episode
  action
   next_state, reward, done, info

Deep reinforcment learning with double Q-learning
https://arxiv.org/pdf/1509.06461.pdf

--------------------------------------------------------------------------------------------------------------------
http://incredible.egloos.com/7167212

--------------------------------------------------------------------------------------------------------------------


핑백

덧글

  • dyanos 2018/02/17 23:57 # 삭제 답글

    오오 박사님도 Reinforcement Learning 공부하시는 건가요?? ㄷㄷ
  • 바죠 2018/02/18 08:52 # 삭제

    dyanos 안녕하세요?
    이것 조금 해보고 있습니다.
    요즘 어떻게 지내시는지?
    이 교수님께서는 알파고 개발 중이십니다.
댓글 입력 영역

최근 포토로그