A Goal-Set Characterization of Task Composition in the Boolean Task Algebra

기술 요약: 불리언 태스크 대수(Boolean Task Algebra)에서의 태스크 구성을 위한 목표 집합 기반 특성화

문제 정의
불리언 태스크 대수(BTA)는 목표 달성 태스크에 불리언 연산(논리곱, 논리합, 부정)을 부여함으로써 강화 학습(RL)에서 제로샷 태스크 구성을 가능하게 하는 프레임워크를 제공한다. 기존의 공식화에서는 목표 집합 $G$에 대해 최적의 표현 완결성을 보장하기 위해, 에이전트가 유니버설(universal) 및 엠티(empty) 태스크 외에도 $O(\lceil \log_2 |G| \rceil)$ 크기의 기저 태스크(base tasks) 집합을 학습해야 한다고 상정한다. 이러한 기저 태스크들은 확장된 Q-값 함수(extended Q-value functions)에 대한 요소별 연산을 통해 복합적인 합성 태스크를 위한 정책을 도출하는 데 사용된다. 그러나 이 방식은 필요한 기저 태스크의 수로 인해 학습 비용이 높고, 가치 함수를 결합하는 복잡성으로 인해 구성 시 계산 비용이 발생한다.

방법론 및 이론적 분석
본 논문은 결정론적 마르코프 결정 과정(MDP) 및 흡수 목표 상태(absorbing goal states) 내에서 BTA의 구조적 가정을 재검토한다. 저자들은 최적 확장 Q-값 함수의 공간에서 발생하는 "붕괴(collapse)"를 정형화한다.

1. 표현 붕괴(Representational Collapse): 저자들은 결정론적 MDP에서 모든 최적 확장 Q-값 함수가 오직 두 가지 구성 요소, 즉 유니버설 태스크($M_U$, 모든 목표에 대해 가장 높은 종단 보상을 할당)와 엠티 태스크($M_\emptyset$, 모든 목표에 대해 가장 낮은 종단 보상을 할당)의 확장 Q-함수에 의해 완전히 결정됨을 증명한다.

   • 명제 1 및 보조정리 1: 임의의 태스크 $M$에 대하여, 특정 목표 $g$에 대한 최적 확장 Q-값 함수 $\bar{Q}^*_M(s, g, a)$는 만약 $g$가 $M$의 희망 목표라면 유니버설 태스크의 슬라이스와 동일하며, $g$가 희망 목표가 아니라면 엠티 태스크의 슬라이스와 동일하다.
   • 시사점: 원래의 BTA에서 제안된 로그 단위의 기저 태스크를 학습하는 것은 이미 유니버설 및 엠티 태스크에 포함된 정보를 중복하는 것이므로 불필요하다.

2. 목표 집합 기반 구성(Goal-Set Based Composition): 이 붕러를 바탕으로, 본 논문은 새로운 구성 방법을 제안한다. 에이전트는 불리언 기저 태스크를 학습하는 대신 유니버설 및 엠티 태스크만을 학습한다. 구성은 다음과 같이 수행된다:

   • 새로운 합성 태스크를 위한 희망 목표 집합 $G^+_M$을 식별한다.
   • 사전 학습된 유니버설 및 엠티 Q-함수로부터 적절한 "슬라이스"를 선택함으로써 새로운 확장 Q-값 함수를 구축한다.
   • 정리 1: 태스크 대수와 목표의 멱집합(power set) 사이의 동형(isomorphism) 관계를 확립하여, 가치 함수의 요소별 조작 대신 목표 집합에 대해 직접 논리 연산을 수행할 수 있도록 한다.

3. 확률적 MDP: 본 논문은 이러한 단순화가 확률적 MDP에서도 유효한지 조사한다. 명제 2는 확률적 환경에서 목표 간의 독립성이 사라짐을 보여주는 반례를 제시한다. 최악의 경우, $2^{|G|} - 1$개의 가능한 비어 있지 않은 모든 부분 집합에 대해 서로 다른 최적 정책이 필요하다. 결과적으로, 확률적 환경에서의 최적 구성은 지수적인 수의 정책을 고려해야 할 수도 있으며, 결정론적 붕괴는 성립하지 않는다.

주요 기여

1. 표현적 한계의 정형화: 저자들은 BTA 표현 공간의 붕괴를 정형화하여, 결정론적 MDP에서 유니버설 및 엠티 태스크 이상의 기저 태스크를 학습하는 것이 불필요함을 증명하였다. 이는 학습 비용을 $O(\lceil \log_2 |G| \rceil)$에서 상수($O(1)$, 단 두 개의 태스크 학습)로 줄인다.
2. 효율적인 구성 방법: 복잡한 가치 함수 연산을 단순한 배열 조회(array lookup) 및 슬라이스 선택으로 대체하는 새로운 방법을 제안한다. 이는 구성 계산 비용을 $O(\lceil \log_2 |G| \rceil \times |G| \times |S| \times |A|)$에서 $O(|G| \times |S| \times |A|)$로 감소시킨다.
3. 확률적 한계 식별: BTA 방식의 구성이 확률적 MDP에서 갖는 근본적인 한계를 식별하여, 목표 슬라이스 간의 독립성이 깨짐으로써 최적 구성을 위해 지수적인 자원이 필요할 수 있음을 보여준다.

실험 결과
저자들은 표 형식(tabular), 시각적(visual), 함수 근사(function-approximation) 및 연속 제어(continuous-control) 도메인(Rooms, Boxman, Office Gridworld, Safety Gym)에서 제안된 방법을 평가한다.

• 성능: 실험을 통해 추가적인 기저 태스크를 학습하는 것이 수렴 시 더 나은 성능을 내지 못함을 확인하였다. 목표 집합 방법(유니버설 및 엠티 태스크만 사용)은 원래의 기저 태스크 방법과 동일한 최적 정책을 달성한다.
• 수렴 속도: Rooms 환경에서, 목표 집합 방법은 총 학습 예산(training budget) 기준으로 측정했을 때 기저 태스크 방법보다 더 빠르게 최적 정책으로 수렴한다. 이는 수렴 전에는 해로울 수 있는 max/min 연산을 통한 가치 함수 혼합을 피하기 때문이다.
• 구성 시간: 목표 집합 방법은 기저 태스크 접근 방식에 비해 일관되게 현저히 낮은 구성 시간을 달성한다. 이 성능 격차는 목표의 수가 증가함에 따라 더욱 벌어진다.
• 스킬 머신(Skill Machines): 선형 시계열 논리(LTL) 명세를 처리하는 스킬 머신 프레임워크에 적용했을 때, 제안된 방법은 기존 프레임워크의 학습 효율성을 유지하면서 구성 시간을 더욱 단축한다.

의의 및 주장
본 논문은 불리언 태스크 대수 프레임워크가 결정론적 설정에서 최적성을 희생하지 않고도 단순화될 수 있다고 주장한다. 최적 확장 Q-값 함수의 공간이 두 개의 근본적인 함수로 붕괴된다는 점을 인식함으로써, 저자들은 원래 요구되었던 로그 단위의 기저 태스크가 불필요함을 입증하였다. 이는 학습 비용과 구성 시간을 모두 줄이는 더 직접적인 태스크 구성 공식을 이끌어낸다. 본 연구는 왜 더 단순한 구성 전략이 작동하는지에 대한 이론적 토대를 제공하며, 이러한 효율성이 보장되는 특정 조건(결정론)을 명시하는 동시에, 최적 구성이 지수적으로 복잡해질 수 있는 확률적 환경에 대해서는 주의를 준다.