절벽 걷기

최적설계 게임 개발 소프트웨어 마지막 수정: 2026-08-15 04:51:36

1. 개요[편집]

절벽 걷기 Cliff Walking
출처	서턴·바토 Reinforcement Learning: An Introduction 예제 6.6
격자	4 × 12, 감가 없음(γ=1), 에피소드형
보상	이동 −1 · 절벽 진입 −100 후 출발점 복귀
최적 경로	절벽 바로 옆 13보, 수익 −13
보여주는 것	온폴리시(SARSA) vs 오프폴리시(Q러닝)의 실질적 차이

절벽 걷기는 온폴리시 학습과 오프폴리시 학습이 같은 문제에서 서로 다른 정책으로 수렴한다는 사실을 눈으로 보여주기 위해 만들어진 표준 격자세계 벤치마크다. 서턴·바토 교과서의 예제 6.6에 실린 뒤로 강화 학습 강의에서 온·오프폴리시를 설명할 때 거의 반드시 소환되는 예제가 됐다.

구성은 이렇다. $4 \times 12$ 격자에서 왼쪽 아래가 출발 $S$ , 오른쪽 아래가 목표 $G$ 이고, 둘 사이 맨 아랫줄 열 칸이 절벽이다. 행동은 상하좌우 네 가지이며 결정론적으로 한 칸 움직이고, 격자 밖으로 나가려 하면 제자리에 머문다. 보상은 모든 이동에 $-1$ , 절벽 칸에 들어가면 $-100$ 과 함께 출발점으로 순간이동한다. 감가는 없고( $\gamma=1$ ) 목표에 도달해야 에피소드가 끝난다.

여기서 중요한 설계 하나 — 절벽에 빠져도 에피소드가 끝나지 않는다. 그냥 $-100$ 을 물고 처음부터 다시 걷는다. 그래서 절벽에 빠지는 비용이 “실패 판정”이 아니라 누적 손실로 계속 쌓인다.¹

2. 최적 정책과 안전 정책[편집]

수익을 계산해 보면 답이 명확하다.

최단 경로: $S$ 에서 한 칸 위로 올라가 절벽 바로 윗줄을 따라 11칸 오른쪽으로 간 뒤 한 칸 내려간다. 13보, 수익 $-13$ . 이것이 $\gamma=1$ 결정론적 MDP의 최적 정책이고 최적 가치가 $v^\ast(S) = -13$ 이다.
한 줄 더 위로 물러난 경로: 15보, 수익 $-15$ .
맨 윗줄까지 물러난 경로: 17보, 수익 $-17$ .

탐험이 없다면 논쟁의 여지가 없다. 최적은 절벽 옆 13보다. 문제는 학습 중에 우리가 $\epsilon$ -탐욕 정책으로 돌아다닌다는 것이고, 절벽 옆 칸에서 무작위 행동 하나가 아래를 가리키면 $-100$ 이라는 사실이다.

3. 두 알고리즘이 다른 답을 배우는 이유[편집]

SARSA와 Q러닝의 갱신식 차이는 표적 한 항뿐이다.

\text{SARSA:}\quad Q(s,a) \leftarrow Q(s,a) + \alpha\bigl[r + \gamma\,Q(s',a') - Q(s,a)\bigr]

