【알고리즘】 11강. 강화학습

11강. 강화학습(reinforcement learning; RL)

 

추천글 : 【알고리즘】 알고리즘 목차 

---

1. 개요 [본문]

2. Markov decision process [본문]

---

 

1. 개요 [목차]

⑴ 정의

① (참고) supervised learning

○ 데이터 : (x, y) (단, x는 feature, y는 label)

○ 목표 : 맵핑 함수 x → y의 계산

② (참고) unsupervised learning

○ 데이터 : x (단, x는 feature이고 label은 없음)

○ 목표 : x의 underlying structure에 대한 학습

③ reinforcement learning

○ 데이터 : (s, a, r, s') (단, s는 state, a는 action, r은 reward, s'은 다음 상태)

○ 목표 : 여러 시간에 걸친 reward의 총합을 최대화

⑵ 특징 : supervised learning, unsupervised learning과는 차별성이 있음

① 정답을 묵시적으로 제공받음 : reward의 형태로 제공받음

② 환경과의 상호작용을 고려해야 함 : delayed feedback 등이 문제가 됨

③ 이전의 결정이 미래의 상호작용에 영향을 줌

④ 적극적으로 정보를 얻는 알고리즘 : 강화학습은 데이터를 얻는 과정까지를 포함함

⑶ 요소 1. reward

⑷ 요소 2. policy

① 정의 : agent의 행동. 즉, state를 입력으로 action을 출력으로 하는 맵핑

② 종류 1. deterministic policy

③ 종류 2. stochastic policy

○ 이유 1. learning에서 최적의 행위를 모르므로 exploration을 하기 위함

○ 이유 2. 최적의 상황이 stochastic한 걸 수도 있음 (예 : 가위바위보, 상대방이 역이용하는 경우)

⑸ 요소 3. value function

① 정의 : 미래의 reward에 대한 기댓값

② 수식화 : state s, policy π, 미래가치를 현재가치로 보정하기 위한 계수 γ에 대하여,

 

 

③ state가 좋은지 나쁜지를 평가하여 action을 선택하는 근거를 제공

⑹ 요소 4. model

① 정의 : 환경(environment)의 행동

② 주어진 state와 action에 대하여 model은 다음 state와 reward를 결정함

③ model-free method와 model-based method가 있음을 유의

 

 

2. Markov decision process [목차]

⑴ 정의 : transition과 관련하여, t+1에서의 상태가 오직 t에서의 상태의 함수로 결정되는 것

① state : s_t ∈ S

② action : a_t ∈ A

③ reward : r_t ∈ R(s_t, a_t)

④ policy : a_t ~ π(· | s_t)

⑤ transition : s_t+1 ~ P(· | s_t, a_t)

⑥ 사실상 거의 대부분의 문제 상황이 Markov decision process에 해당함

⑵ 종류 1. Q-learning

① 정의 : 모든 state에 대하여 value function V^π(s)를 학습하는 것

○ transition probability P(s' | s, a)는 알려져 있지 않음

○ reward function R(s, a)는 알려져 있지 않음

② 방법 1.

○ 모든 state / action pair의 추정량을 초기화 : Q̂(s, a) = 0

○ 초기 반복 scheme

○ 랜덤한 action a를 취함

○ 다음 상태 s'를 관찰하고 환경으로부터 R(s, a)를 받음

○ Q̂(s, a)를 업데이트

○ 후기 반복 scheme

○ a = arg max_a Q̂(s, a)를 취함

○ 다음 상태 s'를 관찰하고 환경으로부터 R(s, a)를 받음

○ Q̂(s, a)를 업데이트

 

 

○ random restart

③ 방법 2. ε-greedy (epsilon greedy)

○ 모든 state / action pair의 추정량을 초기화 : Q̂(s, a) = 0

○ 반복 scheme

○ 1 - ε의 확률로 a = arg max_a Q̂(s, a)를 취하고, ε의 확률로 random action을 취함

○ 다음 상태 s'를 관찰하고 환경으로부터 R(s, a)를 받음

○ Q̂(s, a)를 업데이트

 

 

○ 후기 반복일 경우 random restart

④ DQN(deep Q-network)

○ 정의 : Q learning을 deep learning으로 구현한 것

○ 수많은 게임에 적용됨 : DQN on Atari 2600 (2013), AlphaGo (2016) 등

⑶ 종류 2. policy gradient

① 정의 : policy π(s)를 직접 학습하는 것

② 특징

○ Q-learning은 state가 continuous해도 되는 반면 action은 discrete해야 함

○ policy gradient는 action 및 state가 continuous해도 됨

③ 알고리즘

○ step 1. frame을 받음

○ step 2. P(action)을 얻기 위해 forward를 propagate함

○ step 3. P(action)으로부터 a를 샘플링

○ step 4. 게임의 나머지를 진행

○ step 5. 만약 게임에서 이기면 ∇_θ 방향으로 진행

○ step 6. 만약 게임에서 지면 -∇_θ 방향으로 진행

⑷ 기타 종류

① deep O-network (DON)

② A3C 

③ genetic algorithm

④ SARSA 

 

 

입력: 2021.12.13 15:20