Reinforcement learning with reward shaping is a well established but often computationally expensive approach to large multiagent systems. Agent partitioning can reduce this computational complexity by treating each partition of agents as an independent problem. We introduce a novel agent partitioning approach called Reward/Utility-Based Impact (RUBI). RUBI finds an effective partitioning of agents while requiring no prior domain knowledge, improves performance by discovering a non-trivial agent partitioning, and leads to faster simulations. We test RUBI in the Air Traffic Flow Management Problem (ATFMP), where there are tens of thousands of aircraft affecting the system and no obvious similarity metric between agents. When partitioning with RUBI in the ATFMP, there is a 37% increase in performance, with a 510x speed increase over non-partitioning approaches. Additionally, RUBI matches the performance of the current domain-dependent ATFMP gold standard using no prior knowledge and with 10% faster performance.

Voting among different agents is a powerful tool in problem solving, and it has been widely applied to improve the performance in machine learning. However, the potential of voting has been explored only in improving the ability of finding the correct answer to a complex problem. In this paper we present a novel benefit in voting, that has not been observed before: we show that we can use the voting patterns to assess the performance of a team and predict their final outcome. This prediction can be executed at any moment during problem-solving and it is completely domain independent. We present a preliminary theoretical explanation of why our prediction method works, where we show that the accuracy is better for diverse teams composed by different agents than for uniform teams made of copies of the same agent. We also perform experiments in the Computer Go domain, where we show that we can obtain a high accuracy in predicting the final outcome of the games. We analyze the prediction accuracy for 3 different teams, and we show that the prediction works significantly better for a diverse team. Since our approach is completely domain independent, it can be easily applied to a variety of domains, such as the video games in the Arcade Learning Environment.

Reinforcement learning is a powerful machine learning paradigm that allows agents to autonomously learn to maximize a scalar reward. However, it often suffers from poor initial performance and long learning times. This paper discusses how collecting online human feedback, both in real time and post hoc, can potentially improve the performance of such learning systems. We use the game Pac-Man to simulate a navigation setting and show that workers are able to accurately identify both when a sub-optimal action is executed, and what action should have been performed instead. Our results demonstrate that the crowd is capable of generating helpful input. We conclude with a discussion the types of errors that occur most commonly when engaging human workers for this task, and a discussion of how such data could be used to improve learning. Our work serves as a critical first step in designing systems that use real-time human feedback to improve the learning performance of automated systems on-the-fly. Figure 1: This screenshot shows the web interface of the user study with game layout, and components of the Pac-Man game: 1) Pac-Man, 2) 4 Ghosts, 3) Pills, and 4) Power Pills.

We show that setting a reasonable frame skip can be critical to the performance of agents learning to play Atari 2600 games. In all of the six games in our experiments, frame skip is a strong determinant of success. For two of these games, setting a large frame skip leads to state-of-the-art performance.

Recently it has been shown that deep neural networks can learn to play Atari games by directly observing raw pixels of the playing area. We show how apprenticeship learning can be applied in this setting so that an agent can learn to perform a task (i.e. play a game) by observing the expert, without any explicitly provided knowledge of the game’s internal state or objectives.

Teaching robots about objects in their environment requires a multimodal correlation of images and linguistic descriptions to build complete feature and object models.  These models can be created manually by collecting images and related keywords and presenting the pairings to robots, but doing so is tedious and unnatural.  This work abstracts the problem of training robots to learn about the world around them by introducing I Spy , an interactive dialogue- and vision-based game in which players place objects in front of a humanoid robot and challenge it to guess which object they have in mind.  The robot gradually learns about the objects and the features which describe them through repeated games, by updating its knowledge with newly captured training images.  This paper details I Spy's learning and gaming processes, describes the approaches taken to extract information from multiple modalities both before and during gameplay, and finally discusses the results of a study designed to evaluate the game's model accuracy over time, its overall performance, and its appeal to human players.

In the context of soccer robotics, ball dribbling is a complex behavior where a robot player attempts to maneuver the ball in a very controlled way, while moving towards a desired target. To learn when and how to modify the robot’s velocity vector is a complex problem, hardly solvable in an effective way with methods based on identification of the system dynamics and/or kinematics and mathematical models. We propose a decentralized reinforcement learning strategy, where each component of the omnidirectional biped walk (𝑣𝑥,𝑣𝑦,𝑣𝜃) is learned in parallel with single-agents working in a multiagent task. Moreover, we propose an approach to accelerate the decentralized learning based on knowledge transfer from simple linear controllers. Obtained results are successful; with less human effort, and less required designer knowledge, the decentralized reinforcement learning scheme shows better performances than the current dribbling engine used by UChile Robotics Team in the SPL robot soccer competitions. The proposed decentralized rein- forcement learning scheme achieves asymptotic performance after 1500 episodes and can be accelerated up to 70% by using our approach to share actions.

This paper presents a divide-and-conquer decomposition for solving continuous state reinforcement learning problems. The contribution lies in a method for stitching together continuous state subtasks in a near-seamless manner along wide continuous boundaries. We introduce the concept of Termination Approximation where the set of subtask termination states are covered by goal sets to generate a set of subtask option policies. The approach employs hierarchical reinforcement learning methods and exploits any underlying repetition in continuous problems to allow reuse of the option policies both within a problem and across related problems. The approach is illustrated using a series of challenging racecar problems.

Auction mechanisms are very well known methods to allocate tasks when several agents are involved. Particularly, multi-attribute auctions are a special mechanism that allows the consideration of task attributes other than prices, such as delivery time or energy consumptions. Incentive compatible mechanisms encourage agents to reveal the attributes which agents estimate truthful, however, these mechanisms by themselves cannot know if such estimations are reliable or not due to uncertainty. Under such circumstances, trust could complement incentive compatibility reducing the risk of losses by the auctioneer. The use of trust in auctions is a well-studied problem; however, most of the works in the literature focus on how to model trust rather on how trust is used in the mechanism. Thus, this paper proposes an easy and systematic way to include a multi-faceted model of trust into multi-attribute auctions. Conversely to other previous works where trust is only used in the winner determination problem, the presented approach uses trust both in deciding the winner of the auction and in the payment to the corresponding bidder. According to the results obtained from the experimentation, the use of trust following the methodology presented in this paper highly reduces the number of winner bids from unreliable bidders and, therefore, the number of tasks executed in worse conditions than the agreed. Complementary, this paper proposes a new trust adaptation method which consists of increasing or decreasing the trust value (depending on whether the task is executed properly or not) according to a simple mathematical function with asymptotes on 0 and 1. This model does not present the rigidity problem present in other models of the literature when it comes to agents that have inconstant performances.

The task of computing approximate Nash equilibria in large zero-sum extensive-form games has received a tremendous amount of attention due mainly to the Annual Computer Poker Competition. Immediately after its inception, two competing and seemingly different approaches emerged---one an application of no-regret online learning, the other a sophisticated gradient method applied to a convex-concave saddle-point formulation. Since then, both approaches have grown in relative isolation with advancements on one side not effecting the other. In this paper, we rectify this by dissecting and, in a sense, unify the two views.