기술 요약: 재시도(Retrying)를 통한 정책 경사 강화 학습에서의 탐색 발현

1. 문제 정의

강화 학습(RL)에서 탐색은 일반적으로 보상 신호에 명시적인 보너스(예: 엔트로피, 호기기 또는 카운트 기반 보너스)를 추가하거나 사후 샘플링(posterior sampling) 방법을 사용하여 유도됩니다. 저자들은 이와 구별되는 메커니즘을 제시합니다. 즉, 탐색은 **재시도(retrying)**를 통해 불확실성 하에서 보상을 최대화하려는 에이전트의 필요성으로부터 자연스럽게 발현되어야 한다는 것입니다.

핵심 직관은 에이전트가 행동을 재시도하거나 유사한 상태에 직면할 수 있는 환경에서, 현재의 최선만을 고려하는 탐욕적(greedy) 정책은 이후의 시도에서 더 높은 수익을 얻을 가능성을 무시하기 때문에 부적절하다는 것입니다. 재시도 기회가 없다면, 현재 가장 높은 보상을 줄 것으로 믿어지는 행동을 선택하는 것이 합리적입니다. 그러나 불확ability(불확실성) 하에서는, 대안적인 행동들을 탐색함으로써 불확실성에 대비하는 정책이 여러 차례의 시도 동안 더 높은 기대 최대(expected maximum) 수익을 달면 달성할 수 있습니다. 기존 방법들은 불확실성을 추정하거나 보너스를 구성하기 위해 복잡한 보조 모델을 필요로 하는 경우가 많지만, 본 논문은 재시도의 가치를 공식화하는 보상 기반 목적 함수를 최적화함으로써 탐색을 유도할 수 있는지 묻습니다.

2. 방법론

2.1 ReMax 목적 함수

저자들은 단일 시도의 기대 수익이 아닌, $M$개의 독립적인 샘플(시도)에 대한 기대 최대값을 평가하는 ReMax(Retry Maximum) 목적 함수를 제안합니다.

행동 가치 $\mu$와 이 값들에 대한 분포 $\Pi$(인식적 불확실성을 나타냄)가 있는 밴딧 설정에서, ReMax 목적 함수는 다음과 같이 정의됩니다:
$$J^M_{\text{ReMax}}(\pi) := \mathbb{E}_{\mu \sim \Pi} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} \mu_{A_m} \mid \mu \right] \right]$$
여기서 $A^{[M]}$은 정책 $\pi$로부터의 $M$개 독립적인 추출을 나타냅니다.

• 메커니즘: $M$번의 추출 중 최대값을 최대화함으로써, 이 목적 함수는 현재 추정된 평균 최대값보다 높은 보상을 줄 가능성이 있는 행동에 확률 질량을 할당하도록 유도합니다. 이는 불확실성에 대비하기 위해 확률적 성질(탐색)을 유도하는 결과로 나타납니다.
• 결정론적 사례: 고정된 보상이 있더라도, ReMax는 목적 함수의 기하학적 구조를 재형성합니다. 재시도 파라미터 $M$을 늘리면 최적점 근처의 그래디언트가 평탄해져 수렴 속도가 느려지고 탐색이 지속되는 반면, $M$이 작으면 업데이트가 가속화됩니다.

2.2 RL(MDP)로의 확장

ReMax를 마르코프 결정 과정(MDP)으로 확장하는 데에는 다음과 같은 과제가 있습니다:

1. 불확실성 단위: RL에서의 불확실성은 환경 전체(보상 및 전이)를 포괄합니다.
2. 재시도의 실행 가능성: 동일한 상태에서 여러 행동을 재시도하기 위해 환경을 물리적으로 리셋하는 것은 종종 불가능합니다.

이를 해결하기 위해, 저자들은 상태 $s$에서의 Q-값들의 $M$번 추출에 대한 기대 최대값을 나타내는 Q-함수 $Q^\pi_M(s, a)$를 사용하여 ReMax 목적 함수를 정의합니다. 목적 함수는 $Q$ 값들에 대한 불확실성을 포착하는 분포 $\mathcal{Q}$를 사용하여 다음과 같이 공식화됩니다:
$$J^M_{\text{ReMax}}(\pi, s, Q) := \mathbb{E}_{Q \sim \mathcal{Q}} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} Q(s, A_m) \right] \right]$$
여기서 분포 $\mathcal{Q}$는 (앙상블과 같은 명시적 모델링이나 딥 크리틱의 비정상성을 통해) Q-값에 대한 불확실성을 포착합니다.

