기술 요약: 행동 유발 관측(Action-Triggered Observations)을 통한 강화 학습

1. 문제 정의

본 논문은 상태 관측의 가용성이 외생적이거나 고정된 것이 아니라, **행동에 의해 유발(action-triggered)**되는 특정 클래스의 부분 관측 마르코프 결정 과정(POMDP)을 다룬다. 표준적인 강화 학습(RL)에서 에이전트는 매 행동 후에 새로운 상태를 관측한다. 그러나 임상 진단이나 금융 거래와 같은 많은 실제 시나리오에서는 상태 관측을 얻는 데 비용이 들거나, 신뢰할 수 없거나, 혹은 특정 행동을 통해 관측을 유발해야 하는 경우가 있다.

저자들은 이 설정을 **행동 유발 간헐적 추적 마르코프 결정 과정(ATST-MDPs)**으로 정식화한다.

• 메커니즘: 에이전트가 상태 $s$에서 행동 $a$를 실행하면, 보상을 받고 환경은 $s'$로 전이된다. 결정적으로, $s'$는 항상 관측되는 것은 아니다. 확률 $\beta(a)$에 따라 "관측 이벤트"(데이터 버스트)가 발생하여 $s'$와 마지막 버스트 이후의 누적 보상이 공개된다. 확률 $1-\beta(a)$에 따라 상태 피드백은 제공되지 않는다.
• 과제: 에이전트는 불확실성을 줄이기 위해 관측을 유발하는 행동(더 높은 $\beta(a)$를 가진 행동)을 선택함으로써 제어 정책을 최적화하는 동시에, 정보 획득의 비용과 제어 성능 사이의 균형을 맞추어야 한다.
• 차별점: 관측이 노이즈가 섞여 있지만 빈번하게 발생하는 일반적인 POMDP나, 피드백이 단순히 늦게 오는 외생적 지연(exogenous delays)이 있는 RL과 달리, ATST-MDP는 에이전트의 행동 선택이 상태 공개 빈도를 직접 결정하는 **내생적 지연(endogenous delays)**을 특징으로 한다.

2. 방법론

2.1 확장된 상태 공간 및 벨만 방정식

부분 관측성을 처리하기 위해, 저자들은 확장된 상태 공간 $\mathcal{X} = \mathcal{S} \times \mathcal{A}^{<\infty}$를 정의한다. 확장된 상태 $x = (s_1, a_1, \dots, a_n)$는 마지막으로 관측된 상태 $s_1$과 그 이후 수행된 행동 시퀀스로 구성된다.

