상태 의존적인 실행 가능 행동 집합을 갖는 마르코프 결정 과정에서의 벨만-테일러 점수 해독

Bellman-Taylor Score Decoding for Markov Decision Processes with State-Dependent Feasible Action Sets

운영 연구에서 많은 마르코프 결정 과정(MDP)은 상태에 따라 달라지는 실행 가능한 행동들을 가지며, 이는 다양한 운영 제약 조건에 의해 암묵적으로 정의됩니다. 이러한 특징들은 표준 심층 강화 학습(DRL) 알고리즘의 사용을 어렵게 만듭니다. 왜냐하면 기존 DRL 알고리즘은 일반적으로 고정된 유한한 행동 목록 또는 단순한 유클리드 공간을 가정하기 때문입니다. 본 논문에서는 최적 행동-값 함수의 테일러 전개를 기반으로, 정책 학습을 유클리드 점수 공간으로 이동시키고, 액션 디코더를 통해 실행 가능성을 강제하는 벨만-테일러 점수 해독 프레임워크를 제안합니다. 이렇게 유도된 잠재 점수 MDP는 디코더를 통과하지 않고 표준 DRL 알고리즘을 사용하여 최적화할 수 있습니다. 본 연구에서는 이 접근 방식의 최적성 간격이 구조적 근사 오차와 알고리즘 학습 오차로 분해된다는 성능 보장을 제공합니다. 마지막으로, 본 프레임워크를 큐잉 네트워크 제어 문제에 적용하여 정책이 상태 의존적인 인덱스 기반 디스패칭 규칙을 학습하도록 합니다. 수치 실험 결과에서 소규모 인스턴스에서는 거의 최적의 성능을 나타내며, 더 큰 시스템에서는 기존 방법보다 상당한 개선을 보였습니다.

Many Markov decision processes (MDPs) in operations research have feasible actions that are state dependent and defined implicitly by various operational constraints. These features make it difficult to use standard deep reinforcement learning (DRL) algorithms, whose action interfaces typically assume either a fixed finite action catalog or a simple Euclidean space. Motivated by a Taylor expansion of the optimal action-value function, we propose Bellman--Taylor score decoding, a framework that moves policy learning to a Euclidean score space while enforcing feasibility through an action decoder. The induced latent-score MDP then can be optimized by standard DRL algorithms without differentiating through the decoder. We provide a performance guarantee showing that the optimality gap of this approach decomposes into a structural approximation error and an algorithmic learning error. Lastly, we apply this framework to a queueing network control problem, where the policy essentially learns a state-dependent index-based dispatching rule. Numerical experiments show near-optimal performance in small instances and considerable improvements over benchmarks in larger systems.