On the Role of Computation in Reinforcement Learning

기술 요약: 강화 학습에서 계산의 역할에 대하여

문제 정의
강화 학습(RL)의 표준적인 관점은 정책을 상태를 행동으로 매핑하는 정적 함수로 취급하며, 결정의 복잡도와 상관없이 고정된 양의 계산량을 소비한다. 이 패러다임은 파라미터 수(메모리)와 계산량(시간)을 혼동한다. 파라미터 수를 늘리는 것(무어의 법칙)이 일반적인 전략으로 사용되어 왔으나, 최적의 결정을 내리는 데 필요한 계산량은 서로 다른 상태에 따라 수 차수(orders of magnitude)까지 차이가 날 수 있다. 정적이고 거대한 정책은 종종 비효율적이며, 계산 능력이 제한된 정책은 더 긴 호라이즌(longer-horizon)의 과업에 일반화되지 못하고 훈련 분포에 과적합된 휴리스틱을 학습할 위험이 있다. 본 논문은 RL에서 계산과 파라미터를 구분하는 공식적인 언어가 부재함을 지적하며, 고정된 파라미터를 가진 정책이 가변적이고 증가된 계산 시간으로부터 이득을 얻을 수 있는지 조사한다.

방법론
본 논문은 이론적 정형화와 경험적 검증이라는 두 가지 상호 보완적인 관점을 통해 문제에 접근한다.

1. 이론적 프레임워크:

   • 저자들은 RL 정책을 튜링 머신을 사용하는 유한한 계산 모델로 정형화한다.
   • 저자들은 시간 제한적 정책($\Pi_t$)을 $t(|s|)$ 단계 내에 정지하는 튜링 머신에 의해 구현 가능한 정책으로 정의한다.
   • 저자들은 **정책 계층 정리(Policy Hierarchy Theorem)**를 도입하여, 시간 구성 함수 $g(n) \in o(t(n)/\log t(n))$에 대해, 더 높은 계산 예산($\Pi_t$)을 가진 정책이 더 낮은 예산($\Pi_g$)을 가진 정책보다 임의로 더 나은 성능을 보이는 MDP가 존재함을 증명한다.
   • 또한 **장기 호라이즌 일반화 정리(Long Horizon Generalization Theorem)**를 통해, 저계산 정책은 훈련 과업에는 적응(훈련 데이터의 최적 가치 함수와 일치)할 수 있으나 더 긴 호라이즌의 테스트 과업에는 실패하는 반면, 고계산 정책은 이러한 확장된 과업을 해결할 수 있음을 입증한다.

2. 아키텍처 제안:

   • 이 이론들을 테스트하기 위해, 저자들은 **보간 순환 유닛(Interpolation Recurrent Unit, IRU)**이라 불리는 최소 순환 아키텍처를 제안한다.
   • IRU는 이전 셀 상태와 새로운 로컬 계산 사이를 보간하는 두 개의 선형 레이어(Forget 및 Input)로 구성된 LSTM/GRU 블록의 단순화된 변형이다.
   • 이 아키텍처는 순방향 패스(forward pass) 동안 이 블록을 $N$번 적용(순환 단계)함으로써, 고정된 파라미터 수를 유지하면서도 가변적인 계산량($N$)을 사용할 수 있게 한다.
   • 전체 네트워크(IRU-$N$)는 초기 선형 레이어, 스킵 연결(skip connection)이 포함된 $N$개의 순환 블록, 그리고 최종 출력 헤드로 구성된다.

3. 실험 설정:

   • 실험은 이산 도메인(Boxpick, Lightsout)과 연속 도메인(OGBench)을 아우르는 31개 과업에 걸쳐 수행되었으며, 온라인 및 오프라인 RL 설정을 모두 포함한다.
   • 베이스라인으로는 표준 피드포워드 네트워크(MLP)와 잔차 네트워크(ResNet)가 포함되었다. 결정적으로, ResNet 베이스라인은 유사한 유효 깊이(계산량)를 갖도록 설계되었으나 파라미터 수는 훨씬 많았고(최대 5배), MLP는 유사한 파라미터를 가지되 계산량은 적었다.
   • 연구는 훈련 과업의 성능뿐만 아니라, 일반화 능력을 측정하기 위해 보지 못한 더 긴 호라이즌의 테스트 과업에서의 성능을 평가했다.

주요 기여

