arXiv:1810.03063

Solving Large Sequential Games with the Excessive Gap Technique

Christian Kroer, Gabriele Farina, Tuomas Sandholm

제출 2018-10-07

원문 초록

There has been tremendous recent progress on equilibrium-finding algorithms for zero-sum imperfect-information extensive-form games, but there has been a puzzling gap between theory and practice. First-order methods have significantly better theoretical convergence rates than any counterfactual-regret minimization (CFR) variant. Despite this, CFR variants have been favored in practice. Experiments with first-order methods have only been conducted on small- and medium-sized games because those methods are complicated to implement in this setting, and because CFR variants have been enhanced extensively for over a decade they perform well in practice. In this paper we show that a particular first-order method, a state-of-the-art variant of the excessive gap technique---instantiated with the dilated entropy distance function---can efficiently solve large real-world problems competitively with CFR and its variants. We show this on large endgames encountered by the Libratus poker AI, which recently beat top human poker specialist professionals at no-limit Texas hold'em. We show experimental results on our variant of the excessive gap technique as well as a prior version. We introduce a numerically friendly implementation of the smoothed best response computation associated with first-order methods for extensive-form game solving. We present, to our knowledge, the first GPU implementation of a first-order method for extensive-form games. We present comparisons of several excessive gap technique and CFR variants.

함께 살펴볼 논문

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

arXiv:2607.12909v2q-bio.NC공통 태그 counterfactual

저전력 에지 플랫폼을 위한 비전 기반 실시간 낙상 감지

Real-time fall detection based on vision for low-power edge platforms

낙상 감지는 노인 돌봄과 지능형 감시에 필수적이지만, 기존 비전 기반 접근법은 대부분 이를 정적 자세 분류 또는 이산적 시간적 패턴 매칭으로 다루어, 인간 지지 체계의 불안정 역학을 근본적으로 간과한다. 본 논문은 낙상을 결합 동역학 시스템에서의 안정성 상실 사건으로 재정식화하는 물리 정보 기반 낙상 감지 프레임워크를 제안한다. 우리는 질량 중심(CoM) 하위 시스템과 지지 기반(BoS) 하위 시스템으로 구성된 새로운 이중 LTC 아키텍처를 도입하며, 두 하위 시스템 모두 Liquid Time-Constant(LTC) 신경망으로 구현되어 적응적 시간 상수를 통해 관성 궤적 진화와 지면 접촉 조정을 연속적으로 모델링하고 낙상 운동의 물리적 해석 가능성을 제공한다. 학습 가능한 결합 모듈은 두 하위 시스템 간의 물리적 상호작용을 모사하고, Stability Manifold 분류기는 결합 잠재 공간에서 Lyapunov 영감 안정성 지표를 통해 경계 교차를 감지한다. 보완적으로 반사실적 궤적 투영과 충돌까지의 시간(TTC) 추정은 비가역성 평가와 조기 경보를 추가로 가능하게 한다. 이 아키텍처는 3상태 예측 패러다임(정상, 낙상 중, 낙상 완료)을 지원하도록 설계되었으며, 본 예비 연구에서는 2클래스 데이터셋(정상 대 낙상)에서 핵심 안정성 판별 능력을 검증하고, 전체 3상태 시간적 전이는 향후 연구로 남긴다. 기존 CNN-RNN 파이프라인과 달리, 제안된 공식화는 연속 시간 기계적 관성을 인코딩하여 5만 미만 매개변수의 네트워크로 자원 제약 에지 장치에서 실시간 추론이 가능하다. 광범위한 실험은 우수한 물리적 해석 가능성과 함께 경쟁력 있는 정확도를 보여 주며, 저연산 시각적 낙상 감지에 대한 효과를 입증한다.

arXiv:2609.28870v3cs.DC공통 태그 GPU

정교한 축출 정책이 실패할 때: LLM 접두 문맥 재사용을 위한 캐시 교체 정책의 재고

When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse

