arXiv:2306.07749

Provably Learning Nash Policies in Constrained Markov Potential Games

Pragnya Alatur, Giorgia Ramponi, Niao He, Andreas Krause

제출 2023-06-13

원문 초록

Multi-agent reinforcement learning (MARL) addresses sequential decision-making problems with multiple agents, where each agent optimizes its own objective. In many real-world instances, the agents may not only want to optimize their objectives, but also ensure safe behavior. For example, in traffic routing, each car (agent) aims to reach its destination quickly (objective) while avoiding collisions (safety). Constrained Markov Games (CMGs) are a natural formalism for safe MARL problems, though generally intractable. In this work, we introduce and study Constrained Markov Potential Games (CMPGs), an important class of CMGs. We first show that a Nash policy for CMPGs can be found via constrained optimization. One tempting approach is to solve it by Lagrangian-based primal-dual methods. As we show, in contrast to the single-agent setting, however, CMPGs do not satisfy strong duality, rendering such approaches inapplicable and potentially unsafe. To solve the CMPG problem, we propose our algorithm Coordinate-Ascent for CMPGs (CA-CMPG), which provably converges to a Nash policy in tabular, finite-horizon CMPGs. Furthermore, we provide the first sample complexity bounds for learning Nash policies in unknown CMPGs, and, which under additional assumptions, guarantee safe exploration.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.26783v1math.OC공통 태그 Decision Making, Multi-agent Reinforcement Learning, Sequential Decision Making

지연된 정보 공유를 활용한 탈중앙화 부분 관측 팀 의사결정 방법론

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)를 유도합니다.

arXiv:2609.24025v1cs.AI공통 태그 Decision Making, Multi-agent Reinforcement Learning, Sequential Decision Making

프로그래밍 정책 탐색을 통한 연속 게임용 반응형 캐릭터 행동 합성

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를 위한 실용적인 저작 도구가 될 수 있음을 시사한다. 디자이너가 보상 함수를 지정하면 시스템이 효과적이고 이식 가능하며 종종 놀라운 수준의 편집 가능한 행동을 발견한다.

arXiv:2610.01834v3cs.AI공통 태그 Decision Making, Sequential Decision Making

시뮬레이션은 코드가 담당하고, 평가는 Jev가 담당한다

Code Owns the Simulation, Jev Owns the Evaluation

Jev와 같은 판단 모델(judgment model)은 단 한 번의 호출로 추론 텍스트 없이 설명된 각 선택지에 대한 확률을 반환합니다. 이러한 특징 덕분에 에이전트의 행동 선택 층(layer)으로서 매력적이지만, 어떤 결정을 신뢰할 수 있는지는 명확하지 않습니다. 본 연구에서는 인지 반사 테스트, 일회성 행렬 게임, 텍스트 게임 ALFWorld 및 로봇 제어에서 Jev를 테스트하고 뚜렷한 경계를 발견했습니다. Jev는 입력에 설명된 내용으로부터 올바른 선택지를 판단할 수 있을 때 성공하며, 이를 본 연구에서는 평가(evaluation)라고 부릅니다. 구체적으로, Jev는 직관에 반하는 인지 반사 테스트(Cognitive Reflection Test) 문제의 99%를 해결합니다. 그러나 올바른 선택지가 상대방의 행동이나 먼저 달성해야 하는 하위 목표와 같이 시뮬레이션(simulation, 즉 입력에 없는 내용을 예측하는 것)에 의존할 때는 실패합니다. 게임에서 Jev는 상대방의 행동이 주어지지 않기 때문에 합리적인 상대가 무작위로 행동하는 것처럼 차선으로 플레이합니다. ALFWorld에서 Jev는 작업 설명에 언급된 사물이나 장소를 지칭하는 명령을 선호합니다. 예를 들어, "서랍에 깨끗한 칼을 넣어라"라는 작업이 주어지면, Jev는 싱크대에서 칼을 먼저 씻는 대신 씻지 않은 칼을 서랍으로 곧장 가져갑니다. 놀랍게도 이러한 실패 중 다수는 지식의 부족 때문이 아닙니다. 상대가 무엇을 할지 별도로 질문을 받으면 Jev는 대개 정확하게 답하며, 상대의 행동이 주어지면 적절하게 대응합니다. Jev가 실패하는 것은 단 한 번의 호출로 시뮬레이션을 수행하고 이에 기반한 평가까지 동시에 처리해야 할 때입니다. 이는 예측이나 시뮬레이션을 코드가 수행하도록 할 것을 시사합니다. ALFWorld의 미리보기(lookahead)나 로봇 제어의 물리 시뮬레이션과 같이 코드가 이를 제공하면, Jev는 일반적인 평가 능력을 통해 전문가 수준의 제어기가 됩니다.

