United Kingdom

The classical &#39;buy or rent&#39; ski-rental problem was recently considered in the setting where multiple experts (such as Machine learning algorithms) advice on the length of the ski season. Here, robust algorithms were developed with improved theoretical performance over adversarial scenarios where such expert predictions were unavailable. We consider a variant of this problem which we call the &#39;sequential ski-rental&#39; problem. Here, a sequence of ski-rental problems has to be solved in an online fashion where both the buy cost and the length of ski season are unknown to the learner. The learner has access to two sets of experts, one set who advise on the true cost of buying the ski and another set who advise on the length of the ski season. Under certain stochastic assumptions on the experts who predict the buy costs, we develop online algorithms and prove regret bounds for the same. Our experimental evaluations confirm our theoretical results.

AAMAS 2021

Sequential Ski Rental Problem

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://s3.eu-west-1.amazonaws.com/underline.prod/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


AAAI 2023

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

The classical 'buy or rent' ski-rental problem was recently considered in the setting where multiple experts (such as Machine learning algorithms) advice on the length of the ski season. Here, robust algorithms were developed with improved theoretical performance over adversarial scenarios where such expert predictions were unavailable. We consider a variant of this problem which we call the 'sequential ski-rental' problem. Here, a sequence of ski-rental problems has to be solved in an online fashion where both the buy cost and the length of ski season are unknown to the learner. The learner has access to two sets of experts, one set who advise on the true cost of buying the ski and another set who advise on the length of the ski season. Under certain stochastic assumptions on the experts who predict the buy costs, we develop online algorithms and prove regret bounds for the same. Our experimental evaluations confirm our theoretical results.

technical paper

Although reinforcement learning has been successfully applied in many domains in recent years, we still lack agents that can systematically generalize. While relational inductive biases that fit a task can improve generalization of RL agents, these biases are commonly hard-coded directly in the agent's neural architecture. In this work, we show that we can incorporate relational inductive biases, encoded in the form of relational graphs, into agents. Based on this insight, we propose Grid-to-Graph (GTG), a mapping from grid structures to relational graphs that carry useful spatial relational inductive biases when processed through a Relational Graph Convolution Network (R-GCN). We show that, with GTG, R-GCNs generalize better both in terms of in-distribution and out-of-distribution compared to baselines based on Convolutional Neural Networks and Neural Logic Machines on challenging procedurally generated environments and MinAtar. Furthermore, we show that GTG produces agents that can jointly reason over observations and environment dynamics encoded in knowledge bases.

Grid-to-Graph: Flexible Spatial Relational Inductive Biases for Reinforcement Learning

In this paper, we study the problem of deceptive reinforcement learning to preserve the privacy of a reward function. Reinforcement learning is the problem of finding a behaviour policy based on rewards received from exploratory behaviour. A key ingredient in reinforcement learning is a 
 which determines how much reward (negative or positive) is given and when. However, in some situations, we may want to keep a reward function private; that is, to make it difficult for an observer to determine the reward function used. We define the problem of privacy-preserving reinforcement learning, and present two models for solving it. These models are based on 
 -- a form of deception that 'hides the truth'. We evaluate our models both computationally and via human behavioural experiments. Results show that the resulting policies are indeed deceptive, and that participants can determine the true reward function less reliably than that of an honest agent.

Deceptive Reinforcement Learning for Privacy-Preserving Planning

Causal structure discovery from observational data is fundamental to the causal understanding of autonomous systems such as medical decision support systems, advertising campaigns and self-driving cars. This is essential to solve well-known causal decision making and prediction problems associated with those real-world applications. Recently, recursive causal discovery algorithms have gained particular attention among the research community due to their ability to provide good results by using Conditional Independent (CI) tests in smaller sub-problems. However, each of such algorithms needs a refinement function to remove undesired causal relations of the discovered graphs. Notably, with the increase of the problem size, the computation cost (i.e., the number of CI-tests) of the refinement function makes an algorithm expensive to deploy in practice. This paper proposes a generic causal structure refinement strategy that can locate the undesired relations with a small number of CI-tests, thus speeding up the algorithm for large and complex problems. We theoretically prove the correctness of our algorithm. We then empirically evaluate its performance against the state-of-the-art algorithms in terms of solution quality and completion time in synthetic and real datasets.

Accelerating Recursive Partition-Based Causal Structure Learning