\text{Q러닝:}\quad Q(s,a) \leftarrow Q(s,a) + \alpha\bigl[r + \gamma\,\max_{a''} Q(s',a'') - Q(s,a)\bigr]

Q러닝의 표적에는 $\max$ 가 들어가므로 “다음 상태에서 실수 없이 최선을 뒀다면”의 가치를 학습한다. 즉 탐험 잡음이 표적에 전혀 반영되지 않고, 절벽 옆 칸의 $Q$ 가 깎이지 않는다. 결과적으로 절벽에 붙는 최단 경로를 배운다. 배운 것 자체는 옳다 — 진짜 $Q^\ast$ 다.
SARSA의 표적에는 실제로 다음에 실행할 $a'$ 이 들어간다. $\epsilon$ -탐욕이 가끔 아래를 고르면 그 $-100$ 이 $a'$ 을 통해 절벽 옆 칸의 $Q$ 로 흘러 들어간다. 그래서 절벽 옆 칸의 가치가 실제로 낮게 평가되고, 위로 물러난 우회로를 배운다. 이것도 옳다 — 다만 학습 대상이 $Q^\ast$ 가 아니라 지금 굴리는 $\epsilon$ -탐욕 정책의 $Q^\pi$ 다.

두 알고리즘은 틀린 게 아니라 서로 다른 질문에 답하고 있다. “완벽하게 실행한다면 무엇이 최선인가”와 “가끔 손이 미끄러지는 나에게 무엇이 최선인가”는 다른 질문이고, 절벽 걷기는 그 두 답이 눈에 띄게 갈리도록 설계된 지형이다.

4. 온라인 보상은 Q러닝이 진다[편집]

그래서 역설이 생긴다. Q러닝은 더 좋은 정책을 배우는데 학습 중 성적은 더 나쁘다. $\epsilon = 0.1$ 로 계속 굴리면서 에피소드별 누적 보상을 그려 보면 SARSA 곡선이 Q러닝 곡선보다 뚜렷하게 위에 있다.

대략적인 계산으로 규모를 잡아 보자. $\epsilon$ -탐욕에서 “확률 $\epsilon$ 로 네 행동 중 균등 추출”이라는 흔한 구현을 쓰면 특정 비탐욕 행동이 뽑힐 확률은 $\epsilon/4 = 0.025$ 다. 절벽 옆줄 경로는 아래가 절벽인 칸을 10개 지나므로, 한 번 완주하는 동안 떨어질 확률이 대략

p \;\approx\; 1 - (1-0.025)^{10} \;\approx\; 0.22

떨어지면 $-100$ 을 물고 처음부터 다시 걸으므로, 한 에피소드의 기대 수익 $V$ 는 대충 $V = -13 + p\,(-100 + V)$ 를 만족한다. 풀면

V \;\approx\; -\frac{13 + 100p}{1-p} \;\approx\; -45

반면 위로 물러난 경로는 절벽에 접한 칸을 지나지 않으므로 무작위 행동 한 번으로는 떨어지지 않는다(두 번 연속 운이 나빠야 한다). 걸음 수 15~17에 무작위 행동으로 낭비하는 몇 걸음을 더해도 $-20$ 안팎이다. 정책의 진짜 가치는 $-13$ 대 $-15$ 로 최단 경로가 낫지만, $\epsilon=0.1$ 로 실행했을 때의 값은 $-45$ 대 $-20$ 으로 완전히 뒤집힌다. 교과서 그림에서 두 곡선이 대략 이 정도 간격으로 벌어지는 것이 이 계산의 내용이다.²

여기서 얻어 갈 교훈은 격자세계보다 넓다. “학습한 정책의 성능”과 “학습 중 행동 정책의 성능”은 다른 수치이며, 벤치마크에서 무엇을 보고하는지가 결론을 뒤집을 수 있다. 논문 그래프의 세로축이 온라인 누적 보상인지, 주기적으로 탐험을 끄고 평가한 값인지에 따라 같은 실험이 정반대 순위를 낸다.

5. ε → 0 이면 둘 다 최적으로 간다[편집]

이 예제를 “SARSA가 Q러닝보다 낫다”로 읽으면 오독이다. 표 형태에서 두 알고리즘 모두 로빈스-먼로 스텝 조건과 충분한 탐험 아래 $Q^\ast$ 로 확률 1 수렴한다. 다만 SARSA에는 조건이 하나 더 붙는다 — GLIE, 즉 무한히 탐험하되 정책이 극한에서 탐욕으로 수렴해야 한다( $\epsilon_k \to 0$ ). Q러닝은 표적에 행동 정책이 안 들어가므로 이 조건이 필요 없다.

따라서 $\epsilon$ 을 서서히 줄이면 SARSA도 절벽 옆 최단 경로로 넘어온다. 우회로는 SARSA가 가진 성질이 아니라 탐험 확률이 고정되어 있다는 조건의 결과다. 실험에서 이 부분이 자주 오해되는데, $\epsilon$ 감쇠 스케줄을 두 알고리즘에 똑같이 맞추지 않고 비교하면 아무 의미 없는 그래프가 나온다.

한 가지 더 구분해 둘 것 — 절벽 걷기가 보여주는 것은 온·오프폴리시의 차이이지 Q러닝의 최대화 편향(maximization bias)이 아니다. 최대화 편향은 확률적 보상 아래에서 $\max$ 연산자가 추정치를 위로 밀어 올리는 별개의 현상이고, 교과서도 그건 다른 예제로 따로 설명한다. 절벽 걷기의 환경은 결정론적이라 최대화 편향이 사실상 개입하지 않는다.

6. 기대 SARSA의 자리[편집]

기대 SARSA는 표적에서 $a'$ 을 뽑는 대신 정책 하에서 기댓값을 직접 취한다.

Q(s,a) \leftarrow Q(s,a) + \alpha\Bigl[\, r + \gamma \sum_{a'} \pi(a' \mid s')\, Q(s',a') - Q(s,a) \,\Bigr]

절벽 걷기에서 이 알고리즘은 두 원조보다 낫다. $a'$ 추출에서 오는 분산이 사라져 같은 학습률에서 더 안정적이고, 환경이 결정론적이면 $\alpha = 1$ 까지 올려도 안전하다 — 표적에 확률적 잡음이 아예 없기 때문이다. 학습률을 넓은 범위로 훑어 성능을 그리면 기대 SARSA 곡선이 SARSA·Q러닝 곡선 위에 놓인다.

구조적으로도 흥미롭다. $\pi$ 를 행동 정책으로 두면 온폴리시 SARSA의 저분산 판본이고, $\pi$ 를 탐욕 정책으로 두면 식이 정확히 Q러닝이 된다. 즉 기대 SARSA는 두 알고리즘을 한 식 안에 품는 상위 개념이며, 표적 정책과 행동 정책을 분리하면 그대로 오프폴리시로도 쓸 수 있다. 대가는 행동 수만큼의 곱셈 비용인데, 격자세계처럼 행동이 네 개면 사실상 공짜다.

7. 흔적과 n-스텝을 얹으면[편집]

절벽 걷기는 적격 흔적의 효과를 보여주는 무대이기도 하다. SARSA(0)은 목표에 도달했다는 정보를 한 에피소드에 한 칸씩만 뒤로 밀기 때문에, 12칸 떨어진 출발점까지 신용이 전달되려면 에피소드를 여러 번 반복해야 한다. $\lambda$ 를 올리면 목표를 한 번 밟는 순간 지나온 경로 전체의 $Q$ 가 한꺼번에 올라가고, 학습 곡선이 초반부터 눈에 띄게 내려앉는다. $n$ -스텝 SARSA도 같은 효과를 정수 눈금으로 낸다.

반면 오프폴리시 쪽은 여기서 손해를 본다. 왓킨스 Q(λ) 는 목표정책이 탐욕정책이라는 점을 지키려고 비탐욕 행동을 취한 순간 흔적을 전부 0으로 날리는데, $\epsilon = 0.1$ 이면 평균 10보마다 흔적이 잘려 나간다. 절벽 걷기의 최단 경로가 13보라는 점을 생각하면 흔적을 길게 유지한 이득이 거의 남지 않는다. 흔적을 안 자르는 변형이나 Retrace(λ) 같은 절충안이 나온 배경이 이것이며, 자세한 계보는 적격 흔적 문서에 있다. 결국 신용 할당을 빠르게 하는 장치와 오프폴리시 보정은 서로 싸운다는 것이 이 예제가 추가로 알려주는 사실이다.

8. 안전 강화 학습으로의 함의[편집]

“온폴리시 가치에는 탐험의 위험이 이미 반영되어 있다”는 성질은 실물을 굴리는 상황에서 그 자체로 값어치가 있다. 로봇 팔, 공정 제어, 자율 주행처럼 실패 비용이 큰 시스템에서 우리가 알고 싶은 값은 대개 “완벽하게 실행했을 때의 가치”가 아니라 “불확실성을 품은 실제 실행의 가치” 이기 때문이다. 안전 강화학습 문헌이 SARSA 계열에 우호적인 이유가 여기 있다.

다만 절벽 걷기를 안전성의 근거로 과대해석하면 곤란하다. 짚어 둘 점이 몇 가지 있다.

SARSA는 학습 중에도 절벽에 떨어진다. 탐험 위험을 가치에 반영할 뿐 회피를 보장하지는 않는다. 진짜 안전 보장이 필요하면 제약을 명시적으로 거는 제약 마르코프 결정 과정 정식화나, 위험 행동을 사전에 차단하는 차폐(shielding) 계층이 따로 필요하다.
반영되는 것은 기댓값이지 꼬리 위험이 아니다. 드물지만 치명적인 사건은 기댓값에 거의 안 잡히므로, CVaR 같은 위험 척도를 목적함수에 직접 넣는 접근이 별도로 발전했다.
어디까지나 현재의 $\epsilon$ 에 맞춰진 정책이다. 배포 시점에 탐험을 끄면 SARSA가 배운 우회로는 그냥 두 걸음 손해일 뿐이다. 학습 조건과 배포 조건이 다르면 “안전하게 배웠다”는 말이 성립하지 않는다.

9. 변형과 실습 메모[편집]

확률적 절벽 걷기: 의도한 방향으로 갈 확률을 0.8 정도로 낮추고 나머지를 옆으로 흘리면, 탐험을 꺼도 미끄러짐이 남으므로 우회로가 진짜 최적 정책이 된다. 이렇게 바꾸면 Q러닝도 우회로를 배우며, “SARSA가 겁이 많다”가 아니라 “위험이 전이확률에 있느냐 행동 선택에 있느냐” 가 문제였다는 점이 드러난다.
바람 부는 격자세계(windy gridworld)는 같은 교과서의 이웃 예제로, 결정론적 외란 아래에서 $n$ -스텝·흔적의 효과를 보는 데 쓰인다. 절벽 걷기와 세트로 돌리는 것이 관례.
구현 함정 하나 — 절벽 진입을 “종료 상태”로 처리해 버리면 예제가 통째로 망가진다. 에피소드가 짧게 끝나 버려서 $-100$ 의 무게가 상대적으로 줄어들고, SARSA와 Q러닝의 차이가 흐려진다. 원본은 복귀지 종료가 아니다.
$\epsilon$ -탐욕 구현 규약도 결과에 영향을 준다. “확률 $\epsilon$ 로 전체 행동에서 균등 추출”과 “확률 $\epsilon$ 로 비탐욕 행동에서 균등 추출”은 낙하 확률이 $\epsilon/4$ 와 $\epsilon/3$ 으로 달라, 위 계산의 숫자가 바뀐다. 논문 재현이 안 될 때 의외로 자주 여기가 범인이다.
표가 $4\times12\times4 = 192$ 칸뿐이라 노트북에서 몇 초면 돌아간다. 강화 학습 코드의 부호·인덱스 버그를 잡는 최소 재현 예제로도 쓸 만하다.³

10. 관련 문서[편집]

이 설계가 은근히 잔인하다. 절벽에 빠진 에이전트는 죽지도 못하고 출발점에서 다시 걷는다. 학습 곡선의 아래쪽 톱니가 전부 “또 떨어졌다”의 기록이라는 걸 알고 나면 그래프가 조금 달리 보인다. ↩
여기 적은 $-45$ 는 “완주 중 낙하는 최대 한 번, 낭비 걸음은 무시”라는 거친 가정으로 뽑은 봉투 뒷면 계산이다. 실제 실험값은 학습률·초기값· $\epsilon$ 규약에 따라 $-40$ 에서 $-60$ 사이를 오간다. 요점은 정확한 숫자가 아니라 두 값이 $-13$ 대 $-15$ 가 아니라 두 배 이상 벌어진다는 사실이다. ↩
그리고 이 예제의 진짜 용도는 강의실에 있다. “최적 정책을 배운 쪽이 성적이 더 나쁘다”는 한 문장으로 온·오프폴리시 구분을 설명할 수 있는 예제는 흔치 않다. 서턴·바토가 격자 크기를 $4\times12$ 라는 애매한 값으로 잡은 것도 절벽을 충분히 길게 만들어 이 역전이 확실히 보이게 하려는 조정이었을 것이다. ↩