2.3 정책 경사(Policy Gradient) 정식화

ReMax를 효율적으로 최적화하기 위해, 저자들은 단일 궤적 수익(single-trajectory return)으로부터 계산 가능한 새로운 정책 경사(PG) 추정기를 도출합니다.

• 나이브 접근법의 실패: 정책 경사 정리의 직접적인 적용은 에피소드 RL에서 불가능한, $M$개의 샘플링된 행동에 대한 모든 수익을 동시에 관찰할 것을 요구합니다.
• 기대 개선(Expected Improvement, EI) 재정식화: 저자들은 베이지안 최적화에서 빌려온 "기대 개선" 기반의 베이스라인을 도입합니다. 이들은 max 연산자를 행동별 항과 나머지 $M-1$개 추출의 최대값을 나타내는 베이스라인($W_{-m}$)으로 분해합니다.
• 폐쇄형 해(Closed-Form Solution): Q-값들을 정렬함으로써, 기대 개선 항에 대한 폐쇄형 표현식을 도출합니다. 이를 통해 단일 궤적 수익 $R(s, a)$와 현재 Q-추정치를 사용하여 그래디언트를 추정할 수 있습니다.
• 연속 파라미터 $m$: 정수형 재시도 횟수 $M$을 연속적인 실수 파라미터 $m > 0$으로 일반화합니다. 이를 통해 탐색-활용(exploration-exploitation) 트레이드오프를 미세하게 조정할 수 있습니다. 폐쇄형 해의 $(1 - C_j)^{M-1}$ 항은 $(1 - C_j)^{m-1}$로 대체됩니다.

2.4 RePPO 알고리즘

저자들은 ReMax를 근사 정책 최적화(PPO) 프레임워크 내에 구현하여 **ReMax PPO (RePPO)**를 만듭니다.

• 아키텍처: Q-크리틱을 사용하는 온-폴리시(on-policy) 액터-크리틱 방법입니다.
• 대리 목적 함수(Surrogate Objective): RePPO는 표준 어드밴티지(advantage)를 EI 기반 어드밴티지로 교체하여 표준 PPO 대리 함수를 수정합니다.
  $$A^+(t) = R^+(t) - b^+(s_t)$$
  여기서 $R^+(t) = \text{EIm}(R^\lambda_t, \pi_\theta, Q_\phi(s_t, \cdot))$ 이고, $b^+$는 EI 변환된 Q-값들의 기대값입니다.
• Q-교체 전략: 샘플링된 행동의 Q-값 저평가로 인해 개선 정도가 과대평가되는 것을 방지하기 위해, 저자들은 EI 항을 계산할 때 샘플링된 행동의 Q-값을 실제 궤적 수익으로 교체합니다. 이는 "개선"이 잠재적으로 편향된 추정치가 아닌 실제 수익을 기준으로 측정되도록 보장합니다.

3. 주요 기여

1. ReMax 목적 함수: 명시적인 탐색 보너스 없이 불확실성 하에서 탐욕적 보상 최대화를 통해 탐색을 유도하는 새로운 RL 목적 함수를 제안했습니다.
2. 이론적 도출: $M$번의 추출에 대한 기대 최대값에 대한 폐쇄형 표현식을 활용하여, 단일 궤적 수익으로부터 추정 가능한 ReMax를 위한 새로운 정책 경사 정식화를 도출했습니다.
3. 연속 제어: 이산적인 재시도 횟수 $M$을 연속적인 파라미터 $m$으로 일반화하여 탐색률을 정밀하게 조정할 수 있게 했습니다.
4. RePPO 알고리즘: ReMax를 PPO 프레임워크 내에 구현하여 탐색이 목적 함수 자체에서 어떻게 발현될 수 있는지를 입증하는 실용적인 딥 RL 알고리즘(RePPO)을 제시했습니다.

