Q-learning은 환경의 모델 없이도 에이전트가 현재 상태에 기반하여 가능한 행동들에 값을 할당하도록 훈련시키는 모델-프리(model-free) 강화 학습 알고리즘이다. 확률적 전이와 보상을 처리하는 데 적응이 필요 없이 다룰 수 있다. 유한 마르코프 결정 과정에 대해, Q-learning은 무한한 탐색 시간과 부분적으로 무작위적인 정책이 주어졌을 때, 현재 상태에서 시작하여 모든 연속적인 단계에 걸쳐 총 보상의 기대값을 최대화한다는 의미에서 최적 정책을 찾는다. "Q"는 알고리즘이 계산하는 함수, 즉 주어진 상태에서 취한 행동의 기대 보상 - 다시 말해 그 품질 - 을 가리킨다.
간단한 예로, 격자 미로 에이전트가 10점짜리 출구에 도달하는 법을 배운다고 하자. 분기점에서 Q-learning은 오른쪽이 왼쪽보다 출구에 더 빨리 도달한다면 오른쪽으로 이동하는 것에 더 높은 값을 할당할 수 있으며, 시간이 지남에 따라 두 방향을 모두 시도함으로써 이 선택을 개선한다. 이는 알고리즘이 반복적 업데이트를 통해 즉각적인 보상과 장기적 결과 사이의 균형을 어떻게 맞추는지 보여준다.
강화 학습 맥락
강화 학습은 에이전트, 상태 집합 \(\mathcal{S}\), 그리고 각 상태별 행동 집합 \(\mathcal{A}\)를 포함한다. 행동 \(a \in \mathcal{A}\)를 수행함으로써 에이전트는 상태에서 상태로 전이한다. 특정 상태에서 행동을 실행하면 에이전트는 수치적 점수인 보상을 받는다. 에이전트의 목표는 현재 상태를 달성하기 위한 보상에 미래 상태에서 얻을 수 있는 최대 보상을 더하여 총 보상을 최대화하는 것이며, 이는 잠재적 미래 보상으로 현재 행동에 효과적으로 영향을 미친다. 이 잠재적 보상은 현재 상태에서 시작하는 모든 미래 단계의 보상 기대값의 가중 합이다.
예를 들어, 기차에 탑승하는 경우를 생각해 보자. 보상은 총 탑승 시간의 음수로 측정된다. 한 전략은 기차 문이 열리자마자 들어가는 것으로, 초기 대기 시간을 최소화한다. 그러나 기차가 붐비면 하차 승객들이 나가려고 싸우면서 진입이 느리다. 그러면 총 탑승 시간은 0초 대기 + 15초 싸움 시간이 된다. 다음 날, 무작위 기회(탐색)로 에이전트는 기다렸다가 다른 사람들이 먼저 내리게 하여, 더 긴 대기 시간을 갖지만 싸움 시간은 줄어든다. 전반적으로 이 경로는 총 탑승 시간이 5초 대기 + 0초 싸움 시간이므로 더 높은 보상을 가진다. 탐색을 통해, 초기의 인내심 있는 행동이 강제적인 전략보다 더 큰 비용을 초래했음에도 불구하고, 전체 비용은 더 낮아져 더 보상적인 전략을 드러낸다.
알고리즘 메커니즘
미래로 \(\Delta t\) 단계 후에, 에이전트는 다음 단계를 결정할 것이다. 이 단계의 가중치는 \(\gamma^{\Delta t}\)로 계산되며, 여기서 \(\gamma\)(할인 인자)는 0과 1 사이의 숫자이다. \(\gamma < 1\)이라고 가정하면, 이는 나중에 받는 보상보다 더 일찍 받는 보상을 더 높게 평가하여 좋은 시작의 가치를 반영한다. \(\gamma\)는 또한 매 단계 \(\Delta t\)에서 성공하거나 생존할 확률로 해석될 수 있다.
알고리즘은 상태-행동 조합의 품질을 계산하는 함수 \(Q: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\)를 가진다. 학습이 시작되기 전에, \(Q\)는 프로그래머가 선택한 임의의 고정 값으로 초기화된다. 각 시간 \(t\)에서 에이전트는 행동 \(A_t\)를 선택하고, 보상 \(R_{t+1}\)을 관찰하며, 새로운 상태 \(S_{t+1}\)(이전 상태 \(S_t\)와 선택된 행동 모두에 의존할 수 있음)에 들어가고, \(Q\)가 업데이트된다. 핵심 업데이트는 벨만 방정식으로, 간단한 가치 반복 업데이트로서 현재 값과 새 정보의 가중 평균을 사용한다:
\(Q_{new}(S_t, A_t) \leftarrow (1 - \alpha) \cdot Q(S_t, A_t) + \alpha \cdot [R_{t+1} + \gamma \max_a Q(S_{t+1}, a)]\)
여기서 \(\alpha\)는 학습률로, 새 정보가 기존 정보를 얼마나 대체하는지를 제어한다.
탐색과 활용
알고리즘은 탐색(보상을 발견하기 위해 새로운 행동을 시도하는 것)과 활용(높은 보상을 주는 것으로 알려진 행동을 선택하는 것) 사이의 균형에 의존한다. 엡실론-그리디(epsilon-greedy)와 같은 부분적으로 무작위적인 정책은 대부분의 시간 동안 가장 잘 알려진 행동을 선택하지만, 때때로 무작위 행동을 선택하여 탐색한다. 이는 에이전트가 시간이 지남에 따라 추정치를 개선할 수 있게 하며, 기차 탑승 예에서 무작위 탐색이 더 나은 전략을 드러낸 것과 같다.
수렴과 최적성
유한 마르코프 결정 과정에 대해, Q-learning은 무한한 탐색 시간과 적절한 학습률 일정이 주어지면, 어떤 시작 상태에서든 기대 총 보상을 최대화하는 최적 정책으로 수렴한다. 알고리즘은 환경의 전이 역학 모델을 요구하지 않으므로, 그러한 모델이 알려지지 않거나 복잡한 문제에 적용할 수 있다. 이러한 모델-프리 특성은 명시적 전이 확률을 필요로 하는 모델 기반 방법과 구별된다.
응용 및 확장
Q-learning은 로봇 공학, 게임 플레이, 자율 시스템에 적용되어 왔다. 표 형태의 형태는 작은 상태 공간에 적합하지만, 크거나 연속적인 공간의 경우 딥 Q-네트워크와 같은 확장이 Q-learning을 딥러닝 및 신경망 함수 근사기와 결합한다. 이러한 발전은 인공지능 게임 에이전트 및 머신러닝 제어 작업과 같은 분야에서 성공을 가능하게 했다. 이 알고리즘의 원리는 또한 버클리 AI 연구소 및 MIT CSAIL과 같은 기관의 현대 강화 학습 연구의 기초가 된다.