Abstract

Stackelberg games have found a role in a number of applications including modeling market competition, identifying traffic equilibrium, developing practical security applications and many others. While a number of solution approaches have been developed for these games in a variety of contexts that use mathematical optimization, analytical analysis or heuristic based solutions, literature has been quite sparse on the usage of Genetic Algorithm (GA) based techniques. In this paper, we develop a GA based solution to compute high quality mixed strategy solution for the leader to commit to, in a General Stackelberg Game (GSG). Our experiments showcase that the GA solution developed here indeed performs well in terms of scalability and provides reasonably good solution quality in terms of the average reward obtained.

Abstract

The teacher-student framework aims to improve the sample efficiency of RL algorithms by deploying an advising mechanism in which a teacher helps a student by guiding its exploration. Prior work in this field has considered an advising mechanism where the teacher advises the student about the optimal action to take in a given state. However, real-world teachers can leverage domain expertise to provide more informative signals. Using this insight, we propose to extend the current advising framework wherein the teacher would provide not only the optimal action but also a qualitative assessment of the state. We introduce a novel architecture, namely Advice Replay Memory (ARM), to effectively reuse the advice provided by the teacher. We demonstrate the robustness of our approach by showcasing our experiments on multiple Atari 2600 games using a fixed set of hyper-parameters. Additionally, we show that a student taking help even from a suboptimal teacher can achieve significant performance boosts and eventually outperform the teacher. Our approach outperforms the baselines even when provided with comparatively suboptimal teachers and an advising budget, which is smaller by orders of magnitude. The contributions of our paper are 4-fold (a) supplementing student’s knowledge by providing the state category (b) introduction of ARM to effectively reuse the advice throughout learning (c) ability to achieve significant performance boost even with a coarse state categorization (d) enabling the student to outperform the teacher.

Abstract

In modular reinforcement learning (MRL), a complex decision making problem is decomposed into multiple simpler subproblems each solved by a separate module. Often, these subproblems have conflicting goals, and incomparable reward scales. A composable decision making architecture requires that even the modules authored separately with possibly misaligned reward scales can be combined coherently. An arbitrator should consider different module’s action preferences to learn effective global action selection. We present a novel framework called GRACIAS that assigns fine-grained importance to the different modules based on their relevance in a given state, and enables composable decision making based on modern deep RL methods such as deep deterministic policy gradient (DDPG) and deep Q-learning. We provide insights into the convergence properties of GRACIAS and also show that previous MRL algorithms reduce to special cases of our framework. We experimentally demonstrate on several standard MRL domains that our approach works significantly better than the previous MRL methods, and is highly robust to incomparable reward scales. Our framework extends MRL to complex Atari games such as Qbert, and has a better learning curve than the conventional RL algorithms.

Abstract

Negotiation is an important component of the interaction process among humans. With increasing automation, autonomous agents are expected to take over a lot of this interaction process. Much of automated negotiation literature focuses on agents having a static and known reservation value. In situations involving dynamic environments e.g., an agent negotiating on behalf of a human regarding a meeting, agents can have a reservation value (RV) that is a function of time. This leads to a different set of challenges that may need additional reasoning about the concession behavior. In this paper, we build upon Negotiation algorithms such as ONAC (Optimal Non-Adaptive Concession) and TimeDependent Techniques such as Boulware which work on settings where the reservation value of the agent is fixed and known. Although these algorithms can encode dynamic RV, their concession behavior and hence the properties they were expected to display would be different from when the RV is static, even though the underlying negotiation algorithm remains the same. We, therefore, propose to use one of Counter, Bayesian Learning with Regression Analysis or LSTM model on top of each algorithm to develop the PredictRV strategy and show that PredictRV indeed performs better on two different metrics tested on two different domains on a variety of parameter settings. Keywords: Automated negotiation · Dynamic reservati

Abstract

Events during an emergency unfold in an unpredictable fashion which makes management of traffic duringemergencies pretty challenging. Furthermore, some vehicles would need to be evacuated faster than otherse.g., emergency vehicles or large vehicles carrying a lot more people. The Prioritized Routing Assistant forFlow of Traffic (PRAFT) enables prioritized routing during emergencies. However, the PRAFT solution doesnot compute multiple plans that can help handle better dynamic nature of emergencies. PRAFT maps theprioritized routing problem to the Minimum-Cost Maximum-Flow (MCMF) problem, hence its solution canaccommodate maximum flow while routing vehicles based on priority (maps higher priority vehicles to betterquality routes (i.e., ones with minimum cost)). We build upon the PRAFT solution to make the followingcontributions: (a) Develop a Pareto Minimum-Cost Maximum-Flow (Pareto-MCMF) algorithm which cancompute all the possible MCMF solutions. (b) Through a series of experiments performed using the wellknown traffic simulator SUMO, we could show that all the solutions generated by Pareto-MCMF indeed haveproperties similar to a MCMF solution thus providing multiple high quality options for traffic police to pickfrom depending on the situation.

