Planning in the Presence of Cost Functions Controlled by an Adversary

By H. Brendan McMahan, Geoffrey J. Gordon, Avrim Blum. 2003

384 citations recorded by the source corpus.

Subfields: Reinforcement Learning, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Reinforcement Learning

In Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “Policy-Space Response Oracles (PSRO) generalizes fictitious play and the double-oracle algorithm [36, 40] by analyzing this meta-game using empirical game-theoretic analysis [74].”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, neutral): “…games, such as ﬁctitious play (Robinson, 1951; Monderer & Shapley, 1996; Heinrich & Silver, 2016; Kamra et al., 2019; Han & Hu, 2019), double-oracle (McMahan et al., 2003; Lanctot et al., 2017; Wang et al., 2019; Balduzzi et al., 2019) and regularized self-play (Foerster et al., 2018; Perolat et…”
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, neutral): “The double oracle (DO) algorithm [71] solves a set of (two-player, normal-form) subgames induced by subsets Π ⊂ Π at time t.”
Open-Ended Learning Leads to Generally Capable Agents (2021, methodology): “Iterative notions of improvements have been used, particularly in multiagent systems, either explicitly by targeting the goal with respect to known opponents (Balduzzi et al., 2019; McMahan et al., 2003), implicitly by using internal ranking between agents (Jaderberg et al.”
Open-ended Learning in Symmetric Zero-sum Games (2019, methodology): “The algorithm is an extension of the double oracle algorithm (McMahan et al., 2003) to FFG s, see also (Zinkevich et al., 2007; Hansen et al., 2008).”
Depth-Limited Solving for Imperfect-Information Games (2018, result): “This self-generative approach bears some resemblance to the double oracle algorithm [25] and recent work on generation of opponent strategies in multi-agent RL [23].”
Algorithms for computing strategies in two-player simultaneous move games (2016, methodology): “The main idea is to integrate two key components: (1) instead of evaluating all successors in each state of the game and solving a normal-form game, the algorithm exploits the iterative framework known in game theory as doubleoracle algorithm [39]; (2) the algorithm computes bounds on the utility va”
Fairness in Multi-Agent Sequential Decision-Making (2014, methodology): “Algorithm 1 shares some similarities with the double oracle algorithm proposed in [8] for iteratively solving zero-sum games.”
Joint Policy Search for Multi-agent Collaboration with Imperfect Information (2020, background): “For imperfect information games (IG), Double-Oracle [26], Fictitious (self-)play [20] and Counterfactual Regret Minimization (CFR [44, 23]) can be proven to achieve Nash equilibrium.”
A Fast Bundle-based Anytime Algorithm for Poker and other Convex Games (2007, background): “While McMahan et al. [2003] demonstrated that for some problems only a few iterations of this algorithm can produce very good solutions, in general this will not be the case.”
Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games (2021, methodology): “Adapted from double oracle [22], policy space response oracle (PSRO) [15, 5] has been serving as a powerful tool to solve the nash equilibrium (NE) in zero-sum games.”
An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information (2014, methodology): “We now describe the concept of column/constraint generation techniques applied previously in normal-form games and known as the double-oracle algorithm (McMahan et al., 2003).”
From physical security to cybersecurity (2015, methodology): “This algorithm is inspired by the double oracle algorithm of solving large-scale games [29].”
Time and Space: Why Imperfect Information Games are Hard (2018, methodology): “Double oracle methods [63] also let us solve a reduced problem, using a best response as a computable oracle.”
Cognitive radio: brain-empowered wireless communications (2005, background): “The reader is referred to [64] for such an example involving a robot path-planning problem, which may be likened to a cognitive radio problem made difficult by the actions of a clever opponent.”
Deep Reinforcement Learning for Green Security Games with Real-Time Information (2018, methodology): “When the game is zero-sum, common solution concepts such as Nash equilibrium (NE), SSE, Minimax, and Max-imin, coincide, and a DO framework (McMahan, Gordon, and Blum 2003) is commonly applied to solve the game ef-ﬁciently when the action space is large.”