ch1. The Reinforcement Learning Problem 2 (Introduction)

https://dogunkim.tistory.com/62

ch1. The Reinforcement Learning Problem 1 ((Introduction))

 

<목차>

1.1 Reinforcement Learning 
 1.2 Examples 
 1.3 Elements of Reinforcement Learning 
 1.4 Limitations and Scope 
 1.5 An Extended Example: Tic-Tac-Toe 
 1.6 Summary 
 1.7 History of Reinforcement Learning 
 

 

1.4 Limitations and Scope 

 강화학습은 상태((state))에 크게 의존하게 된다. 상태는 정책((policy))와 가치 함수((value-function))의 입력이 되기도 하고, 모델의 입력과 출력이 되기도 하기 때문이다.

 

 이러한 상태는 ch3에서 더 자세하게 정의하겠지만, 비공식적 의미로 학습자가 사용할 수 있는 환경에 대한 모든 정보를 상태로 생각하는 것이 좋다. 

 

 이 책에서는 의사 결정 문제에 초점을 맞추기 위해 상태를 구성하고 변화시키거나 학습하는 것을 다루지 않는다. 

 

 

---

1.5 An Extended Example: Tic-Tac-Toe 

 

 강화학습의 일반적인 개념을 이해하고 차이점을 보기 위해 Tic-Tac-Toe 예시를 확인해보자. 그냥 쉽게 말해서 한국으로 치면 오목을 둔다고 생각하면 된다. 3개의 같은 대각선을 만든 사람이 게임에서 이기게 된다.

 

 어떻게 하면 상태방의 잘못된 선택을 찾아내고 승리할 확률이 최대로 하는 법을 배우는 학습자를 만들 수 있을까? 이를 풀기 위한 방법으로 i) 기존에 자주 사용되던 접근법인 간단한 min-max 알고리즘, 동적 프로그래밍 같은 방법을 생각할 수 있지만 이로는 최적해를 구할 수 없거나, 구하기 위한 더 많은 조건들이 필요하게 된다. 

 

cf. i) 기존 접근법의 한계 

• 미니맥스(minimax): 상대방의 특정한 플레이 방식을 가정하므로 부적합.
• 동적 계획법(DP): 상대의 모든 움직임 확률을 알아야 함. 이는 실질적인 문제에서는 대부분 불가능.

 ii) 유전 알고리즘과 같은 진화적 방법을 적용할 수도 있다. 이 때 게임 참여자는 가능한 모든 정책들을 직접 탐색하여 상대방을 이길 확률이 가장 높은 것을 찾으려고 할 것이다.  여기서의 정책은 모든 O, X의 조합마다 어떠한 선택을 해야하는 지를 알려주는 각각의 정책이다. 이길 확률이 높은 정책을 찾아갈 것이다. 

https://untitledtblog.tistory.com/110

[수리적 최적화] 유전 알고리즘 (Genetic Algorithm)과 전역 최적화

 

 iii) 가치 함수((value-function))를 사용하여 틱택토 문제를 접근할 수도 있다. 이를 위해 게임에서 나타날 수 있는 모든 상태((state))에 해당 상태의 게임 참여자가 승리할 확률에 대한 가장 최신 추정값을 부여한다. 이 추정값은 앞에서 말한 가치((Value))으로 생각할 수 있다. 상태 B보다 A가 승리할 확률이 높다면 A의 가치가 더 높을 것이며 이미 같은 O 혹은 X로 빙고가 완성된 상태는 가치가 1 또는 0일 것이다. 모든 상태의 초기 가치는 0.5로 설정한다.

 

 X 표시를 하는 입장이라고 생각해보자. 게임 참여자는 X를 표시할 위치를 확인하기 위해 자신의 행동으로 불러올 상태들을 면밀하게 따져보고 가치를 확인한다. 이 때 승리 확률 추정치를 최대로 하는 상태로 가기 위해 탐욕적으로 선택한다.

실선은 게임 도중에 취해진 이동, 점선은 강화학습을 이용하는 게임 참여자가 고려했지만 선택하지 않은 이동

  게임을 하는 동안 간혹 탐욕적으로 선택하는 것이 아닌, 무작위로 표시할 위치를 선택하기도 한다. 이를 탐욕적 선택이라고 하며 위 그림에서 e*가 가치 함수가 가장 높아지는 선택이였지만, 무작위로 e를 선택하는 것이 바로 탐욕적 선택이다.

탐험과 활용: 강화학습의 핵심

강화학습에서 **탐험(Exploration)**과 **활용(Exploitation)**은 학습의 두 가지 중요한 요소다.