Solving the Multi-Agent Path Finding (MAPF) problem optimally is known to be NP-Hard for both make-span and total arrival time minimization. While many algorithms have been developed to solve MAPF problems, there is no dominating optimal MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. In this work, we develop the deep convolutional network MAPFAST (Multi-Agent Path Finding Algorithm SelecTor), which takes a MAPF problem instance and attempts to select the fastest algorithm to use from a portfolio of algorithms. We improve the performance of our model by including single-agent shortest paths in the instance embedding given to our model and by utilizing supplemental loss functions in addition to a classification loss. We evaluate our model on a large and diverse dataset of MAPF instances, showing that it outperforms all individual algorithms in its portfolio as well as the state-of-the-art optimal MAPF algorithm selector. We also provide an analysis of algorithm behavior in our dataset to gain a deeper understanding of optimal MAPF algorithms' strengths and weaknesses to help other researchers leverage different heuristics in algorithm designs.

MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings

We present an extension of the organizational model and infrastructure adopted in JaCaMo, that explicitly encompasses the notion of exception. We propose an exception handling mechanism for organization management in multi-agent systems. This mechanism relies on abstractions that are seamlessly integrated with organizational concepts, such as responsibilities, goals and norms.

Distributing Responsibilities for Exception Handling in JaCaMo

Value alignment is a crucial aspect of ethical multiagent systems. An important step toward value alignment is identifying values specific to an application context. However, identifying context-specific values is complex and cognitively demanding. To support this process, we develop a methodology and a collaborative web platform that employs AI techniques. We describe this platform, highlighting its intuitive design and implementation.

A Collaborative Platform for Identifying Context-Specific Values

Evolutionary Game Theory is an application of game theory to evolving populations of organisms. Of recent interest are EGT models situated on structured populations or spatial evolutionary games. Due to the complexity added by introducing a population structure, model analysis is usually performed through agent-based Monte-Carlo simulations. However, it can be difficult to obtain desired quantities of interest from these simulations due to stochastic effects. We define a framework for modeling spatial evolutionary games using Dynamic Bayesian Networks that capture the underlying stochastic process. The resulting Dynamic Bayesian Networks can be queried for quantities of interest by performing exact inference on the network. We then propose a method for producing approximations of the spatial evolutionary game through the truncation of the corresponding DBN, taking advantage of the high symmetry of the model. This method generalizes mean-field and pair approximations in the literature for spatial evolutionary games. Furthermore, we show empirical results demonstrating the capability of the method to obtain much better accuracy than pair approximation with respect to stochastic simulations.

Approximating Spatial Evolutionary Games using Bayesian Networks

Participatory Budgeting processes are usually designed to span several years, with referenda for new budget allocations taking place regularly. This paper presents the first formalization of long-term PB. We introduce a theory of fairness for this setting, investigate under which conditions our fairness criteria can be satisfied, and analyze the computational complexity of verifying them.

Fairness in Long-Term Participatory Budgeting

In recent work, Gourvès, Lesca, and Wilczynski propose a variant of the classic housing markets model where the matching between agents and objects evolves through Pareto-improving swaps between pairs of adjacent agents in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings. In their work and other follow-up works, these questions have been studied for various classes of graphs: stars, paths, generalized stars (i.e., trees where at most one vertex has degree greater than two), trees, and cliques. For generalized stars and trees, it remains open whether a Pareto-efficient reachable matching can be found in polynomial time.

Object Allocation Over a Network of Objects: Mobile Agents with Strict Preferences

Most frameworks for computing solution concepts in hedonic games are theoretical in nature, and require complete knowledge of all agent preferences, an impractical assumption in real-world settings. This paper presents the first application of strategic hedonic game models on real-world data. We show that PAC stable solutions can reflect Members of Knesset' political positions and reveal politicians who are known to deviate from party lines. Moreover, these models compare favorably to machine learning models.

Sequential Ski Rental Problem

Downloads

Next from AAMAS 2021

Grid-to-Graph: Flexible Spatial Relational Inductive Biases for Reinforcement Learning

Similar lecture

Fault-Tolerant Offline Multi-Agent Path Planning

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Sequential Ski Rental Problem

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2021

Grid-to-Graph: Flexible Spatial Relational Inductive Biases for Reinforcement Learning

Similar lecture

Fault-Tolerant Offline Multi-Agent Path Planning

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads