Author name cluster

Garrett Andersen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

NeurIPS Conference 2017 Conference Paper

Active Exploration for Learning Symbolic Representations

Garrett Andersen
George Konidaris

We introduce an online active exploration algorithm for data-efficiently learning an abstract symbolic model of an environment. Our algorithm is divided into two parts: the first part quickly generates an intermediate Bayesian symbolic model from the data that the agent has collected so far, which the agent can then use along with the second part to guide its future exploration towards regions of the state space that the model is uncertain about. We show that our algorithm outperforms random and greedy exploration policies on two different computer game domains. The first domain is an Asteroids-inspired game with complex dynamics but basic logical structure. The second is the Treasure Game, with simpler dynamics but more complex logical structure.

PDF Details

IJCAI Conference 2016 Conference Paper

ATUCAPTS: Automated Tests that a User Cannot Pass Twice Simultaneously

Garrett Andersen
Vincent Conitzer

In highly anonymous environments such as the Internet, many applications suffer from the fact that a single user can pose as multiple users. Indeed, presumably many potential applications do not even get off the ground as a result. Consider the example of an online vote. Requiring voters to provide identifying information, to the extent that this is even feasible, can significantly deter participation. On the other hand, not doing so makes it possible for a single individual to vote more than once, so that the result may become almost meaningless. (A quick web search will reveal many examples of Internet polls with bizarre outcomes. ) CAPTCHAs may prevent running a program that votes many times, but they do nothing to prevent a single user from voting many times by hand. In this paper, we propose ATUCAPTS (Automated Tests That a User Cannot Pass Twice Simultaneously) as a solution. ATUCAPTS are automatically generated tests such that it is (1) easy for a user to pass one instance, but (2) extremely difficult for a user to pass two instances at the same time. Thus, if it is feasible to require all users to take such a test at the same time, we can verify that no user holds more than one account. We propose a specific class of ATUCAPTS and present the results of a human subjects study to validate that they satisfy the two properties above. We also introduce several theoretical models of how well an attacker might perform and show that these models still allow for good performance on both (1) and (2) with reasonable test lengths.

PDF Details

AAAI Conference 2013 Conference Paper

Fast Equilibrium Computation for Infinitely Repeated Games

Garrett Andersen
Vincent Conitzer

It is known that an equilibrium of an infinitely repeated two-player game (with limit average payoffs) can be computed in polynomial time, as follows: according to the folk theorem, we compute minimax strategies for both players to calculate the punishment values, and subsequently find a mixture over outcomes that exceeds these punishment values. However, for very large games, even computing minimax strategies can be prohibitive. In this paper, we propose an algorithmic framework for computing equilibria of repeated games that does not require linear programming and that does not necessarily need to inspect all payoffs of the game. This algorithm necessarily sometimes fails to compute an equilibrium, but we mathematically demonstrate that most of the time it succeeds quickly on uniformly random games, and experimentally demonstrate this for other classes of games. This also holds for games with more than two players, for which no efficient general algorithms are known.

PDF Details