4. 실험 결과

4.1 밴딧 실험

• 확률적 성질: 2-암 밴딧에서 ReMax는 $M \ge 2$일 때 확률적 정책을 유도하는 반면, 표준 RL($M=1$)은 결정론적 정책을 생성합니다.
• 적응성: ReMax는 보상 불확실성의 크기에 따라 탐색을 적응시킵니다. 분산이 증가함에 따라, ReMax는 평균에 고정되어 있는 엔트로피 정규화 소프트맥스와 달리 희귀한 고보상 결과를 포착하기 위해 탐색을 증가시킵니다.
• 후회(Regret): 사후 밴딧 설정(Beta-Bernoulli 및 Gaussian-Gaussian)에서 ReMax는 Thompson Sampling 및 UCB와 대등하며, Softmax 베이스라인보다 우수한 경험적 하선형 누적 후회를 보여줍니다.

4.2 MinAtar 벤치마크

네 가지 게임(Breakout, Asterix, Freeway, Space Invaders)에서 평가되었습니다:

• 성능: RePPO($m \in [1.2, 1.4]$)는 표준 PPO 변형들(PPO-V, PPO-Q) 및 엔트로피 보너스나 RND 보너스를 가진 PPO보다 우수한 성능을 보였습니다.
• 탐색: RePPO는 명시적인 엔트로피 보너스가 없음에도 불구하고, 훈련 과정 내내 PPO보다 높은 정책 엔트로피를 유지했습니다.
• 파라미터 민감도: 성능은 $m=1.2$에서 $1.4$사이에서 정점을 찍었습니다. 더 큰$m$은 엔트로피 감소를 늦추어(탐색 유지) 지속시켰고, 더 작은$m$은 더 빠른 수렴을 가져왔으나 낮은 성능을 기록했습니다.
• 절제 연구(Ablation): 행동 독립적 베이스라인이나 Q-교체 전략을 제거하면 성능이 크게 저하되어, 이들의 필요성을 확인했습니다.

4.3 Craftax 벤치마크

대규모 오픈엔드 RL 환경인 Craftax에서 평가되었습니다:

• 성능: RePPO($m=1.2$)는 엔트로피 및 RND 보너스를 가진 PPO 변형들(각각 11.66%, 11.68%)과 경쟁력 있는 성능(최대 보상의 11.87%)을 달성했으며, 보너스가 없는 PPO를 능가했습니다.
• 확장성: RePPO는 명시적인 보너스 없이도 높은 엔트로피를 유지함으로써, 복잡하고 긴 호흡의 작업에서도 이 메커니즘이 확장 가능하다는 것을 입증했습니다.

5. 의의 및 주장

본 논문은 ReMax가 다음과 같은 이유로 전통적인 탐색 방법의 유망한 대안이 될 수 있다고 주장합니다:

• 명시적 보너스의 필요성 제거: 탐색은 재시도를 통한 기대 최대 수익을 최대화하려는 목적 함수으로부터 자연스럽게 발생합니다.
• 알고리즘 설계의 단순화: 호기심 보너스를 설계하거나 명시적인 사후 모델을 유지하는 데 따르는 계산적 오버헤드와 복잡성을 피합니다.
• 미세한 제어 제공: 연속 파라미터 $m$을 통해 탐색-활용 트레이드오프를 정밀하게 조정할 수 있습니다.

저자들은 자신들의 딥 RL 실험이 주로 확률적 탐색(증가된 정책 엔트로피)을 보여주었지만, 이론적 프레임워크는 명시적인 불확실성 모델링(예: 앙상블)과 결합될 경우 심층 탐색(시간적으로 일관된 정보 수집)을 지원한다고 언급합니다. 또한, 이 메커니즘을 LLM 분야의 pass@K 목적 함수와 유사한 맥러닝(reasoning) 작업에 적용할 수 있는 일반적인 원칙으로 포지셔닝합니다.

저자들은 딥 RL 설정에 대한 공식적인 후회 경계(regret bounds) 도출은 향후 과제로 남겨두었으며, 현재의 결과는 경험적인 효과의 입증임을 밝히며 이론적 주장을 겸손하게 서술했습니다.