From the 1 of 6 linked papers with an AI index.
6 papers
A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +2
Subsampling theorems for constraint satisfaction problems (CSPs) guarantee that the value of the CSP is approximately preserved after restricting it to small random subsets of vari…
A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
The paper presents a method to construct ε‑covers for the joint value sets of constant-degree polynomials over convex domains, enabling quasi‑polynomial time approximation schemes…
Learning Correlated Reward Models: Statistical Barriers and Opportunities
Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Gabriele Farina +1
Random Utility Models (RUMs) are a classical framework for modeling user preferences and play a key role in reward modeling for Reinforcement Learning from Human Feedback (RLHF). H…
Improved Hardness Results for Min-Max Optimization with Coupled Constraints
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We investigate the computational complexity of min-max optimization under coupled constraints. The work of Daskalakis, Skoulakis, and Zampetakis [DSZ21] was the first to study min-…
Superhuman AI for Stratego Using Self-Play Reinforcement Learning and Test-Time Search
Samuel Sokota, Eugene Vinitsky, Hengyuan Hu +2
Few classical games have been regarded as such significant benchmarks of artificial intelligence as to have justified training costs in the millions of dollars. Among these, Strate…
The Complexity of Correlated Equilibria in Generalized Games
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
Correlated equilibria -- and their generalization -equilibria -- are a fundamental object of study in game theory, offering a more tractable alternative to Nash equilibria in m…