arXiv:2404.06492

Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective

Victor-Alexandru Darvariu, Stephen Hailes, Mirco Musolesi

제출 2024-04-09

원문 초록

Graphs are a natural representation for systems based on relations between connected entities. Combinatorial optimization problems, which arise when considering an objective function related to a process of interest on discrete structures, are often challenging due to the rapid growth of the solution space. The trial-and-error paradigm of Reinforcement Learning has recently emerged as a promising alternative to traditional methods, such as exact algorithms and (meta)heuristics, for discovering better decision-making strategies in a variety of disciplines including chemistry, computer science, and statistics. Despite the fact that they arose in markedly different fields, these techniques share significant commonalities. Therefore, we set out to synthesize this work in a unifying perspective that we term Graph Reinforcement Learning, interpreting it as a constructive decision-making method for graph problems. After covering the relevant technical background, we review works along the dividing line of whether the goal is to optimize graph structure given a process of interest, or to optimize the outcome of the process itself under fixed graph structure. Finally, we discuss the common challenges facing the field and open research questions. In contrast with other surveys, the present work focuses on non-canonical graph problems for which performant algorithms are typically not known and Reinforcement Learning is able to provide efficient and effective solutions.

함께 살펴볼 논문

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

arXiv:2610.11065v1cs.LG공통 태그 Reinforcement Learning, Combinatorial Optimization

CityDeploy-Bench: 다중 송신기 네트워크 배치를 위한 물리 기반 공간 집합 계획 벤치마킹

CityDeploy-Bench: Benchmarking Physics-Grounded Spatial Set Planning for Multi-Transmitter Network Deployment

도시 규모의 무선 배치 자동화는 복잡한 도심 전파 환경과 네트워크 전역의 간섭 속에서 여전히 어려운 과제로 남아 있다. 본 논문에서는 다중 송신기 배치 문제를 통합된 광선 추적(ray-tracing) 검증기 하에서 물리 기반 공간 집합 계획(physics-grounded spatial set planning) 문제로 재구성한 벤치마크인 CityDeploy-Bench를 소개한다. 이 벤치마크는 유틸리티(utility) 표현과 계획 다이내믹스를 분리함으로써, 다양한 플래너(planner)에 대해 직접적인 스칼라 보상, 관계형 모델, 그리고 고차 상호작용 구조 간의 통제된 비교를 가능하게 한다. 실험 결과, 물리적 결합(coupling)이 커질수록 계획 행동에서 명확한 전환이 나타난다. 배치 품질은 학습된 유틸리티가 송신기 간의 집합적 상호작용을 포착하는지에 점점 더 의존하게 되며, 반면 더 강력한 탐색만으로는 누락된 관계형 구조를 보완할 수 없다. 이는 다중 송신기 배치가 독립적인 공간적 의사결정들의 집합이 아니라, 물리적으로 상호작용하는 집합에 대한 조정(coordination) 문제임을 보여준다. 우리는 의사결정 학습(decision learning)과 물리 기반 무선 네트워크 설계를 연결하는 연구를 위한 재현 가능한 테스트베드로서 CityDeploy-Data와 벤치마크 프레임워크를 공개한다.

arXiv:2610.02330v1cs.AI공통 태그 Decision Making, Reinforcement Learning

행동하기 전의 선택: 장기적 도구 사용 에이전트를 위한 비교 가치 추정

Choosing Before Acting: Comparative Value Estimation for Long-Horizon Tool-Use Agents

