Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

기술 요약: $L^\infty$ 상의 벨만 연산자를 이용한 CVaR MDP의 보상 재분배

문제 정의
안전이 중요한 응용 분야에서 기대 수익(위험 중립)을 최적화하는 것은 종종 드물지만 치명적인 결과들을 허용할 수 있다는 점에서 불충분합니다. 정적 조건부 가치 위험(Static Conditional Value-at-Risk, CVaR)은 수익 분포의 하단 꼬리를 제어하기 위해 사용되는 일관된 위험 척도입니다. 그러나 수익에 대한 정적 CVaR는 명목 상태 공간에 대해 재귀적 분리성(recursive separability)이 결여되어 있어, 표준적인 마르코프 벨만 분해를 적용할 수 없습니다.

Bäuerle & Ott (2011)를 포함한 기존 방식들은 누적 보상을 추적하는 연속적인 "예산(budget)" 변수로 상태 공간을 확장함으로써 이를 해결합니다. 이는 이론적으로는 타당하지만, 다음과 같은 두 가지 결정적인 실무적 한계를 가집니다:

1. 희소 보상(Sparse Rewards): CVaR와 관련된 정보가 증강된 상태의 종단 함수(terminal functional)에 완전히 집중되어 있습니다. 이로 인해 증강된 MDP 내의 단계별 보상이 0이 되어, 특히 무한 시계열 설정에서 탐색과 시간적 신용 할당(temporal credit assignment) 문제를 악화시키는 지연된 피드백을 생성합니다.
2. 제한된 수렴성(Restricted Convergence): Bäuerle & Ott 공식과 관련된 벨만 연산자는 매우 제한된 비유계 함수(unbounded functions) 집합에 대해서만 수축성을 보장합니다. 더 실용적인 유계 함수($L^\infty$) 공간의 경우, 해당 연산자는 퇴화된 고정점(zero function)을 가지므로, 주의 깊은(종종 실행 불가능한) 초기화 제약 없이 표준적인 가치 반복(value iteration)이나 Q-러닝을 적용할 수 없습니다.

방법론
저자들은 가치 함수의 대수적 변환을 통해 이러한 한계를 해결하는 새로운 정적 CVaR 목적 함수 재구성 방식을 제안합니다.

1. 변환된 증강 MDP: Bäuerle & Ott (2011)의 상태 증강 방식을 기반으로, 저자들은 시프트 항 $z^-$ (예산의 음수 부분)를 포함하는 새로운 가치 함수 $\bar{v}^*(s, z)$를 정의합니다. 이 변환을 통해 유계 함수 공간 $L^\infty(\bar{S})$ 상에서 정의되는 새로운 벨만 연산자 $\bar{T}$를 도출할 수 있습니다.
2. 보상 재분배: 핵심 혁신은 새로운 단계별 보상 함수 $\tilde{r}(s, z, a) = z^- - (r(s, a) + z)^-$의 정의입니다. 이전 공식이 0의 중간 보상을 생성했던 것과 달리, 이 새로운 보상은 모든 단계에서 조밀하고 정보가 풍부하며, 효과적으로 궤적 전체에 CVaR 관련 신호를 재분배합니다.
3. 수축 특성: 저자들은 새로운 연산자 $\bar{T}$가 전체 유계 함수 공간에 대해 sup-norm에 대한 $\gamma$-수축임을 증명합니다. 이는 가치 반복이 까다로운 초기화 조건 없이도 유일한 고정점으로 수렴함을 보장합니다.
4. 이산화 및 근사: $z$가 연속적이므로, 저자들은 균등 이산화 기법을 채택합니다. 포락선 함수(envelope functions)를 사용하여 실제 연산자를 근사하는 하한 및 상한 바운딩 연산자($\bar{T}^l$ 및 $\bar{T}^u$)를 정의합니다. 또한, 최적 CVaR와 이산화된 근사치 사이의 오차가 이산화 격자 세밀도 및 할인 계수에 비례하여 스케일링된다는 이론적 경계치를 확립합니다.
5. 알고리즘: 이 프레임워크를 바탕으로 다음을 개발했습니다:
   • 정적 CVaR 가치 반복(Static CVaR Value Iteration): 모든 초기 상태와 예산 수준에 대해 최적의 Q-함수를 동시에 계산하는 모델 기반 알고리즘입니다.
   • 정적 CVaR Q-러닝(Static CVaR Q-Learning): 블록 업데이트 전략을 사용하는 모델 프리 알고리즘입니다. 증강된 상태 전이의 결정론적 특성을 활용하여, 단일 궤적을 재라벨링함으로써 여러 초기 예산 가설에 대한 Q-값을 업데이트하고 데이터 효율성을 높입니다. 수렴성은 표준적인 Robbins-Monro 단계 크기 조건 하에서 증명됩니다.

