RL: 3. Dynamic Programming

큰 문제를 작은 문제로 쪼개고, 작은 문제의 해답을 저장해두는 알고리즘

안녕하세요- 오랫만에 강화학습 덕질하려고 글을 쓰기 시작했습니다 ㅎㅎ

이번 포스팅에선 강화학습의 기초, 다이내믹 프로그래밍에 대해 이야기해보려고 합니다.

Dynamic Programming의 기초에 대해 다루어보도록 하겠습니다.

Markov Decision Process를 푸는 3가지 방법

MDP(Markov Decision Process) 혹은 MRP(Markov Reward Process)를 푸는 방법에는 3가지가 있다고 저번 포스팅에서 설명드렸는데요. 세 가지 방법 중 첫번째가 Dynamic Programming입니다. 

 - 다이내믹 프로그래밍(Dynamic programming)
 - 몬테카를로 측정(Monte-Carlo evaluation)
 - 시간차 학습(Temporal-Difference learning)

리차드 서튼 교수님은 Dynamic Programming, Monte Carlo methods, 그리고 Temporal-Difference Learning에 대해서 각각 장점과 단점이 있다고 합니다.

Dynamic Programming:

수학적으로 잘 정의되어 있습니다.
하지만 환경을 반영할 수 있는 정교한 모델이 있어야만 합니다.

Monte Carlo Method:

모델이 필요하지 않고, 직관적으로 단순합니다.
하지만, 시간에 따른 (step-by-step) 계산에는 적합하지 않습니다.

Temporal-Difference Methods:

모델이 필요하지 않고, 시간에 따른 (step-by-step) incremental한 연산에 적합합니다.
하지만, 분석하기엔 더 복잡합니다.

Dynamic Programming이란? 

Dynamic Programming은 수학적 최적화(Mathematical optimization) 방법이며, 컴퓨터 프로그래밍 방법론입니다. Dynamic Programming은 Richard Bellman에 의해 1950년대에 발명되었습니다.

네 그 Bellman 맞습니다. 강화학습 공부하다보면 주구장창 나오는 Bellman Equation의 Bellman입니다. 그리고 컴퓨터 프로그래밍 방법론은 우리가 알고리즘 공부할 때 나오는 DP문제 맞습니다.

Richard E. Bellman (출처: wikipedia)

수학적 최적화, 컴퓨터 프로그래밍 방법론 두 가지 모두 비슷한 맥락을 갖고 있습니다.

Dynamic Programming의 기본 컨셉은
크고 복잡한 문제를
여러 개의 단순한 작은 문제들로 쪼개는 것입니다.

만약에 작은 문제들이 재귀적으로 어떤 큰 문제에 포함될 수 있다면, 다이나믹 프로그래밍을 적용할  수 있습니다. 이 때, 작은 문제들 값(value)과 큰 문제의 값(value) 사이에 관계가 생기게 됩니다. 최적화 이론에서는 이 둘 사이의 관계를 Bellamn Equation으로 정의합니다.

최적화 이론의 관점에서, 다이나믹 프로그래밍은 일반적으로 의사결정(decision)을 시간에 따른 작은 의사결정(decision)들로 단순화하는 것을 말합니다.

Dynamic Programming은 아래 두 가지 특징을 갖는
문제들을 위한 일반적인 솔루션입니다.

- 최적 하부 구조(Optimal Substructure)

최적화의 원칙(Principle of optimality)이 적용될 수 있음
Optimal solution은 여러 개의 작은 문제들로 분해될 수 있습니다.

- 중복되는 하위 문제들(Overlapping subproblems)

작은 문제들은 여러 번 반복될 수 있습니다.
솔루션들은 캐싱되고 다시 사용될 수 있습니다.

최적화의 원칙(Principle of optimality)는
다음 포스팅에 자세히 설명드리도록 하겠습니다. 

Markov Decision Process(MDP)는
Dynamic Programming에 필요한 위 두 가지 특징을 갖고 있습니다.

- 최적 하부 구조(Optimal Substructure): 

Bellman Equation은 Optimal Substructure 특성을 활용해
재귀적으로 MDP를 분해합니다.

- 중복되는 하위 문제들(Overlapping subproblems): 

가치 함수(Value Function)는 솔루션을 저장하고 재사용합니다.