arXiv:2610.02036v3cs.AI공통 태그 Decision Making, Multi-agent Reinforcement Learning

전역 일관성: 모든 에이전트가 옳아도 팀 전체는 틀릴 때 - 멀티 에이전트 협업을 위한 국소-전역 의미론적 기반

Global Coherence: When Every Agent Is Right and the Team Is Still Wrong - A Local-to-Global Semantic Foundation for Multi-Agent Collaboration

AI 에이전트는 코드, 문서, 도구, 분석을 공유한다. 어떤 참여자도 전체 상태를 보지 못하므로, 모든 단계가 옳아 보이는데도 결합된 결과는 틀릴 수 있다. 우리는 이를 전역 일관성 문제라고 부른다. 이는 지능만의 문제가 아니라 상태의 문제이다. 더 강한 모델은 국소적으로 더 잘 결정하지만, 자신의 맥락에서 무엇이 빠져 있는지는 볼 수 없다. 관측 에일리어싱 불가능성 정리는 정확한 조건을 제시한다. 에이전트는 자신의 맥락과 일치하는 모든 세계가 공통의 행동을 허용할 때, 그리고 그때에만 항상 유효하게 행동할 수 있다. 서로 닮은 세계들이 서로 다른 행동을 요구할 때에는, 어떤 추론, 역할, 메시지, 표본도 올바른 행동을 보장할 수 없다. 유효한 행동이 서로소인 이러한 세계가 $k$개 있으면, 최선의 무작위 정책이 성공할 확률은 1/k이다. 충분한 최소 맥락을 찾는 것은 NP-난해이지만, 정제(refinement)가 하나를 찾아내고 규칙이 바뀔 때 이를 최신 상태로 유지한다. 두 번째 실패는 완전한 정보 하에서도 남는다. 유효한 조각들이 하나의 세계로 맞춰지지 않을 수 있다. 동일한 정리가 일관성의 조건을 규정하며, 층(sheaf)과 군다발(groupoid)은 이를 충족하는 한 가지 방법이다. 모델이 제안하고, 하네스가 무엇이 유효한지 결정한다. 열 가지 연구로 이를 검증한다. TeamBench에서 팀은 5/5회 실행에서 공유 예산을 초과 지출하며, 실시간 집계를 보여 주어도 4/5가 남고, 예산을 소유하는 하네스에서는 0/5가 남는다. 어떤 쌍별 검사로도 볼 수 없는 신원 충돌이 공개 정렬 네트워크 45개 중 23개에서 나타나며, 분할 시야 에이전트는 40회 병합 중 9회에서 이를 만들어 내고, 네트워크 검사는 아홉 건을 모두 제거한다. 최첨단 LLM은 결정적 사건을 볼 때 40/40개의 수정 과제를 해결하지만, 그 사건을 숨기면 더 오래 추론하거나, 투표하거나, 역할로 나누는 어떤 방식도 우연 수준을 유의하게 넘지 못하며, 동반 연구는 두 번째 제공자의 모델에서 이를 재현한다. tau2-bench Telecom에서 무음 되돌림 이후 하네스는 1.00점을 기록하는 반면 호출 시점 정책 검사는 0.07점이다. 정제는 모든 필드를 공유하는 비용의 28%로 충분한 맥락을 유지한다.

arXiv:2610.10942v2cs.AI공통 태그 Decision Making, Sequential Decision Making

StoreBench: 자율 운영자 에이전트의 평가 및 학습을 위한 라이브 커머스 환경

StoreBench: A Live-Commerce Environment for Evaluating and Training Autonomous Operator Agents