주요 기여

• 새로운 벨만 연산자: 저자들은 증강된 상태 공간에서 작동하며, 제어 목적에 대해 정확하고, 희소하지 않은 단계별 보상을 제공하며, 유계 함수 상에서 수축 사상인 무한 시계열 정적 CVaR를 위한 새로운 벨만 연산자를 도입했습니다.
• 근사 보장: 저자들은 격자 해상도에 따른 성능 차이를 정량화하여, 이산화된 정적 CVaR에 대한 엄격한 근사 오차 경계를 제공합니다.
• 수렴 증명: 제안된 Q-러닝 알고리즘이 이산화된 증강 공간의 최적 행동-가치 함수로 수렴하기 위한 충분 조건을 확립했습니다.
• 전역 최적성: 이 알고리즘들은 각 위험 파라미터마다 별도로 학습할 필요 없이, 단 한 번의 실행으로 모든 위험 수준(초기 증강 상태)에 대한 전역 최적해를 산출합니다.

실험 결과
저자들은 에이전트가 목표 지점으로 이동하면서 크레이터(높은 패널티)를 피하고 연료 사용(단계 패널티)을 최소화해야 하는 확률적 그리드월드 환경("Crater Walk")에서 접근 방식을 검증합니다.

• 위험 민감도: 학습된 정책은 위험 파라미터 $\alpha$에 따라 행동을 성공적으로 조정합니다. $\alpha$가 감소함에 따라(위험 회피도가 높아짐에 따라) 수익 분포의 하단 꼬리가 줄어들며, 에이전트는 경로가 길어지더라도 크레이터를 더 자주 피하게 됩니다.
• 성능: 가치 반복 및 Q-러닝 알고리즘 모두 효과적인 성능-안전 트레이드오프를 달s합니다. Q-러닝 알고리즘은 50,000회의 훈련 반복 내에 수렴합니다.
• 이산화 정확도: 이산화 해상도(100에서 5000개의 빈)를 변화시키며 수행한 실험은 상한 및 하한 바운딩 연산자의 성능 곡선이 해상도가 높아짐에 따라 실제 최적값으로 수렴함을 보여주며, 이는 이론적 오차 경계를 경험적으로 입증합니다.

의의 및 주장
본 논문은 정적 CVaR MDP에서의 희소 보상 및 제한된 수렴성 보장이 문제 자체의 본질적인 특성이 아니라 특정 모델링 선택의 결과물이라고 주장합니다. 보상을 재분배하고 유계 함수 상에서 작동하는 정확한 재구성을 제안함으로써, 저자들은 표준적인 동적 계획법 및 모델 프리 강화 학습 기법을 정적 위험 민감 문제에 적용할 수 있게 했습니다. 저자들은 본 실험적 분석이 테이블형(tabular) 설정에 집중되어 있지만, 이론적 프레임워크는 보상 부호 제한 없이 연속적인 상태 공간을 다루기 위한 함수 근사(예: 딥 뉴럴 네트워크)로의 향후 확장을 지원한다고 언급했습니다.