Abstract

Negotiation is an important component of the interaction process among humans. With increasing automation, autonomous agents are expected to take over a lot of this interaction process. Much of automated negotiation literature focuses on agents having a static and known reservation value. In situations involving dynamic environments eg, an agent negotiating on behalf of a human regarding a meeting, agents can have a reservation value (RV) that is a function of time. This leads to a different set of challenges that may need additional reasoning about the concession behavior. In this paper, we build upon Negotiation algorithms such as ONAC (Optimal Non-Adaptive Concession) and Time-Dependent Techniques such as Boulware which work on settings where the reservation value of the agent is fixed and known. Although these algorithms can encode dynamic RV, their concession behavior and hence the …

Abstract

Automated negotiation between computational agents or between agents and humans has been a subject of active research with a focus on obtaining better quality solutions within reasonable time frames. The critical issue negotiators face during automated negotiation is that a negotiator may not always know the personality type of the opponent. Studies show that having information about the opponent improves the outcome of negotiation in general. However, unless there is prior knowledge, learning the opponent type in the limited amount of time or number of rounds in a negotiation is a difficult task. In this paper, we use a Partially Observable Markov Decision Process (POMDP) based modeling to perform better modeling of the opponent personality type. In particular, we focus on modeling the opponent into four different types to showcase that a better understanding of personality type can improve the outcome …

Abstract

Monitoring of wildlife is very important for maintaining sustainability of environment. In this paper, we pose Wildlife Monitoring as a Cooperative Target Observation (CTO) problem and propose a Multi Criteria Decision Analysis (MCDA) based algorithm named MCDA-CTO, to maximize the observation of different animal species by Unmanned Aerial Vehicles (UAVs) and to effectively handle multiple target types and the multiple criteria that arise due to targets and environmental factors, during decision making. UAVs have uncertainty in observation of targets which makes it challenging to develop a high-quality monitoring strategy. We therefore develop monitoring techniques that explicitly take actions to improve belief about the true type of targets being observed. In wildlife monitoring, it is often reasonable to assume that the observers may themselves be a subject of observation by unknown adversaries (poachers). Randomizing the observers actions can therefore help to make the target observation strategy less predictable. We then provide experimental validation which shows that the techniques we develop provide a higher (true positive/true negative) ratio along with better randomization than state of the art approaches.

Abstract

Periodic Double Auctions (PDAs) are commonly used in the real world for trading, eg in stock markets to determine stock opening prices, and energy markets to trade energy in order to balance net demand in smart grids, involving trillions of dollars in the process. A bidder, participating in such PDAs, has to plan for bids in the current auction as well as for the future auctions, which highlights the necessity of good bidding strategies. In this paper, we perform an equilibrium analysis of single unit single-shot double auctions with a certain clearing price and payment rule, which we refer to as ACPR, and find it intractable to analyze as number of participating agents increase. We further derive the best response for a bidder with complete information in a single-shot double auction with ACPR. Leveraging the theory developed for single-shot double auction and taking the PowerTAC wholesale market PDA as our testbed, we proceed by modeling the PDA of PowerTAC as an MDP. We propose a novel bidding strategy, namely MDPLCPBS. We empirically show that MDPLCPBS follows the equilibrium strategy for double auctions that we previously analyze. In addition, we benchmark our strategy against the baseline and the state-of-the-art bidding strategies for the PowerTAC wholesale market PDAs, and show that MDPLCPBS outperforms most of them consistently.

Abstract

Decentralized MDPs (Dec-MDPs) provide a rigorous framework for collaborative multi-agent sequential decisionmaking under uncertainty. However, their computational complexity limits the practical impact. To address this, we focus on a class of Dec-MDPs consisting of independent collaborating agents that are tied together through a global reward function that depends upon their entire histories of states and actions to accomplish joint tasks. To overcome scalability barrier, our main contributions are:(a) We propose a new actor-critic based Reinforcement Learning (RL) approach for event-based Dec-MDPs using successor features (SF) which is a value function representation that decouples the dynamics of the environment from the rewards;(b) We then present Dec-ESR (Decentralized Event based Successor Representation) which generalizes learning for event-based Dec-MDPs using SF within an end-to-end deep RL framework;(c) We also show that Dec-ESR allows useful transfer of information on related but different tasks, hence bootstraps the learning for faster convergence on new tasks;(d) For validation purposes, we test our approach on a large multi-agent coverage problem which models schedule coordination of agents in a real urban subway network and achieves better quality solutions than previous best approaches.