강화학습(RL) 환경은 이제 사후 학습(post-training)에서 대규모 언어 모델(LLM)의 역량을 향상시키는 주요 수단이 되었으나, 대부분의 에이전트 벤치마크는 여전히 정적입니다. 즉, 에이전트가 행동할 때만 환경이 변화하고, 보상은 최종적인 판정으로 주어지며, 통과 기준은 자의적으로 설정됩니다. 본 논문에서는 에이전트가 프로덕션 수준의 상거래 백엔드에서 중간 규모의 온라인 의류 매장을 운영하며 불확실성 속에서 장기 계획 수립 및 경제적 판단력을 시험받는 라이브 커머스 환경인 StoreBench를 소개합니다. 고객은 24시간 내내 주문하고, 공급업체는 가격을 재책정하거나 공급에 실패하며, 시장 충격은 부분적인 예고만 있거나 예고 없이 발생합니다. 에이전트는 실제 인간 운영자가 사용하는 것과 동일한 29개의 판매자 도구를 통해 행동하며, 취해진 행동의 함수로 시뮬레이션 시간을 계산하는 윈도우 기반 운영 예산 하에서 작동하므로 모델 지연 시간이 시뮬레이션 시간에 영향을 미칠 수 없습니다. 통과 임계값은 스크립트 기반 앵커 정책을 기준으로 보정되었고, 보상은 다양한 보상 해킹 목록에 대비해 강화되었으며, 일련의 행동이 주어지면 모든 에피소드가 동일하게 재현됩니다. 본 연구에서는 추론 노력을 일치시킨 상태에서 세 가지 월드 시드에 걸쳐 30~45일 및 시뮬레이션된 1년 전체에 해당하는 11개 시나리오를 바탕으로 7개의 프론티어 LLM을 평가합니다. 평균적으로 스크립트 기반 스마트 트리아지(smart-triage) 정책에 필적하는 모델은 없었습니다. 최고 성능을 보인 DeepSeek-V4-Pro는 휴리스틱의 97% 대비 49%의 태스크-시드 셀을 통과했습니다. 동일한 도구와 예산을 사용하여 작업한 인간 전문가는 모든 모델보다 높은 점수를 기록했습니다(평균 종합 점수 0.708 대 0.700). Claude Code 하네스 기반의 시뮬레이션된 1년 전체에 걸쳐 대다수 모델은 극적인 성능 향상을 보입니다. GRPO 사후 학습 실행에서 서로 다른 5개의 태스크로만 학습된 Qwen3.5-27B는 홀드아웃(held-out) 평가 태스크에서의 평균 종합 점수를 0.136에서 0.373으로 향상시켰습니다. 본 연구에서는 학습 분할용 예시 태스크 5개, 샘플 궤적 10개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.

arXiv:2610.15993v1cs.AI공통 태그 Decision Making, Sequential Decision Making

핸드오프 곡선: 멀티턴 LLM 라우팅에서의 초기 선택, 사후 핸드오프 및 지도 타깃

Handoff Curves: Initial Selection, Later Handoff, and Supervision Targets in Multi-turn LLM Routing

본 연구에서는 여러 턴(turn)에 걸친 대규모 언어 모델(LLM) 태스크에서 초기 모델(model) 선택, 사후 핸드오프(handoff), 그리고 학습(training) 타깃이 성공률과 비용에 미치는 영향을 연구합니다. 핸드오프 단계 변화에 따른 태스크 성공률과 비용을 기록하는 핸드오프 곡선을 활용하여 여러 라우터 아키텍처를 비교합니다. 연구진이 구축한 데이터셋(dataset)은 BFCL, MultiWOZ, $τ$-retail 전반에 걸친 3개 Qwen 모델의 34,204건의 완전한 실행 기록을 포함하며, 라우팅 결정을 위한 오프라인 지도 정보를 제공합니다. 주요 비교 분석에서 Qwen3.5 35B-A3B를 시작 모델로 사용했을 때, 사후 핸드오프를 허용하는 것은 BFCL 또는 MultiWOZ에서 초기 선택 대비 효용 개선을 보이지 못했으며 다양한 비용 가중치 범위에 걸쳐 BFCL에서 비용을 증가시켰습니다. 지도 타깃을 변경하면 자체 데이터셋과 TwinRouterBench 모두에서 라우터 성능이 향상됩니다. 자체 데이터셋의 경우 노이즈가 있는 학습 성공 곡선을 단조 적합(monotone fit)으로 대체함으로써 보고된 작동 지점 전반에 걸쳐 동일한 비용에서 성공률이 0.2~4.1%포인트 향상되었습니다. TwinRouterBench에서는 남은 작업 및 앞으로 닥칠 어려운 단계에 필요한 모델 성능을 기술하는 타깃을 구성했습니다. 벤치마크의 단계별 라벨로 학습하는 것과 비교하여, 이러한 타깃은 전체 정적 뱅크에서 궤적 통과 점수를 7.8%포인트, 비용 절감 효과를 6.3%포인트 높였습니다. 이 타깃으로 학습된 라우터의 실제 배포에서는 인스턴스당 0.59달러의 라우터 비용으로 100개 인스턴스 중 79개를 해결했습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.