• 충분성: 확장된 상태는 이력(history)에 대한 충분 통계량(sufficient statistic) 역할을 하며, 이를 통해 문제를 $\mathcal{X}$ 상의 완전 관측된 MDP로 취급할 수 있게 한다.
• 역학(Dynamics): $\mathcal{X}$ 상의 전이는 혼합 형태를 띤다. 확률 $\beta(a)$에 따라 상태는 새로운 관측 상태로 리셋되며($x \leftarrow s'$), 확률 $1-\beta(a)$에 따라 행동 시퀀스가 추가된다($x \leftarrow x \cdot a$).
• 벨만 방정식: 저자들은 이 확장된 공간에서의 가치 함수 $V^\pi$ 및 $Q^\pi$에 대한 벨만 최적 방정식을 유도하여, 최적의 확장 정책 $\pi^*$의 존재를 증명한다.

2.2 행동 시퀀스 재구성

확장된 상태 공간이 무한히 분기된다는 점을 인식하여, 저자들은 데이터 버스트의 **갱신 구조(renewal structure)**에 기반한 재구성을 제안한다. 즉, 에이전트는 매 데이터 버스트마다 행동 단위로 결정하는 대신, 다음 관측이 발생할 때까지 실행할 행동 시퀀스 $a \in \mathcal{A}^\mathbb{N}$를 결정한다.

• 이는 문제를 $(\mathcal{S}, \mathcal{A}^\mathbb{N})$에 대한 의사 결정 과정으로 변환한다.
• 가치 함수 $K^\pi(s, a)$는 상태 $s$에서 행동 시퀀스 $a$를 실행하여 다음 데이터 버스트가 발생할 때까지 누적되는 기대 할인 보상과, 공개된 상태로부터의 지속 가치(continuation value)를 나타낸다.

2.3 선형 MDP 가정 하의 선형 표현

무한 차원의 행동 시퀀스 공간을 다룰 수 있도록, 본 논문은 전이 커널과 보상이 특징 맵(feature map) $\phi(s, a)$에 대해 선형이라는 선형 MDP 구조(가정 4.1)를 가정한다.

• 핵심 통찰: 이 가정 하에서, 행동 시퀀스 가치 함수 $K^\pi$는 유한 차원 특징 맵 $\psi: \mathcal{S} \times \mathcal{A}^\mathbb{N} \to \mathbb{R}^{2d}$에 대해 선형 표현을 갖는다.
• 구성: 특징 맵 $\psi$는 행동 행렬 $M_a$(전이 역학에서 유도됨)와 관측 확률 $\beta_a$를 사용하여 구축된다. 구체적으로, $\psi$는 행동 시퀀스 동안 특징의 진화와 각 단계에서 데이터 버스트가 발생할 확률을 인코딩한다.
• 결과: $K^\pi(s, a) = \langle \psi(s, a), v^\pi_{1,2} \rangle$이며, 여기서 $v^\pi_{1,2}$는 정책에 의존하는 벡터이다. 이를 통해 무한한 행동 공간에도 불구하고 표준적인 회귀 기반 방법론을 사용할 수 있다.

2.4 추정 및 학습 알고리즘

본 논문은 ATST-LSVI-UCB(Action-Triggered Sporadically Traceable Least-Squares Value Iteration with Upper Confidence Bounds)를 제안한다.

• 특징 추정: 실제 특징 맵 $\psi$를 알 수 없으므로, 알고리즘은 리지 회귀(ridge regression)와 경험적 평균을 사용하여 탐색 데이터를 통해 기저의 행동 행렬 $M_a$와 관측 확률 $\beta_a$를 추정한다. 정리 4.6과 코롤러리 4.9는 $\psi$의 $\epsilon$-허용 근사치를 구축하기 위한 비점근적 샘플 복잡도 경계를 제공한다.
• 알고리즘: 알고리즘은 기하학적 호라이즌(geometric horizons)을 가진 에피소드 단위로 작동한다. 추정된 특징 맵에 대해 후방 가치 반복(backward value iteration)을 수행하여 낙관적인 가치 추정치(UCB 보너스 사용)를 계산하고, 탐욕적인 행동 시퀀스를 실행한다.
• 최적화: 행동 공간은 무한하지만, $\max_a K(s, a)$ 최적화는 특징 맵의 컴팩트한 이미지(compact image) 상에서 수행된다. 실제로는 유한 깊이 또는 결국 주기적인(eventually periodic) 시퀀스로 제한하여 근사할 수 있다.

3. 주요 기여

1. ATST-MDP의 정식화: 행동에 의해 관측 가능성이 결정되는 환경을 위한 새로운 프레임워크를 제시하며, 이는 표준 MDP와 일반적인 POMDP 사이의 간극을 메운다.
2. 이론적 토대: 확장된 상태 공간에서의 벨만 방정식을 유도하고 최적 정책의 존재를 증명하였다.
3. 선형 표현: 선형 MDP 가정 하에서 행동 시퀀스에 대한 가치 함수가 유한 차원 특징 맵에 대해 선형임을 입증하여 효율적인 학습을 가능하게 하였다.
4. 알고리즘 및 후회 경계(Regret Bounds): 낙관적 가치 반복 알고리즘인 ATST-LSVI-UCB를 제안하였다. 저자들은 에피소드 학습에 대해 $\tilde{O}(\sqrt{d^3 K (1-\gamma)^{-3}})$의 후회 경계를 증명하였으며, 이는 완전 관측된 선형 MDP의 알려진 최적 속도와 일치한다.
5. 샘플 복잡도: 데이터로부터 행동 시퀀스 특징 맵을 추정하기 위한 샘플 복잡도 보장을 확립하였으며, 이는 차원 $d$에 대해서는 다항식 수준이지만 상태 공간의 크기 $|\mathcal{S}|$와는 독립적임을 보여준다.

4. 결과

• 이론적 결과: 후회 경계는 부분 관측성과 행동 유발 지연이라는 추가된 복잡성에도 불구하고, 완전 관측된 선형 MDP의 최신 기술(state-of-the-art)과 일치한다. 이 경계는 특징 차원 $d$, 에피소드 수 $K$, 그리고 할인 계수 $(1-\gamma)$의 역수에 따라 스케일링된다.
• 실험적 결과: 두 가지 테이블 환경인 RiverSwim(탐색 중심)과 RiverBalance(안정화 중심)에 대한 실험을 통해 알고리즘의 실행 가능성을 입증하였다.
  • RiverSwim에서는 낮은 $\beta$ 값(희소한 관측)이 오히려 더 긴 오픈 루프 결합(탐색)을 장려함으로써 수렴을 가속화하는 놀라운 결과를 보였다.
  • RiverBalance에서는 높은 $\beta$ 값(빈번한 관측)이 더 높은 보상을 얻었으며, 이는 안정성을 유지하기 위해 상태 의존적 교정이 필요한 작업의 특성을 반영한다.
  • 결과는 최적의 관측 빈도가 작업에 따라 달라짐을 강조한다.

5. 의의 및 주장

본 논문은 행동에 의해 관측이 유발되는 환경을 위한 강화 학습의 이론적 토대를 제공한다고 주장한다. 그 의의는 다음과 같다:

• 간극 해소: 일반적인 POMDP 방법론이 계산적 불가능성으로 인해 어려움을 겪는 특정적이고 실질적으로 중요한 클래스(능동적 지각, 비용이 드는 센싱 등)를 다룬다.
• 효율성(Tractability): 데이터 버스트에 의해 유도되는 갱신 구조와 선형 MDP 가정을 활용함으로써, 다루기 힘든 부분 관측 문제를 다루기 쉬운 선형 회귀 문제로 변환한다.
• 최적성: 완전 관측 환경과 유사한 후회 속도를 달성함으로써, 구조를 이해하고 활용한다면 간헐적 관측의 "비용"을 완화할 수 있음을 시사한다.
• 보상 없는 추정(Reward-Free Estimation): 특징 맵 추정은 보상과 무관하게 이루어진다. 즉, 환경의 구조적 학습(역학 및 관측 확률)을 특정 보상 함수와 분리할 수 있어 유연한 정책 적응이 가능하다.

저자들은 향-후 연구로서 무한한 행동 시퀀스 최적화를 위한 효율적인 근사 기법 설계와, 사전 수집된 탐색 데이터 없이도 특징 추정치를 적응적으로 정교화하는 완전 온라인 알고리즘 개발에 집중해야 한다고 언급하였다.