장시간 실행되는 LLM 애플리케이션과 자율 에이전트는 점점 늘어나는 컨텍스트를 반복적으로 전송하므로, 프리픽스 캐싱은 프리필 비용을 줄이는 데 매우 중요하다. 이는 수십 년간의 전통적인 캐시 관리 기법이 에이전트형 및 대화형 LLM 서빙에 그대로 적용되는가라는 근본적인 질문을 제기한다. 우리는 200억 개가 넘는 처리 토큰으로 구성된 실제 서비스 트레이스를 분석하고, 용량이 제한된 HBM 환경과 대규모 메모리 풀 환경에서 14가지 축출 알고리즘을 평가한다. 그 결과, 단순한 LRU(Least Recently Used)가 놀라울 정도로 견고하여 정교한 전통적 정책과 대등한 성능을 보이지만, 벨라디(Belady)의 최적 해와는 여전히 상당한 격차가 남아 있음을 확인한다. 그 이유는 구조적이다. 프리픽스 재사용은 활성 세션의 꾸준한 진행 속도에 의해 좌우되므로, 최근 사용 여부가 축출에 대해 이례적으로 강한 예측 변수가 된다. 그럼에도 프리픽스 캐싱은 최근성이 무시하는 측면에서 전통적 워크로드와 다르며, 특히 단일 턴 요청의 만연, 극단적인 세션 크기 편중, 어텐션 연산이 토큰 깊이에 따라 증가하기 때문에 발생하는 매우 불균일한 미스 비용이 그러하다. 최적과의 격차를 줄이기 위해, 우리는 프리픽스 캐시 관리를 위한 몇 가지 설계 원칙을 제시한다. 즉, 최근성을 기준선으로 유지하면서 일회성 프롬프트를 걸러내기 위한 신속한 강등, 비용이 큰 미스를 우선시하는 연산 인지형 축출, 용량 적응형 축출 단위를 함께 도입하는 것이다. 우리의 트레이스와 시뮬레이터는 공개되어 있다.

arXiv:2607.03012v2cs.CV공통 태그 GPU

HyperVAttention: 비디오 디퓨전을 위한 시공간 클러스터링 기반 효율적인 희소 어텐션

HyperVAttention: Efficient Sparse Attention with Spatio-Temporal Clustering for Video Diffusion

비디오 확산 트랜스포머(VDiT)는 고충실도 비디오 생성에서 상당한 능력을 보여 왔다. 그러나 장시간 비디오를 생성하는 능력은 셀프 어텐션 메커니즘의 이차 복잡도에 의해 근본적으로 제약된다. 최근의 클러스터링 기반 희소 어텐션 방법은 의미적으로 유사한 토큰을 묶어 품질과 속도 간 절충을 개선하지만, 실제 효율은 상당한 클러스터링 오버헤드와 불규칙한 클러스터 유도 블록으로 인한 낮은 CTA 활용률이라는 두 가지 병목으로 인해 제한된다. 우리는 이 두 병목을 함께 해결하는 학습 불필요 희소 어텐션 프레임워크인 HyperVAttention(HVA)을 제안한다. 클러스터링 오버헤드를 줄이기 위해, 비디오 토큰의 시공간 지역성을 활용하여 중심점 탐색을 고정된 국소 이웃으로 제한하는 3D 국소 윈도우 클러스터링을 도입하고, 효율적인 실행을 위해 맞춤형 Triton 커널로 구현한다. 또한 노이즈 제거 단계 전반에서 클러스터 할당의 시간적 안정성을 활용하여 앵커 단계에서만 전체 클러스터링을 수행하고 중간 단계에서는 일부 토큰만 갱신하는 하이브리드 클러스터링 전략을 제안한다. CTA 활용률을 높이기 위해, 병렬 병합형 군집화를 통해 CTA 정렬 실행 비용을 최소화하는 하드웨어 인식 클러스터 병합을 제시하며, 유휴 타일 용량을 활용하여 블록 밀도와 근사 충실도를 개선한다. 이러한 구성 요소는 함께 클러스터링 오버헤드를 줄이고 중복 갱신을 피하며 희소 어텐션을 최신 GPU 커널의 고정 타일 구조에 더 잘 맞춘다. 비디오 생성 실험에서 HVA는 학습 불필요 희소 어텐션의 파레토 프런티어를 개선하여, 비슷한 지연 시간에서 SVG2보다 높은 충실도를 달성하고 HunyuanVideo에서 전체 어텐션 대비 $2.13\times$ 속도 향상을, 더 빠른 변형인 HVA-Flash로는 $2.23\times$ 속도 향상을 달성한다.

arXiv:2610.02480v2cs.AI공통 태그 counterfactual

MEA: 충실한 모델 설명을 위한 보상 기반 다중 에이전트 시스템

MEA: A Reward-Driven Multi-Agent System for Faithful Model Explanations

