Q-Learning in Non-Deterministic World

그림 1.

Non Deterministic은 한가지 행동이 여러가지 결과를 만들 수 있는 환경을 의미한다. 그림1에서 빨간선은 Agent가 이동하기로 의도한 방향이고 파란선은 에이전트가 실제로 이동한 방향이다. Deterministic한 상황에서는 에이전트가 의도한 대로 항상 오른쪽으로만 이동한다. 그런데 그림 1과 같은 상황에서는 에이전트가 그림처럼 오른쪽으로도 이동할 수도 있고 위로도 이동할 수도 있다. 이처럼 한가지의 행동(Action)이 여러가지 결과를 내는 환경을 Non-Deterministic이라 부른다.

앞선 포스트에서 설명한 Q-Learning은 예전에 알고리즘 시간에 배웠던 Dynamic Programming(이하 DP)과 여러모로 유사한데 DP는 에이전트가 취한 행동이 항상 고정된 결과를 가져올 때는(Deterministic) 최적의 해를 빠르게 낼 수 있는 알고리즘이지만 여러 가지 결과를 낼 수 있는 상황(Non-Deterministic)에서는 적용할 수 없는 문제점이 있다. 마찬가지로 Q-Learning도 환경이 고정될 때는 100%에 가까운 확률로 예측을 하지만 여러가지 결과를 내는 환경에서는 학습률이 1~2% 이하로 급격하게 저하된다. 

다행이도 DP와 달리 Q-Learning 수식을 조금만 수정하면 Non-Deterministic 환경에서도 어느 정도 괜찮은 성능을 볼 수 있다. 알고리즘 설명에 앞서 우리의 현실 세계를 바라보자. 회사에 이제 막 입사한 신입 사원은 자신의 직속 상사뿐만 아니라 고과권자, 임원 그리고 다른 회사에서 일하는 학교 선배 등등 무수히 많은 멘토들로부터 조언을 듣게 된다. 이중 몇몇은 지금 당장 실행에 옮길 수 있는 조언도 있고 지금은 아니어도 미래에 해야할 조언도 있으며 감동적인 얘기지만 요즘 시대의 정서와는 맞지 않는 (꼰대 소리) 이야기도 있다. 그래서 현명한 신입 사원이라면 멘토의 조언을 곧이곧이 받아들이지 않고 필요한 것들만 적절히 취사 선택 한다.

수정된 Q-Learning에서도 동일한 방식이 적용된다. 에이전트는 행동의 보상을 그대로 업데이트 하지 말고 여러가지 결과물의 보상값을 볼 수 있도록 기존에 학습한 정보를 고집할 필요가 있다. 수학자들은 고집하는 정도를 수학 수식의 형태로 간단하지만 예술적으로 표현 해뒀다. 이미 인공지능을 공부해본 사람들은 아마 예측 했을 수도 있겠다. Linear Regression을 공부 할 때 귀에 박히도록 배운 학습률(learning rate)을 적용하면 된다. 학습률이 높을 수록 방금 취한 action의 보상 값을 많이 반영하고 낮을 수록 보상값을 무시한다. 

1. 모든 환경 데이터 값, Q(s, a)을 초기화 한다.

2. 현재 상태를 확인한다.

3. 그리고 다음의 작업을 반복한다.

- 동작을 선택할 때 랜덤 값을 포함한다.

a = argmax(Q(s, a) + ramdom_value)

- 보상 값을 받는다.

- 새로운 상태 값(s')을 확인한다.

- 환경 데이터 값을 업데이트 한다

  Q(s, a) = (1 - learning_rate) * Q(s, a) + learning_rate * (gamma * reward + Max Q(s', a'),)

# 0 < learning_rate < 1

* 이 알고리즘을 사용하면 예전처럼 100%까지는 아니어도 50-60% 정도의 정확도는 보인다. 여전히 아직은 아쉬운 결과 값이다.

* 어찌보면 단순한 수식의 변형이 학습률을 이정도로 끌어올리니 신기하다. 인간의 두뇌도 생각보다 단순하게 이뤄져 있을 것 같다는 생각이 든다.