Adaptive Joint Testing of Policies in Discounted Markov Decision Processes

Essence

Figure 1. The reset-chain instance. State sL is a rewarding reset state: it yields reward 1 and then deterministically r

단일 적응적 궤적(single adaptive trajectory)만을 이용해 유한한 정책 집합의 가치 부호(sign)를 fixed-confidence로 동시에 검증하는 문제를 다루고, 이를 위한 instance-specific 특성 시간 T⋆(p)를 정의한 뒤 이를 점근적으로 달성하는 온라인 알고리즘 PT-ACE(μ)를 제안한다.

Motivation

Known: discounted tabular MDP에서 단일 정책에 대한 fixed-policy testing은 static sampling 하에서 instance-specific lower bound와 scalar-frontier 기반 stopping rule (Ariu et al., 2025)로 잘 연구되어 있으며, best-policy identification 등 온라인 pure exploration에서의 navigation 문제도 선행 연구(Al Marjani et al., 2021)를 통해 다루어졌다.
Gap: 기존 연구는 단일 정책을 static allocation 하에서 검증하는 데 집중했지만, 실제로는 여러 정책 후보를 하나의 공유된 adaptive trajectory로부터 동시에(jointly) 검증해야 하는 상황이 많고, 이 경우 학습자는 state-action count를 직접 제어할 수 없고 미지의 transition kernel에 의존하는 occupancy polytope 위에서 행동해야 하므로 bottleneck allocation 학습과 trajectory 실현(navigation)이라는 새로운 난제가 발생한다.
Why: 여러 controller, treatment rule, recommendation policy 후보를 하나의 상호작용 데이터 스트림으로부터 동시에 인증해야 하는 실용적 시나리오(정책 배포 전 안전성/성과 검증 등)에서, 각 정책마다 별도로 데이터를 수집하는 것은 비효율적이며 이론적으로 최적인 단일 궤적 기반 joint 인증 방법이 필요하기 때문이다.
Approach: occupancy measure에 대한 max-min 프로그램으로 정의되는 characteristic time T⋆(p)를 information-theoretic 벤치마크로 도출하고, exchange-based 학습, trajectory 호환 navigation, 병렬 certified stopping을 결합한 PT-ACE(μ) 알고리즘으로 이 벤치마크에 점근적으로 접근한다.

Achievement

Lower bound 확립: stationary occupancy measure와 sign-flipped alternative에 대한 max-min program으로 characteristic time T⋆(p)를 정의하고, 모든 δ-probably correct 전략이 liminf E_p[τ_δ]/log(1/δ) ≥ T⋆(p)를 만족함을 증명했다.
PT-ACE(μ) 알고리즘 제안: exchange layer(bottleneck allocation 학습), navigation layer(occupancy target을 executable behavior policy로 변환), stopping layer(정책별 certified parallel test)의 3단 결합 구조를 설계했다.
Exchange layer 이론 보장: 데이터에 따라 움직이고 모든 state-action 좌표에 양의 floor를 부과하는 empirical occupancy domain 위에서도, cut vector가 균일하게 통제되고 평균 exchange iterate가 vanishing error와 floor-dependent factor까지 최적 joint testing frontier를 달성함을 증명했다.
Navigation layer 이론 보장: 단일 adaptive trajectory가 생성하는 empirical allocation이 exchange 평균과 동일한 bottleneck frontier 값을 vanishing error까지 상속함을 증명했다.
최종 upper bound: 세 layer를 결합해 admissible fixed floor μ>0에 대해 limsup E_p[τ_δ]/log(1/δ) ≤ (1+c(μ,p))T⋆(p) (c(μ,p)→0 as μ→0)를 증명, 즉 μ→0 극한에서 정확한 instance-specific 특성 시간을 회복함을 보였다.

How

Figure 1. The reset-chain instance. State sL is a rewarding reset state: it yields reward 1 and then deterministically r

문제 설정: discounted tabular MDP (S, A, γ, 미지의 p, 알려진 reward r, 초기분포 ρ)에서 유한 target policy 집합 Πtest에 대해 각 정책 가치의 부호 Ansj(p)=sign(V_{p,j}(ρ))를 확률 1-δ 이상으로 인증
하한: stationary occupancy measure와 sign-flipped alternative 상의 max-min program으로 T⋆(p) 정의, 표준 change-of-measure 논증으로 asymptotic lower bound 도출
부록 A의 reset-chain example을 통해 on-policy testing은 exponential sample이 필요하지만 active navigation은 polynomial time에 informative transition row를 탐색 가능함을 보여 active-allocation 접근의 필요성을 예증(Figure 1)
PT-ACE(μ) 알고리즘: (1) exchange layer - stabilized exchange-based 학습으로 bottleneck occupancy allocation 학습(skip–reanchor safeguard, uniform cut-bound argument, transported interior benchmark로 moving domain 문제 처리), (2) navigation layer - averaged occupancy로부터 trajectory-compatible behavior policy 생성, (3) stopping layer - Ariu et al. (2025)의 certified fixed-policy testing solver를 각 target policy에 대해 병렬 적용, 모든 policywise lower certificate가 양수일 때만 정지
trajectory-side anchor-policy ergodicity condition과 certified numerical subroutine, vanishing input tolerance 하에서 δ-correctness와 점근적 sample complexity upper bound를 증명