최근 중요도가 높은 고위험 영역에서 수많은 머신러닝(ML) 모델이 도입되고 있지만, 그 예측을 바탕으로 행동해야 하는 실무자들에게 이러한 모델은 여전히 대부분 불투명한 상태로 남아 있습니다. 사후(post-hoc) 설명 방법들이 모델의 동작을 들여다볼 수 있는 시각을 제공하긴 하지만, 이를 효과적으로 다루기 위해서는 대부분의 도메인 전문가들이 갖추지 못한 전문 지식이 필요합니다. 즉, 고차원 출력을 탐색하고, 최적의 설명을 선택하며, 이질적인 도구들 전반에 걸친 증거를 종합해야 합니다. 이를 위해 본 연구에서는 설명에 필요한 전문 지식의 장벽을 완전히 제거하는 다중 에이전트 프레임워크인 MEA를 제시합니다. 제안자(Proposer) 에이전트는 질문과 양식(modality)에 따라 설명 도구를 선택하고 구성하며, 실행자(Actor) 에이전트는 충실도(faithfulness)를 기준으로 엔드투엔드 최적화되어 테이블, 텍스트, 비전 양식 전반에 걸쳐 모델 동작에 기반(grounding)한 자연어 설명으로 출력을 변환합니다. 나아가, 특징 기여도(feature attribution), 반사실적 추론(counterfactual reasoning), 거짓 특징(spurious feature) 탐지를 아우르는 다양한 질문 유형을 도입하고, 각각을 섭동 기반 충실도 지표와 짝지었습니다. 연구 결과, 프론티어 대규모 언어 모델(LLM)들은 체계적으로 충실하지 못한 설명을 생성하는 것으로 나타났습니다. 양식 적응형 페널티로 강화된 충실도 보상에 대해 최적화함으로써, MEA는 6개 데이터셋 전반에서 기존 사후 설명 기법, 에이전트 기반 베이스라인, 상용 폐쇄형 베이스라인을 일관되게 능가했으며, 보상 기반 최적화를 통해 학습되지 않은 백본 대비 충실도가 테이블에서 +28%, 텍스트에서 +21%, 비전에서 +34% 향상되었습니다. 더 넓게는, 본 연구 결과는 AI 에이전트 자체가 머신러닝 설명가능성(explainability)을 위한 확장 가능하고 적응력 있는 인터페이스 역할을 할 수 있음을 시사하며, 오랫동안 이 분야를 규정해 온 고정된 단일 목적 도구를 넘어 일반화되는 자연어 설명가능성으로 향하는 길을 열어줍니다.

arXiv:2609.26142v2stat.ME공통 태그 counterfactual

하나의 해답을 향한 세 가지 경로: 응용 연구자를 위한 AIPW, TMLE 및 이중 머신러닝의 일치화

Three Routes to One Answer: Reconciling AIPW, TMLE, and Double Machine Learning for Applied Researchers

증강 역확률 가중(AIPW), 표적 최대우도 추정(TMLE), 이중/편향 제거 기계학습(DML)은 평균 처치 효과에 대한 동일한 효율적 영향 함수에 이르는 점근적으로 동등한 세 가지 경로이다. 우리는 실제 데이터에서 공유된 교란 모수를 이용한 실제 사례 조정을 제시한다. 즉, 이 경로들과 해당 소프트웨어가 일치하려면 실무자가 무엇을 고정해야 하는지, 그리고 언제 일치하지 않는지를 다룬다. 금연과 체중 변화에 대한 공개 데이터(n = 1566), 하나의 Super Learner 라이브러리, 방식 내에서 일치시킨 폴드를 사용하여, 전체 표본, 교차 적합, 이중 교차 적합 변형으로 세 가지를 모두 직접 구현한다. 고정된 설계에서 표본 평균 효과가 알려진 준합성 벤치마크로 구간 포함률을 평가한다. 여섯 개의 이중 강건 추정치는 반복 분할에 걸쳐 3.32--3.39 kg의 범위를 보인다. 우리 코드와 tmle, AIPW, DoubleML, tmle3 패키지의 단일 실행 결과는 3.32--3.49 kg의 범위를 보이며, 이는 적합 방식의 차이와 단일 분할 잡음과 부합한다. 20개의 시드에 걸쳐, 우리 라이브러리를 공유하는 세 가지 구현은 그중 하나가 TMLE임에도 중앙값 기준 0.01 kg 이내에서 일치한다. 일치는 실패할 수 있다. 이진 사망 결과에 대해 표본 내 교란 모수 적합을 사용하는 경우와, 직업 훈련 사례에서 겹침이 부족한 경우가 그러하다. 우리는 추정량을 선택하기 전에 겹침을 진단할 것을 권장하며, 보고 체크리스트와 소프트웨어 코드를 제공한다.

토론

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