대규모 언어 모델(LLM)은 복잡한 작업을 수행하기 위해 장기적인(long-horizon) 도구 호출 시퀀스에 의존하며, 여기서 각 호출은 작업 상태를 변경하고 이후 결정의 조건이 됩니다. 장기적 도구 사용에서는 긴 상호작용 궤적 전반에 걸쳐 최종 결과 기반의 보상만으로는 취약한 신용 할당(credit assignment)을 제공할 수밖에 없습니다. 단계별(step-level) 보상은 더 구체적인 피드백을 제공할 수 있으나, 신뢰할 수 있는 단계별 지도(supervision)를 얻으려면 종종 사람이나 LLM의 판단, 또는 중간 결정의 후속 영향을 추정하기 위한 추가적인 롤아웃(rollout)이 필요합니다. 본 논문에서는 효과적인 도구 사용 에이전트(agent)가 가능한 다음 도구 호출을 실행하기 전에 그 장기적 가치를 추정해야 한다고 주장합니다. 이러한 목표를 달성하려면 동일한 문맥에서 대안적인 도구 호출들에 대한 비교 지도(comparative supervision)가 필요하지만, 기록된 궤적(logged trajectory)에는 실제로 수행된 호출만 포함되어 있습니다. 이에 따라 우리는 도구 사용 에이전트를 위한 비교 추론(Comparative Inference for Tool-use Agents, CITA)을 제안합니다. CITA는 관측된 도구 동작, 베이즈 도구 그래프 시뮬레이터로부터 얻은 확장 가능한 지도, 그리고 LLM 기반 비교를 통한 의미적 판단을 결합한 쌍(paired) 신호로부터 비교 추론 모델(Comparative Inference Model, CIM)을 학습합니다. 그 결과 CIM은 현재 문맥에서 가능한 다음 도구 호출이 최종 작업 성공에 기여할 가능성을 추정하도록 학습합니다. 세 가지 도구 사용 벤치마크와 다양한 백본 LLM 전반에서, CITA는 도구 F1 점수와 작업 성공률을 일관되게 향상시킵니다. 추가 분석을 통해 CIM이 비교 도구 선택에 대한 정확한 단계별 가치 추정치를 학습함을 보입니다.

arXiv:2610.02525v1cs.AI공통 태그 Decision Making, Reinforcement Learning

다음에 무엇을 탐구할지 학습하기: 장기 연구 에이전트를 위한 메타 추론

Learning What to Investigate Next: Meta-Reasoning for Long-Horizon Research Agents

장기(long-horizon) 연구 에이전트(agent)는 증거가 축적됨에 따라 어떻게 탐구할지뿐만 아니라 다음에 무엇을 탐구할지도 결정해야 합니다. 이러한 결정은 긴 실행 궤적(execution trace) 내에서 드물게 발생하며, 그 결과가 여러 차례의 탐구 이후에 나타날 수 있기 때문에 학습하기 어렵습니다. 본 논문에서는 연구 자원 배분과 실행을 분리하는 계층적 아키텍처인 반복 연구 에이전트를 위한 메타 추론(Meta-reasoning for Iterative Research Agents, MIRA)을 소개합니다. 외부 루프(outer-loop) 메타 추론기는 영구 연구 기록에서 컨텍스트를 큐레이션한 다음, 다음 탐구를 위한 작업 지시서를 작성하거나 에피소드를 종료합니다. 새로운 내부 루프(inner-loop) 실행기는 각 작업 지시서를 수행하여 실행을 메타 추론 행동 간의 전이 과정 일부로 만듭니다. 정책 학습(policy training) 없이도 MIRA는 장기 추론(inference)을 개선하고 정리 증명 및 개방형 신경망 아키텍처 연구에서 추가 연산량을 더 효과적으로 배분합니다. 또한 MIRA의 결정 경계는 신용 할당(credit assignment)을 위한 자연스러운 단위를 제공합니다. 각 경계에서 부분 상태(partial state)로부터 예상 잔여 보상을 예측하도록 생성형 크리틱(generative critic)을 학습시켜 토큰(token) 수준의 대안들보다 우수한 성능을 보였습니다. 교차 환경 사전학습은 예측과 적응을 개선하여 부분적 진행 상황의 가치를 평가하기 위한 전이 가능한 사전 분포(prior)를 산출합니다. 이 사전 분포를 활용하여 별도의 크리틱 모델 없이 잔여 보상을 예측하고 다음 탐구를 선택하도록 공동 학습되는 생성형 액터-크리틱(actor-critic)인 MIRA-AC를 초기화합니다. MIRA-AC는 정책 최적화를 메타 추론 결정에 집중시켜, 이들이 시작하는 더 긴 실행 궤적을 직접 최적화하지 않고도 효율적인 장기 강화학습(reinforcement learning)을 가능하게 합니다. 모델 자체의 프록시 힐클라이밍(hill-climbing) 신호로 MIRA-AC를 학습시키면 4개의 자동 연구(autoresearch) 환경 전반에서 골드 성능이 향상되며, 액터는 교차 환경 가치 초기화(initialization)를 통해 전이됩니다. 종합적으로, 이러한 결과들은 장기 자율 연구를 지휘하기 위한 명시적 정책으로서 메타 추론을 학습할 수 있음을 보여줍니다.

