Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions
원문 초록
We study the performance of optimistic regret-minimization algorithms for both minimizing regret in, and computing Nash equilibria of, zero-sum extensive-form games. In order to apply these algorithms to extensive-form games, a distance-generating function is needed. We study the use of the dilated entropy and dilated Euclidean distance functions. For the dilated Euclidean distance function we prove the first explicit bounds on the strong-convexity parameter for general treeplexes. Furthermore, we show that the use of dilated distance-generating functions enable us to decompose the mirror descent algorithm, and its optimistic variant, into local mirror descent algorithms at each information set. This decomposition mirrors the structure of the counterfactual regret minimization framework, and enables important techniques in practice, such as distributed updates and pruning of cold parts of the game tree. Our algorithms provably converge at a rate of $T^{-1}$, which is superior to prior counterfactual regret minimization algorithms. We experimentally compare to the popular algorithm CFR+, which has a theoretical convergence rate of $T^{-0.5}$ in theory, but is known to often converge at a rate of $T^{-1}$, or better, in practice. We give an example matrix game where CFR+ experimentally converges at a relatively slow rate of $T^{-0.74}$, whereas our optimistic methods converge faster than $T^{-1}$. We go on to show that our fast rate also holds in the Kuhn poker game, which is an extensive-form game. For games with deeper game trees however, we find that CFR+ is still faster. Finally we show that when the goal is minimizing regret, rather than computing a Nash equilibrium, our optimistic methods can outperform CFR+, even in deep game trees.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Transformer-Based Spatial-Temporal Counterfactual Outcomes Estimation
Unveiling Causal Reasoning in Large Language Models: Reality or Mirage?
Argumentative Ensembling for Robust Recourse under Model Multiplicity
저전력 에지 플랫폼을 위한 비전 기반 실시간 낙상 감지
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만 미만 매개변수의 네트워크로 자원 제약 에지 장치에서 실시간 추론이 가능하다. 광범위한 실험은 우수한 물리적 해석 가능성과 함께 경쟁력 있는 정확도를 보여 주며, 저연산 시각적 낙상 감지에 대한 효과를 입증한다.
스트리밍 개입: 비디오 대규모 언어 모델은 실수가 발생할 때 이를 수정할 수 있는가?
Streaming Interventions: Can Video Large Language Models Correct Mistakes as They Occur?
요리와 같은 일상적인 기술을 배우는 일은 온라인 비디오와 같은 교육용 미디어에 점점 더 의존하고 있습니다. 이는 비디오(및 멀티모달) 대규모 언어 모델(LLM)을 작업 가이드 어시스턴트로 활용할 수 있는 가능성을 열어줍니다. 잠재적인 작업 가이드 어시스턴트가 실제 환경에서 성공하기 위해 필수적인 능력은 사용자를 안내하기 위해 실수가 드러나는 즉시 선제적으로 개입하는 능력입니다. 이러한 핵심 능력을 평가하기 위해, 우리는 현실적인 요리 시나리오에서 반응형 단계별 작업 가이드를 평가하는 벤치마크인 Ego-MC-Bench(Mistake Corrections)를 소개합니다. 광범위한 실험을 통해 Ego-MC-Bench가 최첨단 비디오 LLM에게 매우 도전적인 과제임을 확인했습니다. 우리는 주된 원인이 이 작업에 대해 모델을 미세조정할 학습 데이터의 가용성이 제한되어 있기 때문이라고 주장합니다. 광범위한 요리 비디오 데이터셋이 존재하지만, 기존 데이터셋에는 적절한 시점에 이루어지는 개입과 함께 실수에 대한 예제가 부족합니다. 이러한 데이터 제한을 해결하기 위해, 우리는 또한 비대화형 요리 비디오를 선제적 개입을 보여주는 지도 학습 예제로 변환하여 생성된 반사실적 합성 데이터셋인 Ego-CoMist를 소개합니다. Ego-CoMist로 미세조정을 수행하면, 특히 엣지 디바이스에서 지원을 제공하는 데 적합한 더 작고 효율적인 비디오 LLM의 성능이 향상됨을 보여줍니다.
텍스트-이미지 모델은 귀납주의적 칠면조인가? 인과 추론을 위한 반사실적 벤치마크
Are Text-to-Image Models Inductivist Turkeys? A Counterfactual Benchmark for Causal Reasoning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.