Imperfect-Information Extensive-Form Games (IIEFGs) is a prevalent model for real-world games involving imperfect information and sequential plays. The Extensive-Form Correlated Equilibrium (EFCE) has been proposed as a natural solution concept for multi-player general-sum IIEFGs. However, existing algorithms for finding an EFCE require full feedback from the game, and it remains open how to efficiently learn the EFCE in the more challenging bandit feedback setting where the game can only be learned by observations from repeated playing. This paper presents the first sample-efficient algorithm for learning the EFCE from bandit feedback. We begin by proposing K-EFCE--a generalized definition that allows players to observe and deviate from the recommended actions for K times. The K-EFCE includes the EFCE as a special case at K = 1, and is an increasingly stricter notion of equilibrium as K increases.

Pseudo-games, or abstract economies [4], are optimization problems that are closely related to min-max Stackelberg games, but which are technically not games, as noted by Facchinei and Kanzow [26, 27], because each player's strategy set is not fixed at the outset (i.e., before they have to make a decision), but instead depends on the other players' choices. In this appendix, we formally define two-player, zero-sum pseudo-games,10 and discuss how they differ from min-max Stackelberg games. We also define the equilibrium concept par excellence of pseudo-games, namely generalized Nash equilibrium, and juxtapose its definition with vanilla Nash equilibrium. A two-player, zero-sum pseudo-game comprises two players, with respective payoff functions f(x,y)and f(x,y), and respective strategy spaces given by the correspondences X: Y X and Y: X Y, i.e., set valued mappings that depend on the choice the other player takes. Pseudo-games are closely related to min-max Stackelberg games, as they both comprise agents with the same objectives and the same space of feasible strategy profiles, namely {(x,y) 2 X Y |8 k 2 [K],gk(x,y) 0}.

We study the design of computationally efficient online learning algorithms under smoothed analysis. In this setting, at every step an adversary generates a sample from an adaptively chosen distribution whose density is upper bounded by 1/ times the uniform density. Given access to an offline optimization (ERM) oracle, we give the first computationally efficient online algorithms whose sublinear regret depends only on the pseudo/VC dimension dof the class and the smoothness parameter .

Machine learning models can frequently produce systematic errors on critical subsets (or slices) of data that share common attributes. Discovering and explaining such model bugs is crucial for reliable model deployment. However, existing bug discovery and interpretation methods usually involve heavy human intervention and annotation, which can be cumbersome and have low bug coverage. In this paper, we propose HiBug, an automated framework for interpretable model debugging. Our approach utilizes large pre-trained models, such as chatGPT, to suggest human-understandable attributes that are related to the targeted computer vision tasks. By leveraging pre-trained vision-language models, we can efficiently identify common visual attributes of underperforming data slices using humanunderstandable terms. This enables us to uncover rare cases in the training data, identify spurious correlations in the model, and use the interpretable debug results to select or generate new training data for model improvement. Experimental results demonstrate the efficacy of the HiBug framework. Code is available at: https://github.com/cure-lab/HiBug.