arXiv:2610.00126v1cs.CR공통 태그 Decision Making, Combinatorial Optimization

검증자가 정답을 유출할 수 있다: 폐루프 에이전트 디버깅에서 최적화에 앞선 진단 가능성

A Verifier Can Leak the Answer: Diagnosability Before Optimization in Closed-Loop Agent Debugging

에이전트(agent) 개발자들은 시뮬레이터 기반 검증자(verifier)를 통해 프롬프트, 도구, 정책 및 진단 알고리즘을 비교하는 방식을 점점 더 많이 활용하고 있습니다. 그러나 검증자는 솔버(solver) 비교를 무의미하게 만들 수도 있습니다. 즉, 검증자의 프로브(probe)나 술어(predicate)가 타깃의 식별 정보를 인코딩하고 있다면, 정확한 옵티마이저(optimizer)는 어떠한 실질적인 모호성도 해결하지 못한 채 효과적인 것처럼 보일 수 있습니다. 본 연구에서는 폐루프(closed-loop) 의사결정 에이전트를 위한 집계 트레이스 디버거에서 발생하는 이러한 실패 사례를 보고합니다. 정확한 최소 적중 집합(Minimum Hitting Set, MHS)과 전파 인식 탐욕 알고리즘(propagation-aware greedy method)은 12개 개발 사례 모두에서 동일한 지지 집합(support)을 반환했으며, 9/12 사례에서 동일한 주입 결함(planted fault) 복구를 달성했습니다. 후속 감사 결과, 정확한 앵커(exact-anchor) 술어가 9/9 사례에서 주입된 쌍을 생성한 것으로 확인되었습니다. 해당 앵커들을 제거한 후 전체 주입 쌍 복구율은 8/9였습니다. 그럼에도 불구하고 하드 프로브 싱글톤(hard-probe singleton) 쌍은 9/9 사례에서 주입된 쌍과 일치했으며, 전파 후 비어 있지 않은 잔여 충돌군(residual conflict family)이 유지된 사례는 전무했습니다(0/9). 옵티마이저는 올바르게 작동했으나, 검증자가 이미 정답을 노출하고 있었던 것입니다. 이에 본 논문에서는 솔버 우선 평가 방식을 지지 집합 기반 게이팅(support-gated) 검증 규약으로 대체합니다. 먼저 클린 참조 맵(clean reference map)을 통해 반복적인 컴포넌트 노출을 입증해야 하며, 그다음 일치된 참조/현재 게이트를 통해 비교 가능한 런타임 증거를 확립해야 하고, 그 이후에만 독립적으로 보정된 신호 규칙이 탐지 결과를 반환할 수 있습니다. 1,440개의 사례와 21,600개의 파티션 행으로 구성된 사전 등록된 홀드아웃(heldout) 평가에서, 55/72 체제-컴포넌트(regime-component) 단위가 참조 게이트를 통과했고, 54/55가 런타임 게이트를 통과했으며, 표현된 컴포넌트의 안정적 위허용(stable false admission)은 단측 정확 95% 상한선 0.1391과 함께 0/20을 기록했습니다. 승인된 단위 내에서는 영향을 받은 정상 트래픽이 공칭 결함 셀 비율(nominal fault-cell fraction)보다 탐지를 더 잘 예측했습니다. 본 연구의 핵심적인 구조적 교훈은 컴포넌트 선택기를 최적화하기 전에 증거의 적격성과 비공개성(non-revelation)을 먼저 검증해야 한다는 점입니다. 그렇지 않으면 더 강력한 솔버가 단지 더 강력한 검증자 아티팩트(artifact)를 인증하는 것에 불과할 수 있습니다.

토론

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