1. 활용(Exploitation)
   • 탐욕적 선택(Greedy Selection): 현재 상태에서 가장 높은 보상을 기대할 수 있는 행동을 선택.
   • 목표: 기존에 학습된 정보를 활용해 즉각적인 보상을 극대화.
   • 예: 틱택토에서 승리 확률이 가장 높은 칸에 X를 놓는다.
2. 탐험(Exploration)
   • 새로운 행동을 시도하거나 경험하지 못한 상태를 탐색.
   • 목표: 더 나은 가능성을 발견하고 학습의 폭을 넓힘.
   • 예: 승리 가능성이 낮아 보이는 칸을 일부러 선택해 상태를 탐색.
3. 균형의 중요성
   • 탐험만 하면 학습이 느리고 비효율적.
   • 활용만 하면 새로운 가능성을 발견하지 못하고 국소 최적해에 갇힐 위험.
   • 이를 조화롭게 조절하는 것이 강화학습의 핵심이다.

 

 게임을 하는 동안 참여자는 자신이 처한 상태의 가치를 계속해서 변화시킨다. 즉 그 가치가 승리 확률에 대한 더 정확한 추정이 되도록 노력하는 것이다. 위 그림에서 *를 선택한 탐욕적 선택 이후 결정될 상태의 가치를 선택 이전의 상태에 backup한다. 이전 상태의 현재 가치가 나중 상태의 가치에 가까워지도록 갱신될 것이다. 이는 다음과 같은 수식으로 표현할 수 있다.

 $s^'$은 탐욕적 선택 이후의 상태, (s)는 탐욕적 선택 이전의 상태이며, V는 가치 함수이다.  α는 step-size parameter라고 불리는 시간 간격 매개 변수로 학습 속도에 영향을 준다. 이러한 방법은 두 연속적신 시각의 추정값 차이에 기반하여 계산되기 때문에 시간차 학습이라고 불린다. 이는 미래의 상태에 기반하여 현재 상태를 평가하는 강화학습의 중요한 특성을 보여준다. 

상태 값 업데이트: 시간차 학습(TD Learning)

틱택토에서 강화학습은 시간차 학습(Temporal Difference Learning) 방식을 사용해 상태 값을 지속적으로 업데이트한다.

1. 학습 과정:
   • 특정 상태 s에서 움직인 후 새로운 상태 s′로 이동한다.
   • 이후 상태 s′의 승리 확률 값을 기준으로 현재 상태 s의 값을 업데이트한다.
2. 업데이트 공식:V(s)←V(s)+α⋅(V(s′)−V(s))
   • V(s): 현재 상태 s의 값. ex) 0.5
   • V(s′): 다음 상태 s′의 값. ex) 0.8
   • α: 학습률(step-size parameter). 학습 속도를 조절하는 작은 양수. ex) 0.1
3. 시간차 학습의 장점:
   • 미래 상태를 기반으로 현재 상태를 평가한다.
   • 동적인 환경에서도 학습이 가능하다.

 

 ii) 진화적 방법이나 iii) 가치 함수를 사용하는 방법 모두 정책((policy))을 탐색하는 공통점을 갖는다. 하지만 진화적 방법은 게임 도중의 과정은 무시하며 최종 결과만을 사용하고, 가치 함수를 사용하는 강화 학습의 방법은 개별적인 상태들을 평가하며, 게임 도중에 발생한 정보를 활용한다는 이점을 갖는다.

 

이러한 간단한 예제를 통해 강화 학습의 몇 가지 핵심 특성을 설명할 수 있다.

1. 환경과의 상호작용을 통한 학습:
   • 강화학습은 플레이 중 환경(상대방)과 상호작용하며 학습을 진행한다.
2. 강화학습에는 확실한 목표가 존재하고, 올바른 행동을 위해 지연된 효과를 고려하는 계획 또는 예지가 필요함:
   • 강화학습은 현재 행동이 미래에 미칠 영향을 고려한다.
   • 틱택토에서는 여러 수를 앞서 내다보며 전략을 수립하는 '계획' 효과를 학습한다.
3. 모델 기반 vs 모델 비사용:
   • 모델 기반 학습: 환경의 변화를 예측하여 계획적으로 행동한다.
   • 모델 비사용 학습: 환경 모델 없이 시행착오를 통해 학습한다.

실제로 취하지 않을 선택에 대해 환경이 어떻게 변할지를 예측할 수 있도록 하는 모델이 존재하여 게임 참여자는 앞을 내답고 자신의 선택에 따른 상태의 결과를 알 수 있었다. 

 

   4. 대규모 문제에도 적용 가능:

• 단순한 틱택토뿐만 아니라, 상태 공간이 매우 큰 문제(예: 백개먼)에도 적용 가능하다.
• 인공신경망과 결합하면 새로운 상태에서도 과거 경험을 일반화하여 학습 성능을 향상시킬 수 있다.

 

 

---

1.6 Summary

강화학습(Reinforcement Learning)은 목표 지향적인 학습과 의사결정을 자동화하고 이해하기 위한 계산적 접근법이다. 이 방법은 환경과의 직접적인 상호작용을 통해 학습하는 데 초점을 맞추며, 다음과 같은 특징을 갖는다.

 

• 탐험을 통한 학습
  • 강화학습에서는 지도 학습처럼 정답(label)이나 완전한 환경 모델에 의존하지 않는다.
  • 에이전트(agent)가 환경(environment)과 상호작용하며 얻은 경험을 통해 학습한다.
• 장기 목표 추구
  • 강화학습은 단기적인 보상이 아닌 장기적인 목표를 달성하기 위해 설계되었다.
  • 에이전트는 현재의 행동이 미래에 미칠 영향을 고려하며 학습한다.
• 환경과의 상호작용 정의
  • 강화학습은 상태(states), 행동(actions), 보상(rewards)으로 구성된 정형화된 프레임워크를 사용한다.
  • 이 프레임워크는 인공지능 문제의 핵심 요소를 단순하고 명확하게 표현한다.
    • 원인과 결과: 행동이 결과에 미치는 영향을 학습.
    • 불확실성과 비결정성: 환경의 예측 불가능성을 포함.
    • 명시적인 목표: 보상을 통해 학습의 목표를 명확히 정의.

 

또한 특정 상태에서 장기적으로 얻을 보상의 기대치를 나타내는 가치 함수는 효율적인 정책 탐색을 위한 중요한 요소이며, 강화 학습의 핵심이라고 볼 수 있다.

 

 

 

---

1.7 History of Reinforcement Learning 

이건 그냥 읽어보고 넘어가자.. 책 내용을 간단하게 요약해놨다.

주요 흐름

1. 시행착오 학습(Trial-and-Error Learning)
   • 심리학적 배경: 동물 행동 연구에서 시작.
     • Edward Thorndike의 효과의 법칙(Law of Effect): 만족을 주는 행동은 강화되고, 불쾌한 행동은 약화된다.
     • B.F. Skinner: 행동의 강화 원리를 실험적으로 확립.
   • 인공지능 초기 적용:
     • Alan Turing(1948): 쾌-고통 시스템 설계.
     • Claude Shannon(1952): Theseus 미로 해결 로봇.
     • Donald Michie(1961): MENACE(틱택토 학습 시스템).
2. 최적 제어와 동적 계획법(Optimal Control & Dynamic Programming)
   • 수학적 배경:
     • Richard Bellman(1950s): 벨만 방정식과 동적 계획법(DP) 개발.
     • Markovian Decision Processes(MDP): 확률적 최적 제어 문제를 정의.
   • 한계: 환경 모델이 필요하고, 계산 복잡도가 높아 실제 학습에 제한적.

---

2. 중요한 통합 요소

1. 시간차 학습(Temporal-Difference Learning)
   • Arthur Samuel(1959): 체커 게임에서 시간차 학습 개념 적용.
   • Sutton과 Barto(1980s): TD 학습을 강화학습의 핵심으로 발전.
   • Chris Watkins(1989): Q-러닝 개발, 강화학습의 세 가지 흐름 통합.
2. 신경망과의 결합
   • 1990s: TD-Gammon(Backgammon 프로그램)으로 큰 성공(Gerry Tesauro).
   • 강화학습과 도파민 뉴런 활동의 유사성이 신경과학 발전에 기여.

---

3. 최근 발전

• 강화학습은 심리학, 경제학, 게임 이론, 신경과학 등 다양한 분야와 융합되며 빠르게 발전.
• Q-러닝, Actor-Critic, 신경망 기반 알고리즘 등으로 강화학습의 적용 범위 확장.
• TD 알고리즘과 도파민 활동 간의 유사성으로 신경과학 연구 활성화.

---

결론

강화학습은 시행착오 학습, 최적 제어, 시간차 학습의 흐름이 결합된 결과이다. 현재는 인공지능, 신경과학, 경제학 등 여러 분야에서 핵심적인 역할을 하고 있다.