Originality

단일 정책 static testing에서 다중 정책 joint testing으로 문제를 확장하고, 이를 위한 bottleneck testing frontier 기반 instance-specific characteristic time T⋆(p)를 새롭게 정의
여러 정책에 걸친 공유 occupancy allocation을 학습하는 exchange layer와, 이를 단일 궤적으로 실현하는 navigation layer를 결합한 3단 구조(exchange-navigation-stopping)를 설계, 특히 데이터에 따라 움직이고 positive floor가 부과된 occupancy domain 위에서의 online learning을 위한 skip–reanchor safeguard와 uniform cut-bound argument라는 기술적 장치 도입
Ariu et al. (2025)의 fixed-policy testing 프레임워크를 정책별 certified stopping 모듈로 재사용하면서, 이를 joint/online/navigation 문제로 비자명하게 확장

Limitation & Further Study

upper bound는 fixed floor μ>0에 대해서만 증명되며, μ→0 극한에서 정확한 T⋆(p)를 회복하지만 실제로 유한한 μ에서는 (1+c(μ,p)) 배의 interiorization factor가 남아 완전한 최적성은 극한에서만 성립
navigation 증명은 uniform-action state-action chain의 irreducibility/aperiodicity(anchor-policy ergodicity)를 요구하는데, 이는 모든 MDP 인스턴스에서 자연스럽게 보장되지 않는 제약 조건
admissible floor 범위가 instance-dependent하여 사전에 알기 어려울 수 있고, 알고리즘 실행 가능 조건(|S||A|μ≤1)과 이론적 보장이 성립하는 floor 범위 사이에 간극이 존재
후속 연구로 non-tabular(함수 근사) 설정으로의 확장, anchor-policy ergodicity 조건의 완화, 유한 δ 또는 유한 샘플 영역에서의 non-asymptotic 성능 분석 등이 필요해 보임

같이 보면 좋은 논문

Improving generalization of robot locomotion policies via sharpness-aware reinforcement learning

기반 연구SPECTER2 유사도 0.91로 Reinforcement Learning Policy Optimization와 Scientific AI for Physics and Environment가 맞닿아, 'Improving generalization of robot locomotion policies via sharpness-aware reinforcement learning'가 이 ICML 2026 논문의 배경·대안·응용 맥락을 보완한다.

Kimi k1.5: Scaling reinforcement learning with llms

기반 연구SPECTER2 유사도 0.90 기준으로 'Adaptive Joint Testing of Policies in Discounted Markov Decision Processes'의 AI4S 방법론을 'Kimi k1.5: Scaling reinforcement learning with llms'의 과학 생산·평가 맥락과 함께 보면 연구 자동화의 의미를 입체적으로 볼 수 있다.

Trust, But Verify: A Self-Verification Approach to Reinforcement Learning with Verifiable Rewards

기반 연구SPECTER2 유사도 0.91로 Reinforcement Learning Policy Optimization와 LLM Benchmarking and Agent Evaluation가 맞닿아, 'Trust, But Verify: A Self-Verification Approach to Reinforcement Learning with Verifiable Rewards'가 이 ICML 2026 논문의 배경·대안·응용 맥락을 보완한다.

YC-Bench: Benchmarking AI Agents for Long-Term Planning and Consistent Execution

기반 연구SPECTER2 유사도 0.91로 Reinforcement Learning Policy Optimization와 Agentic AI for Scientific Automation가 맞닿아, 'YC-Bench: Benchmarking AI Agents for Long-Term Planning and Consistent Execution'가 이 ICML 2026 논문의 배경·대안·응용 맥락을 보완한다.

E-valuator: Reliable Agent Verifiers with Sequential Hypothesis Testing

기반 연구instance-specific 최적 샘플 복잡도 이론이 본 논문의 T⋆(p) 정의에 이론적 기반을 제공함

ICMAPE: In-Context Multiagent Pure Exploration

기반 연구fixed-confidence 검증의 이론적 기반을 제공한다.

후속 연구pure-exploration 문제의 이론적 기반을 제공하는 선행 연구이다.

Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

다른 접근정책 검증 문제를 단일 궤적이 아닌 다른 방식으로 접근한다.

SIA-W: Self-Improving Agents with Test-Time Weight Updates

다른 접근적응적 실험 설계 및 정책 평가에서 유사한 문제 설정을 공유함

EMA Policy Gradient: Taming Reinforcement Learning for LLMs with EMA Anchor and Top-k KL

후속 연구instance-specific 특성 시간 개념을 확장한 후속 연구이다.