[RL] Q-Learning and Double Q-Learning

Q-Learning: Q-Learning은 1989년 Watkins에 의해 제안된 강화학습 알고리즘이며 optimal action-value function Q(s,a)의 off-policy 학습이다. 이 알고리즘은 Q-value iteration을 mimics하였고 importance sampling을 요구하지않는다는 특징이 있다. 해당 알고리즘과 비슷한 알고리즘으로는 expected SARSA가 있다. Q-Learning은 next state의 Q-value를 추정하는 과정에서 max 연산을 사용한다는 점에서 expected SARSA와 차이가 있다. 또한 off-policy 알고리즘이기 때문에 target policy와 behavior policy가 각기 다르다는 특징 또한 있다. 2013년에는 해당 알고리즘을 심층 학습과 결합한 Deep Q-Network (DQN) 알고리즘이 제안되기도 하였다.
 
Q-Learning is a reinforcement learning algorithm proposed by Watkins in 1989, which enables off-policy learning of the optimal action-value function Q(s,a). It is an off-policy algorithm, meaning that the target policy and behavior policy are different. This algorithm mimics Q-value iteration and does not require importance sampling. A similar algorithm to Q-Learning is expected SARSA. However, Q-Learning differs from expected SARSA in that it uses a max operation to estimate the Q-value of the next state. In 2013, a combination of Q-Learning and deep learning was proposed, resulting in the Deep Q-Network (DQN) algorithm.
 
Double Q-Learning: 기존 Q-Learning은 1개의 q-function과 max 연산을 통해 next state의 Q-value를 추정한다. 이러한 과정에서 positive bias가 induces되었고 실제 next state의 Q-value보다 큰 값을 추정하는 문제가 발생하였다. 이러한 bias를 maximization bias 또는 overestimation bias라고 부른다. 이러한 문제를 해결하기 위해 제안된 알고리즘이 van Hasselt가 제안한 Double Q-Learning 이다. 해당 알고리즘은 2개의 독립적인 q-function을 구성하여 q1 function을 업데이트할 때는 q1을 최대화하는 액션을 통해 q2 function의 추정값을 활용하고, q2 function을 업데이트할 때는 q2을 최대화하는 액션을 통해 q1 function의 추정값을 활용하는 방식을 통해 Q-value가 과대평가되는 것을 방지하였다.
 
The original Q-Learning algorithm estimates the Q-value of the next state using a single Q-function and a max operation. However, this process induces a positive bias, leading to an overestimation of the Q-value of the next state. This bias is known as maximization bias or overestimation bias. To address this problem, van Hasselt proposed the Double Q-Learning algorithm. This algorithm uses two independent Q-functions, where the Q1 function updates using the estimated value of Q2 through the action that maximizes Q1, and vice versa for the Q2 function. By utilizing the estimated values from both Q-functions in a alternating way, Double Q-Learning prevents the overestimation of Q-values.