• 계산 제한적 정책의 정형화: 본 논문은 계산 시간(파라미터 수와 구별됨)을 늘리는 것이 이론적으로 낮은 계산량의 정책이 해결할 수 없는 문제를 해결하고 일반화 성능을 높일 수 있음을 보여주는 최초의 공식적 증명을 제공한다.
• 최소 순환 아키텍처: 파라미터 수를 늘리지 않고 순환 단계를 통해 계산량을 확장할 수 있는 경량 아키텍처인 IRU를 도입한다.
• 계산 가치(Value of Compute) 지표: POMDP에서의 정보 가치(Value of Information)와 유사한 수치적 척도인 **계산 가치(VoC)**를 제안한다. 이 지표는 에이전트가 특정 단계 동안 계산 예산을 일시적으로 늘렸을 때 발생하는 가치의 이득 또는 손실을 추정한다.
• 계산과 파라미터의 분리: 성능 향상이 단순히 모델 용량(파라미터)의 증가가 아닌 증가된 표현력(계산량)에서 기인한다는 경험적 증거를 제시한다.

결과

• 성능 스케일링: 이산 및 연속 환경 모두에서 순환 단계($N$)를 1에서 10으로 늘림에 따라 성공률이 유의미하게 향м상되었다. Boxpick 및 OGBench와 같은 도전적인 과업에서는 성능이 최대 10배까지 증가했다.
• 일반화: IRU 정책은 MLP 및 ResNet에 비해 짧은 호라이즌 과업에서 훈련되었음에도 불구하고 보지 못한 긴 호라이즌 과업에서 훨씬 더 나은 일반화 성능을 보였다. 특히, IRU는 긴 호라이즌 평가 과업에서 5배 더 많은 파라미터를 가진 ResNet보다 우수한 성능을 보였다.
• 샘플 효율성: IRU 아키텍처는 더 높은 샘ming 효율성을 보였으며, 더 적은 환경 단계(environment steps) 내에서 더 높은 점진적 성능(asymptotic performance)에 수렴했다.
• 개선 원천: "결합된(Yoked)" 실험(능동적 에이전트가 수집한 데이터로 수동적 에이전트를 훈련)을 통해, 추가 계산의 주요 이득은 개선된 탐사(exploration)나 데이터 품질이 아니라 정책의 표현력(복잡한 솔루션을 학습하는 능력)에서 온다는 것을 밝혔다. 저계산 능동 에이전트의 데이터로 훈련된 수동 에이전트는 스스로 고계산을 사용하지 않는 한 성능이 저조했다.
• 절제 연구(Ablation): IRU 아키텍처는 속도와 파라미터 효율성 측면에서 표준 LSTM 및 순환 ResNet보다 뛰어난 성능을 보였으며, 이는 추가적인 계산을 효과적으로 활용하기 위해 특정 게이팅 메커니즘이 필요함을 시사한다.

의의 및 주장
본 논문은 RL의 관점을 정적 함수 근사에서 시간과 메모리가 서로 다른 축을 갖는 계산적 관점으로 전환할 것을 주장한다. 저자들의 주장은 다음과 같다:

1. 계산은 별개의 자원이다: 계산 시간을 늘리는 것은 가설 클래스의 크기(파라미터)를 늘리지 않고도 성능과 일반화를 입증 가능하게 향상시킬 수 있으며, 이를 통해 거대 정적 모델과 관련된 과적합 문제를 피할 수 있다.
2. 반복을 통한 일반화: 반복적 계산은 정책이 더 긴 호라이즌까지 외삽(extrapolate)할 수 있는 알고리즘적 솔루션을 학습할 수 있게 하며, 이는 언어 모델에서 관찰되었으나 사전 훈련이나 멀티 태스크 커리큘럼 없이 RL에서 탐구되지 않았던 현상이다.
3. 정적 관점의 한한계: 결과는 표준 MDP 가정(예: 결정론적 최적 정책의 존재)이 계산적 제약 하에서는 성립하지 않을 수 있음을 시사하며, 이는 왜 완전 관측된 과업에서도 비마르코프(non-Markov) 정책이 때때로 필요한지를 설명할 수 있다.

저자들은 자신들의 작업이 이러한 효과를 격리하기 위해 최소한의 아키텍처를 사용했지만, 그 결과는 미래의 RL 시스템이 현재 상태의 난이도에 따라 계산량을 동적으로 조절하는 적응형 계산 전략을 고려해야 함을 시사한다고 결론짓는다.