Collaborating Authors

Algorithm selection by rational metareasoning as a model of human strategy selection

Neural Information Processing Systems

Selecting the right algorithm is an important problem in computer science, because the algorithm often has to exploit the structure of the input to be efficient. The human mind faces the same challenge. Therefore, solutions to the algorithm selection problem can inspire models of human strategy selection and vice versa. Here, we view the algorithm selection problem as a special case of metareasoning and derive a solution that outperforms existing methods in sorting algorithm selection. We apply our theory to model how people choose between cognitive strategies and test its prediction in a behavioral experiment.

Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies

AAAI Conferences

Strong stubborn sets have recently been analyzed and successfully applied as a pruning technique for planning as heuristic search. Strong stubborn sets are defined declaratively as constraints over operator sets. We show how these constraints can be relaxed to offer more freedom in choosing stubborn sets while maintaining the correctness and optimality of the approach. In general, many operator sets satisfy the definition of stubborn sets. We study different strategies for selecting among these possibilities and show that existing approaches can be considerably improved by rather simple strategies, eliminating most of the overhead of the previous state of the art.

Rock, Paper, StarCraft: Strategy Selection in Real-Time Strategy Games

AAAI Conferences

The correct choice of strategy is crucial for a successful real-time strategy (RTS) game player. Generally speaking, a strategy determines the sequence of actions the player will take in order to defeat his/her opponents. In this paper we present a systematic study of strategy selection in the popular RTS game StarCraft. We treat the choice of strategy as a game itself and test several strategy selection techniques, including Nash Equilibrium and safe opponent exploitation. We adopt a subset of AIIDE 2015 StarCraft AI tournament bots as the available strategies and our results suggest that it is useful to deviate from Nash Equilibrium to exploit sub-optimal opponents on strategy selection, confirming insights from computer rock-paper-scissors tournaments.

Sufficiency-Based Selection Strategy for MCTS

AAAI Conferences

Monte-Carlo Tree Search (MCTS) has proved a remarkably effective decision mechanism in many different game domains, including computer Go and general game playing (GGP).  However, in GGP, where many disparate games are played, certain type of games have proved to be particularly problematic for MCTS.  One of the problems are game trees with so-called optimistic moves, that is, bad moves that superficially look good but potentially require much simulation effort to prove otherwise.  Such scenarios can be difficult to identify in real time and can lead to suboptimal or even harmful decisions. In this paper we investigate a selection strategy for MCTS to alleviate this problem. The strategy, called sufficiency threshold, concentrates simulation effort better for resolving potential optimistic move scenarios.  The improved strategy is evaluated empirically in an n-arm-bandit test domain for highlighting its properties as well as in a state-of-the-art GGP agent to demonstrate its effectiveness in practice.  The new strategy shows significant improvements in both domains.

Bandit-based Communication-Efficient Client Selection Strategies for Federated Learning Artificial Intelligence

Due to communication constraints and intermittent client availability in federated learning, only a subset of clients can participate in each training round. While most prior works assume uniform and unbiased client selection, recent work on biased client selection has shown that selecting clients with higher local losses can improve error convergence speed. However, previously proposed biased selection strategies either require additional communication cost for evaluating the exact local loss or utilize stale local loss, which can even make the model diverge. In this paper, we present a bandit-based communication-efficient client selection strategy UCB-CS that achieves faster convergence with lower communication overhead. We also demonstrate how client selection can be used to improve fairness.