지금까지 배운 동적계획법과 몬테카를로 방법을 정리하면 그림 2.59와 같다. 동적계획법은 환경에 대한 정보를 알고 있어 상태전이확률 ( P(s'|s,a) )을 이용해 상태가치함수를 학습한다. 반면, 일반적인 경우에는 환경 정보를 알기 어렵기 때문에 몬테카를로 방법처럼 에피소드를 반복하여 상태가치함수를 추정하는 방식이 사용된다.
몬테카를로 방법의 한계 환경에 대한 정보 없이 학습이 가능하지만, 반드시 에피소드가 끝나야 수익을 계산할 수 있다는 제약이 있다. 즉, 바둑이나 미로 탐색처럼 종료 조건이 있는 문제에는 적합하지만, 생산 라인 최적화나 주식시장처럼 종료되지 않는 문제에는 적용이 어렵다.
이러한 한계를 극복하고자 동적계획법과 몬테카를로 방법의 장점을 결합한 시간차 학습(Temporal Difference learning, 이하 TD) 이 제안되었다.
TD의 상태가치 예측(Prediction)
TD는 에피소드 전체가 끝날 때까지 기다릴 필요 없이, 각 Time Step 단위로 즉시 학습이 가능하다는 점에서 몬테카를로 방법과 구별된다. 이 방식은 환경 모델 없이도 학습할 수 있으며, 상태에서 행동을 선택하고 이동한 직후 곧바로 가치 업데이트가 가능하다.
이때, r_{t+1} + γV(S_{t+1})은 타깃(target)이며, V(S_t)과의 차이를 TD 오차(TD error) 라고 한다.
수렴 조건 (식 2.28): V(S_t) = r_{t+1} + γV(S_{t+1}) 이면 TD 오차가 0이 되고, 더 이상 학습할 필요가 없다.
타깃의 불완전성과 수렴 가능성
실제 상황에서는 다음 상태의 가치 V(S_{t+1})를 정확히 알 수 없기 때문에, 이를 추정값으로 사용한다. 따라서 아직 학습되지 않은 상태를 기준으로 또 다른 상태를 학습하는 모순처럼 보일 수 있다.
그러나, 몬테카를로 방법과 마찬가지로 충분히 많은 에피소드를 진행하면 V(S_{t+1}) 역시 점차 수렴하게 되며, 결과적으로 전체 상태가치도 수렴함이 증명되어 있다.
요약: TD는 학습 속도와 실시간 적용 가능성 측면에서 효율적이며, 모델 없는 환경에서도 상태가치를 추정할 수 있다.
TD(0) 알고리즘
TD에는 다양한 버전이 있지만, 가장 단순한 형태는 TD(0) 이다. 이 방식은 오직 한 단계 후 상태만을 이용해 현재 상태의 가치를 업데이트한다.
알고리즘: TD(0)의 Prediction
초기화:
π <- 평가할 정책
V <- 임의의 상태가치 함수
각 에피소드에 대해 반복:
s를 초기화
에피소드의 각 스텝에 대해 반복:
a <- 상태 s에서 정책 π에 의해 결정된 행동
행동 a를 취한 후 보상 r과 다음 상태 s'를 관측
V(s) <- V(s) + a[r + γV(s') - V(s)]
s <- s'
s가 마지막 상태라면 종료
Python 코드 구현
# TD(0) prediction
np.random.seed(0)
# 환경, 에이전트를 초기화
env = Environment()
agent = Agent()
gamma = 0.9
#초기화 :
# π ← 평가할 정책
# 가능한 모든 행동이 무작위로 선택되도록 지정
# 𝑉 ← 임의의 상태가치 함수
V = np.zeros((env.reward.shape[0], env.reward.shape[1]))
# 최대 에피소드, 에피소드의 최대 길이를 지정
max_episode = 10000
max_step = 100
alpha = 0.01
print("start TD(0) prediction")
# 각 에피소드에 대해 반복 :
for epi in tqdm(range(max_episode)):
delta =0
# s 를 초기화
i = 0
j = 0
agent.set_pos([i,j])
# 에피소드의 각 스텝에 대해 반복 :
for k in range(max_step):
pos = agent.get_pos()
# a←상태 𝑠 에서 정책 π에 의해 결정된 행동
# 가능한 모든 행동이 무작위로 선택되게 함
action = np.random.randint(0,4)
# 행동 a 를 취한 후 보상 r과 다음 상태 s’를 관측
# s←𝑠'
observation, reward, done = env.move(agent,action)
# V(𝑠)←V(𝑠)+ α[𝑟+𝛾𝑉(𝑠')−𝑉(𝑠)]
V[pos[0],pos[1]] += alpha * (reward + gamma * V[observation[0],observation[1]] - V[pos[0],pos[1]])
# s가 마지막 상태라면 종료
if done == True:
break
print("V(s)")
show_v_table(np.round(V,2),env)
TD(0)의 결과와 해석
그림 2.61은 TD(0)를 통해 학습한 각 상태의 가치 테이블을 보여준다. 동적계획법이나 몬테카를로 방법과 비교해 값은 다를 수 있지만, 도착지점으로 가까워질수록 가치가 커지는 구조는 동일하다. 이는 TD(0) 역시 상태가치 예측을 잘 수행함을 의미한다.
🧭 시간차학습(TD)의 Control: SARSA와 Q-learning
✅ 행동 선택 정책의 기본
TD Control에서는 행동 선택을 위한 정책으로 다음 두 가지가 사용된다:
ε-탐욕정책 (ε-greedy)
최적 행동은 높은 확률로 선택하지만, 무작위로 다른 행동을 선택할 가능성도 존재함
식 2.25:
π(s,a) = {
1-ε+ε/|A(s)| if a = A^*
ε/|A(s)| otherwise
}
SARSA는 행동정책과 타깃정책이 동일한 경우로, on-policy 알고리즘이다. 행동가치 함수는 다음과 같이 갱신된다:
Q(s,a) ← Q(s,a) + α[r + γQ(s',a') − Q(s,a)]
타깃:
Target = r + γQ(s', a')
즉, 다음 상태에서 실제로 선택한 행동의 가치를 사용해 학습한다.
SARSA 알고리즘:
알고리즘: TD(0) SARSA
모든 s∈S, a∈A(S)에 대해 초기화:
Q(s,a) <- 임의의 값
Q(terminal - state,.) = 0
각 에피소드에 대해 반복:
s를 초기화
s에서 행동정책으로 행동 a를 선택(예: ε-탐욕정책)
에피소드의 각 스텝에 대해 반복:
행동 a를 취한 후 보상 r과 다음 상태 s'을 관측
s'에서 타깃 정책으로 행동 a'을 선택(예: ε-탐욕정책)
Q(s,a) <- Q(s,a) + a[r+γQ(s',a') - Q(s,a)]
s <- s'; a <- a'
s가 마지막 상태라면 종료
# TD(0) control : SARSA
np.random.seed(0)
# 환경, 에이전트를 초기화
env = Environment()
agent = Agent()
gamma = 0.9
# 모든 𝑠∈𝑆,𝑎∈𝐴(𝑆)에 대해 초기화:
# 𝑄(𝑠,𝑎)←임의의 값
Q_table = np.random.rand(env.reward.shape[0], env.reward.shape[1],len(agent.action))
# Q(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙−𝑠𝑡𝑎𝑡𝑒,𝑎)=0
Q_table[2,2,:] = 0
max_episode = 10000
max_step = 100
print("start TD(0) control : SARSA")
alpha = 0.1
epsilon = 0.8
# 각 에피소드에 대해서 반복 :
for epi in tqdm(range(max_episode)):
dleta = 0
# S 를 초기화
i = 0
j = 0
agent.set_pos([i,j])
temp =0
# s 에서 행동 정책(Behavior policy)으로 행동 a를 선택 ( 예 : ε-greedy
action = e_greedy(Q_table,agent,epsilon)
# 에피소드의 각 스텝에 대해서 반복 :
for k in range(max_step):
pos = agent.get_pos()
# Q_visit_count[action, pos[0],pos[1]] +=1
# 행동 a 를 취한 후 보상 r과 다음 상태 s^' 관측
observation, reward, done = env.move(agent, action)
# s^' 에서 타깃 정책(Target policy)으로 행동 a^'를 선택 ( 예 : ε-greedy
next_action = e_greedy(Q_table,agent,epsilon)
# Q(𝑆,𝐴)←Q(𝑆,𝐴) + α[𝑅+𝛾𝑄(𝑆',𝐴')−𝑄(𝑆,𝐴)]
Q_table[pos[0],pos[1],action] += alpha * (reward + gamma * Q_table[observation[0], observation[1],next_action] - Q_table[pos[0],pos[1],action])
# s←s^' ; a←a^'
action = next_action
# s가 마지막 상태라면 종료
if done == True:
break
# 학습된 정책에서 최적 행동 추출
optimal_policy = np.zeros((env.reward.shape[0], env.reward.shape[1]))
for i in range(env.reward.shape[0]):
for j in range(env.reward.shape[1]):
optimal_policy[i,j] = np.argmax(Q_table[i,j,:])
print("SARSA : Q(s,a)")
show_q_table(np.round(Q_table,2),env)
print("SARSA :optimal policy")
show_policy(optimal_policy,env)
SARSA는 ε-탐욕정책을 행동정책과 타깃정책 모두에 사용한다. 따라서 현재 상태와 다음 상태 모두에서 동일한 방식으로 행동을 선택한다. 이러한 구조는 보수적이고 안정적인 경로 학습을 유도한다.
🚀 Q-learning (Off-policy)
Q-learning은 행동정책과 타깃정책이 다르다. 현재 상태에서는 ε-탐욕정책으로 행동을 선택하지만, 학습에는 다음 상태에서 가능한 최적 행동의 가치(max Q) 를 사용한다.
알고리즘: TD(0) Q-learning
모든 s∈S, a∈A(S)에 대해 초기화:
Q(s,a) <- 임의의 값
Q(terminal - state, a) = 0
각 에피소드에 대해 반복:
s를 초기화
에피소드의 각 스텝에 대해 반복:
s에서 행동 정책으로 행동 a를 선택
행동 a를 취한 후 보상 r과 다음 상태 s'를 관측
s'에서 타깃 정책으로 행동 a'을 선택
Q(s,a) <- Q(s,a) + a[r + γmax_{a'}Q(s',a') - Q(s,a)]
s <- s'
s가 마지막 상태라면 종료
# TD(0) contro : Q-learning
# 환경, 에이전트를 초기화
env = Environment()
agent = Agent()
gamma = 0.9
np.random.seed(0)
# 모든 𝑠∈𝑆,𝑎∈𝐴(𝑆)에 대해 초기화:
# 𝑄(𝑠,𝑎)←임의의 값
Q_table = np.random.rand(env.reward.shape[0], env.reward.shape[1],len(agent.action))
# Q(𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙−𝑠𝑡𝑎𝑡𝑒,𝑎)=0
Q_table[2,2,:] = 0
max_episode = 10000
max_step = 100
print("start TD(0) control : Q-learning")
alpha = 0.1
epsilon = 0.8
# 각 에피소드에 대해 반복 :
for epi in tqdm(range(max_episode)):
dleta = 0
# S 를 초기화
i = 0
j = 0
agent.set_pos([i,j])
# 에피소드의 각 스텝에 대해 반복 :
for k in range(max_step):
# s 에서 행동 정책(Behavior policy)으로 행동 a를 선택 ( 예 : ε-greedy
pos = agent.get_pos()
action = e_greedy(Q_table,agent,epsilon)
# 행동 a 를 취한 후 보상 r과 다음 상태 s^'를 관측
observation, reward, done = env.move(agent, action)
# s^' 에서 타깃 정책(Target policy)으로 행동 a^'를 선택 ( 예 : greedy)
next_action = greedy(Q_table,agent,epsilon)
# Q(s,a)←Q(s,a) + α[r+𝛾 maxa'𝑄(s',a')−𝑄(s,a)]
Q_table[pos[0],pos[1],action] += alpha * (reward + gamma * Q_table[observation[0], observation[1],next_action] - Q_table[pos[0],pos[1],action])
# s가 마지막 상태라면 종료
if done == True:
break
# 학습된 정책에서 최적 행동 추출
optimal_policy = np.zeros((env.reward.shape[0], env.reward.shape[1]))
for i in range(env.reward.shape[0]):
for j in range(env.reward.shape[1]):
optimal_policy[i,j] = np.argmax(Q_table[i,j,:])
print("Q-learning : Q(s,a)")
show_q_table(np.round(Q_table,2),env)
print("Q-learning :optimal policy")
show_policy(optimal_policy,env)
이처럼 Q-learning은 off-policy에 해당하며, 탐욕정책을 타깃으로 사용하여 더 공격적인 최적 경로 탐색을 수행한다.
⚖️ SARSA vs Q-learning 요약 비교
항목
SARSA
Q-learning
정책 유형
On-policy
Off-policy
타깃 정책
행동정책과 동일 (ε-greedy)
탐욕정책 (greedy)
타깃 정의
Q(s', a')
max_a' Q(s', a')
업데이트 방식
실제 선택한 행동 기준
가장 가치 높은 행동 기준
특성
안전한 경로 탐색
최단 경로 탐색
절벽 예제 경로
절벽을 피해 우회함
절벽 가까이를 지나 최적 경로 탐색
🔍 차이점의 시각적 이해
SARSA: s → a → r, s' → a'에서 a'는 실제로 선택한 행동
Q-learning: s → a → r, s'에서 a'는 가치가 가장 큰 행동
SARSA는 a' = a가 되도록 타깃 정책에서 선택한 행동을 실제 행동으로 이어간다. Q-learning은 타깃 정책에서 max Q로 선택한 a'와, 이후 행동정책에서 선택하는 a가 다를 수 있다.
🧠 절벽 문제에서의 비교
환경: 4×12 격자, 절벽 근처(R = -100), 출발 → 도착 경로 존재
SARSA: 절벽을 피해 우회 경로 학습
Q-learning: 절벽을 감수하고 최적(최단) 경로 학습
그림 2.68에서는 ε = 0.7인 상황에서 SARSA와 Q-learning을 실행한 결과를 보여주며, 이론적인 차이를 실제로 확인할 수 있다. 문제의 성격에 따라 안정성을 중시하면 SARSA, 효율성을 중시하면 Q-learning을 사용하는 것이 바람직하다.