우리가 강화학습을 공부하며 정말 자주 보게 되는 이 가치 함수(value function)은 주로 주어진 상태의 가치를 계산하는 데 쓰입니다. 강화학습에서 가치 함수는 핵심적인 개념이죠.

다이나믹 프로그램은 MDP에서 환경과 보상에 대해 완전히 알고 있는 상황을 가정합니다.

예를 들어, 우리가 앞으로 계속 공부하는 데 활용할 Grid World를 생각해봅시다. 

이 Grid World에서는 왼쪽으로 가면 막혀있는지, 어디로 가야 보상을 얻게 되는지 우리는 다 알고 있습니다. 환경에 대한 완전한 정보가 제공되었을 때, Dynamic Programming을 적용할 수 있습니다. 

Dynamic Programming은 MDP에서 계획(planning)을 하기 위해 활용됩니다.

여기서 우리가 풀어볼 계획 문제(Planning)는 완전한 강화학습 문제라고 볼 수는 없습니다. 

강화학습으로 가는 길에 있는 좀 더 단순화된 문제라 생각하시면 됩니다.

예측

- 입력값: MDP <S, A, P, R, gamma> 그리고 정책 pi

-             혹은 MRP <S, P, R, gamma>

- 출력값: 가치 함수(value function) v_pi

제어

- 입력값: MDP <S,A,P,R,gamma>

- 출력값: 최적 가치 함수(optimal value function) v_pi

               그리고 최적 정책 pi

Dynamic Programming 활용 분야

Dynamic Programming은 여러 분야에서 활용되고 있습니다.

- 스케쥴링 알고리즘
- 문자열 알고리즘 (예: sequence alignment)
- 그래프 알고리즘 (예: shortest path algorithms)
- 그래픽 알고리즘 (예: Viterbi algorithm)
- 바이오인포매틱스 (예: lattice models)

Dynamic Programming은 다양한 도메인에서 활용되고 있고, 사실 소프트웨어 엔지니어의 알고리즘 문제로도 인기가 많은 문제입니다.  

출처: https://www.slideshare.net/contact2kazi/dynamic-programming-63869302

Dynamic Programming의 대표적인 활용 예시는, 최단 거리 찾기 알고리즘인데요- 최단거리 알고리즘을 생각해보면, 요즘 핫한 타다와 카카오택시의 배차 알고리즘이 생각나네요 ㅎㅎ 물론 DP를 쓰지는 않겠지만요-

한국 모빌리티 업계에서 일어날 혁신을 기대합니다 화이팅!

출처: 타다 광고 크리에이티브

출처: 카카오택시 광고 크리에이티브

Reference

https://www.youtube.com/watch?v=Nd1-UUMVfz4&list=PLzuuYNsE1EZAXYR4FJ75jcJseBmo4KQ9-&index=3

https://en.wikipedia.org/wiki/Dynamic_programming

마지막으로, Clova AI에서 뛰어난 인턴/정규직 소프트웨어 엔지니어분들을 모집하고 있습니다.

[Clova AI 개발 풀타임 및 인턴십 구인공고]

저희와 같이 Real-world AI Application을 만드실 
엔지니어분을 찾습니다!  

저희 팀은 특히 비즈니스를 위한 AI를 연구 중입니다.
개발 인턴, 개발 풀타임 모두 채용 중입니다.

AI Application을 위한 모든 엔지니어링 스택을 경험하실 수 있습니다.

궁금하신 게 있다면, 놀러오세요- 
밥 사드리면서 친절하게 설명드리겠습니다 ㅎㅎ

[역할]
Development for a backend service
Server reliability engineering
Performance measuring and optimizing
Maintaining infrastructure

[자격요건]
1+ years experience in a technical role (Engineer, SRE, Software Developer)
Excellent written and verbal communication
Strong organization skills on multi-tasks

[자격요건 및 우대사항]
Knowledge of artificial intelligence and machine learning (Deep Learning)
Experiences of cloud-native application.
Experiences of continuous open source contribution
Experiences of data engineering

[채용하고 싶은 사람]
An open mindset and lively person
A person who gets a passion to learn
A humble person at their part

[지원 방식]
clova-jobs@navercorp.com
chris.ai@navercorp.com
이력서 전달 부탁드립니다.

감사합니다.