Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
원문 초록
We study the policy evaluation problem in multi-agent reinforcement learning where a group of agents, with jointly observed states and private local actions and rewards, collaborate to learn the value function of a given policy via local computation and communication over a connected undirected network. This problem arises in various large-scale multi-agent systems, including power grids, intelligent transportation systems, wireless sensor networks, and multi-agent robotics. When the dimension of state-action space is large, the temporal-difference learning with linear function approximation is widely used. In this paper, we develop a new distributed temporal-difference learning algorithm and quantify its finite-time performance. Our algorithm combines a distributed stochastic primal-dual method with a homotopy-based approach to adaptively adjust the learning rate in order to minimize the mean-square projected Bellman error by taking fresh online samples from a causal on-policy trajectory. We explicitly take into account the Markovian nature of sampling and improve the best-known finite-time error bound from $O(1/\sqrt{T})$ to~$O(1/T)$, where $T$ is the total number of iterations.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
분산 감소 정책 그래디언트는 거의 미니맥스-최적이다
Variance-Reduced Policy Gradient is Nearly Minimax-Optimal
표준 정책 그래디언트(Policy Gradient, PG) 알고리즘은 몬테카를로 업데이트에 의존하기 때문에 추정 분산이 높다는 문제를 가진다. 오프-정책 분산 감소(off-policy variance reduction)가 이 문제를 완화하지만, 현재로서는 최적의 샘플 복잡도(sample complexity)를 확립하려면 균일하게 유계인(uniformly bounded) 중요도 가중치(importance weights)와 같은 제한적인 가정이나 비현실적인 2차(second-order) 연산이 필요하다. 본 연구에서는 Loopless Variance-Reduced PG(LVR-PG)를 소개한다. 이는 재귀적 업데이트(recursive update)와 방어적 중요도 샘플링(defensive importance sampling)을 결합한 1차(first-order) 추정량들의 한 클래스를 추상화하는 통합 이론적 프레임워크로, PAGE-PG와 STORM-PG와 같은 기존 추정량들을 포함한다. 우리는 일반적인 파라메트릭 정책(parametric policy)에 대해 약한 그래디언트 지배(weak gradient domination) 조건 하에서 이 알고리즘 클래스가 $\tilde{\mathcal{O}}(ε^{-2})$의 라스트 이터레이트(last-iterate) 전역 수렴(global convergence)을 달성함을 증명한다. 우리는 순수하게 1차 업데이트만을 사용하여, 최소한의 가정 하에 그래디언트 전처리기(gradient preconditioner) 없이 이 보장을 확립한다. 최신 하한(lower bound)을 연속적인 파라메트릭 정책(continuous parametric policy)으로 확장함으로써, 우리는 $Ω(ε^{-2})$의 샘플 복잡도 한계를 확립하며, 이는 로그 인자(logarithmic factor)와 호라이즌(horizon) 항을 제외하면 우리의 프레임워크가 미니맥스 최적(minimax-optimal)임을 확인해 준다.
영차 잔차 추적을 통한 부분 정보 확률적 최적화
Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking
많은 최적화(optimization) 문제에서는 그래디언트(gradient)의 일부에만 직접 접근할 수 있으며, 나머지 성분은 함수 평가를 통해 추론해야 합니다. 이러한 구조는 수행적 예측(performative prediction), 수행적 강화학습(performative reinforcement learning), 그리고 블랙박스 하위 레벨을 갖는 이단계 최적화(bilevel optimization)에서 발생합니다. 본 논문에서는 사용 가능한 그래디언트 성분과 잔차의 이동 추정치를 결합하는 부분 정보 확률적 최적화(Partially Informed Stochastic Optimization, PISO)를 제안합니다. PISO는 각 영차(zeroth-order) 관측을 이 추정치 중심으로 정렬함으로써, 무작위 탐침으로 인한 분산이 잔차의 크기가 아닌 추적 오차에 의존하도록 만듭니다. 이를 통해 명시적인 수축 메커니즘과 모멘텀(momentum)에 대한 원리적 해석을 갖춘 무작위 스케치 반복(iteration)을 도출합니다. 매끄러운 비볼록 목적 함수에 대해, 접근 불가능한 그래디언트 성분에 대한 균일한 경계를 요구하지 않으면서 잔차의 변동과 초기 크기에 의존하는 수렴(convergence) 보장을 확립합니다. 독립적으로 샘플링된 함수 평가와 가우시안 또는 구면 탐침을 사용할 때, PISO는 립시츠 그래디언트 조건에서 \(O(d^{2}\varepsilon^{-6})\), 추가적인 립시츠 헤시안(Hessian) 가정 하에서는 \(O(d^{2}\varepsilon^{-5})\)의 우수한 함수 평가 복잡도를 달성합니다. 이러한 수렴 속도는 업데이트당 단 하나의 탐침 방향, 두 개의 함수 샘플, 그리고 하나의 기지 성분 샘플만을 필요로 합니다. 또한 본 분석은 배치 처리를 통해 배포 횟수를 줄이는 대신 관측치를 교환하는 방식을 정량화합니다. 다섯 가지 설정 전반에서, PISO 변형들은 세 가지 설정에서 유사한 오라클 접근을 갖는 테스트된 베이스라인 대비 성능을 향상시키고, 이단계 라우팅에서는 유사한 해에 더 빠르게 도달하며, 수행적 강화학습에서는 반응 모델(response-model)의 도함수가 없는 방법 중 가장 뛰어난 성능을 보입니다.
판매 학습: 다중 제품 시장에서 전략적 대규모 언어 모델 에이전트를 위한 강화학습
Learning to Sell: Reinforcement Learning for Strategic Large Language Model Agents in Multi-Product Markets
다중 제품 시장에서 작동하는 자율 대규모 언어 모델(LLM) 에이전트는 정보 비대칭과 자원 제약 조건 하에서 순차적 의사결정을 내려야 합니다. 본 연구에서는 판매자가 독립적인 구매자 풀을 대상으로 대체 가능한 자산 카탈로그를 동시에 협상하는 다중 품목 협상 환경에서 에이전트가 판매자로서 효과적으로 활동하도록 학습시키는 머신러닝 접근 방식을 개발합니다. 구매자들은 제품 전반에 걸쳐 비공개적이고 이질적인 가치 평가를 지니며, 각 구매자는 최대 하나의 품목만 구매할 수 있습니다. 판매자는 전체 통신 턴 수의 제한에 직면하여 구매자의 비공개 가치 평가를 고려해 가장 수익성이 높은 제품과 동적으로 매칭하는 동시에, 더 큰 잠재 가치를 지닌 조합을 향해 제한된 상호작용 예산을 전략적으로 할당해야 합니다. 본 논문에서는 자연어를 파싱 가능하고 규제된 의사결정 공간으로 매핑하는 정형화된 4단계 메시지 프로토콜을 사용하여 이 문제를 부분 관측 마르코프 결정 과정(POMDP)으로 정형화합니다. 이러한 정형화를 바탕으로 검증 가능한 보상 기반 강화학습(RLVR)을 사용하는 사후 학습(post-training) 방법을 설계합니다. 이 프레임워크를 평가하기 위해 제약 준수, 판매자 잉여 추출, 할당 품질을 정량화하는 다차원 메트릭 스위트를 구축합니다. 학습된 판매자 에이전트는 제한된 재고를 구매자에게 더 효과적으로 매칭하는 법을 학습하며, 판매자 잉여 추출 및 구매자-제품 할당 품질 모두에서 조 단위 매개변수를 지닌 프론티어 모델과 대등하거나 이를 능가하는 성능을 보입니다. 마지막으로, 이렇게 학습된 전략은 학습 중 접하지 않은 새로운 시장 구조, 상관관계가 있는 가치 평가 분포, 가격 범위로도 견고하게 일반화됩니다.
안전성을 경쟁력으로 전환하기: 안전 필터링 강화학습을 통한 최소 착취성 로봇 정책
Turning Safety into Competence: Minimally Exploitable Robot Policies via Safety-Filtered Reinforcement Learning
경쟁적인 작업에 배치된 로봇은 안전성(safety)을 저해하지 않으면서 상대를 제압할 수 있어야 합니다. 안전 강화학습(safe RL)을 포함한 기존 접근 방식들은 작업 성공을 달성함과 동시에 실패를 피하도록 단일 정책을 학습(training)합니다. 이러한 결합은 학습을 복잡하게 만들고, 의도적인 공격에 의해 학습된 정책이 악용(exploitable)될 수 있는 여지를 남깁니다. 본 논문에서는 안전성 통합과 경쟁 작업 학습을 분리하는 2단계 강화학습 프레임워크인 Safety to Competence(S2C)를 제안합니다. 경쟁적인 상호작용을 안전 필수 마르코프 게임(safety-critical Markov games)으로 정형화하고, 모든 플레이어가 안전한 기동을 준수할 때 완벽한 필터링이 정책의 비착취성(non-exploitability)을 보존함을 증명합니다. S2C는 적대적 강화학습을 통해 강건한 안전 필터를 학습하고, 작업 정책 학습 중 이를 환경(environment)에 포함시키며, 실제 배치 시에도 동일한 필터를 유지합니다. 시뮬레이션된 터치다운 게임에서 S2C는 8가지 안전 강화학습 베이스라인을 능가하여 가장 높은 승률과 Elo 레이팅, 그리고 가장 낮은 착취성을 달성했습니다. 인간 상대를 대상으로 한 하드웨어 스트레스 테스트에서도 S2C의 뛰어난 역량이 입증되었습니다.
지연된 정보 공유를 활용한 탈중앙화 부분 관측 팀 의사결정 방법론
A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing
본 논문에서는 저순위 잠재 동역학(low-rank latent dynamics)과 미지의 시스템 모델을 갖는 탈중앙화 부분 관측 팀 의사결정 문제를 연구합니다. 제안된 프레임워크는 전이 모델(transition model)에 대한 사전 지식 없이도 부분 관측 마르코프 결정 과정(POMDP)에서의 협력적 의사결정을 다루기 위해 팀 이론적 동치성(team-theoretic equivalence)과 저순위 모델 표현을 결합합니다. 각 팀 구성원은 로컬의 개별 정보와 팀 전체에 공유되는 지연된 공통 정보를 기반으로 의사결정을 내립니다. 사용 가능한 정보만을 활용하여, 각 구성원은 근사 저순위 마르코프 결정 과정을 학습하고 최소제곱 가치 반복(least-squares value iteration)을 적용하여 정책을 계산합니다. 이를 통해 중앙 조정자나 중앙 집중식 학습이 모두 필요하지 않은 완전 탈중앙화 학습 및 계획 알고리즘을 도출합니다. 우리는 결과로 도출된 구성원 측 해가 중앙 집중식 팀 해를 근사함을 보입니다. 즉, 부분 관측 가능성, 미지의 동역학, 지연된 공통 정보에도 불구하고 각 구성원은 근사 팀 최적 정책의 해당 구성 요소를 복원합니다. 나아가 제안된 알고리즘에 대한 유한 표본 성능 보장(finite-sample performance guarantees)을 확립하고 이에 대응하는 표본 복잡도 한계(sample-complexity bound)를 유도합니다.
프로그래밍 정책 탐색을 통한 연속 게임용 반응형 캐릭터 행동 합성
Synthesizing Reactive Character Behaviors for Continuous Games via Programmatic Policy Search
본 논문은 연속 게임에서 반응형 캐릭터 행동을 간결하고 사람이 읽을 수 있는 프로그램 형태로 합성하는 방법을 제시한다. 게임 AI 실무는 여전히 수작업으로 작성한 행동 트리, 상태 기계, 스크립트에 크게 의존하는 반면, 학계의 강화학습은 학습 비용이 크고 수정하기 어려운 불투명한 신경망 제어기를 주로 만든다. 우리 접근은 연속 공간 게임 정책을 위한 도메인 특화 언어 위에서 직접 탐색함으로써 이 간극을 메운다. 이 언어는 반응형 기하학적 의사결정을 중심으로 설계되었으며 방향 최대화(direction maximization)와 같은 고차(higher-order) 구성을 포함한다. 이러한 구성은 연속 행동 공간을 열거 가능한 프로그램 구조로 이산화하는 데 도움이 된다. 프로그램 탐색을 실용적으로 만들기 위해, 행동적 커버리지는 유지하면서 중복 프로그램 형태를 제거하는 대규모 합성 안티패턴(synthesis antipatterns) 집합을 도입한다. 또한 하향식(bottom-up) 기호 열거와 코딩 에이전트의 하향식(top-down) 안내를 결합한다. 그 결과 방법인 agentic sketching은 에이전트가 고수준 정책 구조를 제안하고 열거기를 호출해 지역 프로그램 슬롯을 채우도록 한다. 14개의 연속 게임으로 구성된 벤치마크에서 방법을 평가했으며, 고전 제어 과제부터 다중 에이전트 축구까지 범위에 걸친다. 순수 열거만 사용하는 것이 코딩 에이전트 단독 사용보다 종종 더 효율적이며, 결합 방법은 둘 모두를 크게 능가한다. 결과는 프로그래밍 정책 탐색이 게임 AI를 위한 실용적인 저작 도구가 될 수 있음을 시사한다. 디자이너가 보상 함수를 지정하면 시스템이 효과적이고 이식 가능하며 종종 놀라운 수준의 편집 가능한 행동을 발견한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.