English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In recent years, empirical game-theoretic analysis (EGTA) has emerged as apowerful tool for analyzing games in which an exact specification of theutilities is unavailable. Instead, EGTA assumes access to an oracle, i.e., asimulator, which can generate unbiased noisy samples of players' unknownutilities, given a strategy profile. Utilities can thus be empiricallyestimated by repeatedly querying the simulator. Recently, various progressivesampling (PS) algorithms have been proposed, which aim to produce PAC-stylelearning guarantees (e.g., approximate Nash equilibria with high probability)using as few simulator queries as possible. One recent work introduces apruning technique called regret-pruning which further minimizes the number ofsimulator queries placed in PS algorithms which aim to learn pure Nashequilibria. In this paper, we address a serious limitation of this originalregret pruning approach -- it is only able to guarantee that true pure Nashequilibria of the empirical game are approximate equilibria of the true game,and is unable to provide any strong guarantees regarding the efficacy ofapproximate pure Nash equilibria. This is a significant limitation since inmany games, pure Nash equilibria are computationally intractable to find, oreven non-existent. We introduce three novel regret pruning variations. Thefirst two variations generalize the original regret pruning approach to yieldguarantees for approximate pure Nash equilibria of the empirical game. Thethird variation goes further to even yield strong guarantees for allapproximate mixed Nash equilibria of the empirical game. We use these regretpruning variations to design two novel progressive sampling algorithms, PS-REG+and PS-REG-M, which experimentally outperform the previous state-of-the-artalgorithms for learning pure and mixed equilibria, respectively, ofsimulation-based games.

Regret Pruning for Learning Equilibria in Simulation-Based Games