Papers
2024
- Personalized Reinforcement Learning with a Budget of PoliciesDmitry Ivanov , and Omer Ben-PoratIn Proceedings of the AAAI Conference on Artificial Intelligence , 2024
Personalization in machine learning (ML) tailors models’ decisions to the individual characteristics of users. While this approach has seen success in areas like recommender systems, its expansion into high-stakes fields such as healthcare and autonomous driving is hindered by the extensive regulatory approval processes involved. To address this challenge, we propose a novel framework termed represented Markov Decision Processes (r-MDPs) that is designed to balance the need for personalization with the regulatory constraints. In an r-MDP, we cater to a diverse user population, each with unique preferences, through interaction with a small set of representative policies. Our objective is twofold: efficiently match each user to an appropriate representative policy and simultaneously optimize these policies to maximize overall social welfare. We develop two deep reinforcement learning algorithms that efficiently solve r-MDPs. These algorithms draw inspiration from the principles of classic K-means clustering and are underpinned by robust theoretical foundations. Our empirical investigations, conducted across a variety of simulated environments, showcase the algorithms’ ability to facilitate meaningful personalization even under constrained policy budgets. Furthermore, they demonstrate scalability, efficiently adapting to larger policy budgets.
@inproceedings{ivanov2024personalized, title = {Personalized Reinforcement Learning with a Budget of Policies}, author = {Ivanov, Dmitry and Ben-Porat, Omer}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, year = {2024}, }
2023
- Deep Contract Design via Discontinuous NetworksIn Advances in Neural Information Processing Systems (NeurIPS) , 2023
Contract design involves a principal who establishes contractual agreements about payments for outcomes that arise from the actions of an agent. In this paper, we initiate the study of deep learning for the automated design of optimal contracts. We introduce a novel representation: the Discontinuous ReLU (DeLU) network, which models the principal’s utility as a discontinuous piecewise affine function of the design of a contract where each piece corresponds to the agent taking a particular action. DeLU networks implicitly learn closed-form expressions for the incentive compatibility constraints of the agent and the utility maximization objective of the principal, and support parallel inference on each piece through linear programming or interior-point methods that solve for optimal contracts. We provide empirical results that demonstrate success in approximating the principal’s utility function with a small number of training samples and scaling to find approximately optimal contracts on problems with a large number of actions and outcomes.
@inproceedings{wang2023deep, author = {Wang, Tonghan and Duetting, Paul and Ivanov, Dmitry and Talgam-Cohen, Inbal and Parkes, David C}, booktitle = {Advances in Neural Information Processing Systems (NeurIPS)}, editor = {Oh, A. and Neumann, T. and Globerson, A. and Saenko, K. and Hardt, M. and Levine, S.}, pages = {65818--65836}, publisher = {Curran Associates, Inc.}, title = {Deep Contract Design via Discontinuous Networks}, volume = {36}, year = {2023}, } - Mediated Multi-Agent Reinforcement LearningDmitry Ivanov , Ilya Zisman , and Kirill ChernyshevIn Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , 2023
The majority of Multi-Agent Reinforcement Learning (MARL) literature equates the cooperation of self-interested agents in mixed environments to the problem of social welfare maximization, allowing agents to arbitrarily share rewards and private information. This results in agents that forgo their individual goals in favour of social good, which can potentially be exploited by selfish defectors. We argue that cooperation also requires agents’ identities and boundaries to be respected by making sure that the emergent behaviour is an equilibrium, i.e., a convention that no agent can deviate from and receive higher individual payoffs. Inspired by advances in mechanism design, we propose to solve the problem of cooperation, defined as finding socially beneficial equilibrium, by using mediators. A mediator is a benevolent entity that may act on behalf of agents, but only for the agents that agree to it. We show how a mediator can be trained alongside agents with policy gradient to maximize social welfare subject to constraints that encourage agents to cooperate through the mediator. Our experiments in matrix and iterative games highlight the potential power of applying mediators in MARL.
@inproceedings{ivanov2023mediated, title = {Mediated Multi-Agent Reinforcement Learning}, author = {Ivanov, Dmitry and Zisman, Ilya and Chernyshev, Kirill}, booktitle = {Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS)}, pages = {49--57}, year = {2023}, }
2022
- Optimal-er auctions through attentionDmitry Ivanov , Iskander Safiulin , Igor Filippov , and Ksenia BalabaevaIn Advances in Neural Information Processing Systems (NeurIPS) , 2022
RegretNet is a recent breakthrough in the automated design of revenue-maximizing auctions. It combines the flexibility of deep learning with the regret-based approach to relax the Incentive Compatibility (IC) constraint (that participants prefer to bid truthfully) in order to approximate optimal auctions. We propose two independent improvements of RegretNet. The first is a neural architecture denoted as RegretFormer that is based on attention layers. The second is a loss function that requires explicit specification of an acceptable IC violation denoted as regret budget. We investigate both modifications in an extensive experimental study that includes settings with constant and inconstant numbers of items and participants, as well as novel validation procedures tailored to regret-based approaches. We find that RegretFormer consistently outperforms RegretNet in revenue (ie is optimal-er) and that our loss function both simplifies hyperparameter tuning and allows to unambiguously control the revenue-regret trade-off by selecting the regret budget.
@inproceedings{ivanov2022optimal, title = {Optimal-er auctions through attention}, author = {Ivanov, Dmitry and Safiulin, Iskander and Filippov, Igor and Balabaeva, Ksenia}, booktitle = {Advances in Neural Information Processing Systems (NeurIPS)}, volume = {35}, pages = {34734--34747}, year = {2022}, }
2021
- Self-Imitation Learning from DemonstrationsGeorgiy Pshikhachev , Dmitry Ivanov , Vladimir Egorov , and Aleksei ShpilmanIn Deep RL Workshop at NeurIPS , 2021
Despite the numerous breakthroughs achieved with Reinforcement Learning (RL), solving environments with sparse rewards remains a challenging task that requires sophisticated exploration. Learning from Demonstrations (LfD) remedies this issue by guiding the agent’s exploration towards states experienced by an expert. Naturally, the benefits of this approach hinge on the quality of demonstrations, which are rarely optimal in realistic scenarios. Modern LfD algorithms require meticulous tuning of hyperparameters that control the influence of demonstrations and, as we show in the paper, struggle with learning from suboptimal demonstrations. To address these issues, we extend Self-Imitation Learning (SIL), a recent RL algorithm that exploits the agent’s past good experience, to the LfD setup by initializing its replay buffer with demonstrations. We denote our algorithm as SIL from Demonstrations (SILfD). We empirically show that SILfD can learn from demonstrations that are noisy or far from optimal and can automatically adjust the influence of demonstrations throughout the training without additional hyperparameters or handcrafted schedules. We also find SILfD superior to the existing state-of-the-art LfD algorithms in sparse environments, especially when demonstrations are highly suboptimal.
@inproceedings{pshikhachev2021self, title = {Self-Imitation Learning from Demonstrations}, author = {Pshikhachev, Georgiy and Ivanov, Dmitry and Egorov, Vladimir and Shpilman, Aleksei}, booktitle = {Deep RL Workshop at NeurIPS}, year = {2021}, key = {value}, } - Flatland competition 2020: MAPF and MARL for efficient train coordination on a grid worldFlorian Laurent , Manuel Schneider , Christian Scheller , Jeremy Watson , Jiaoyang Li , and 7 more authorsIn NeurIPS 2020 Competition and Demonstration Track , 2021
The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP). The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur, for example the breakdown of a vehicle. While solving the VRSP in various settings has been an active area in operations research (OR) for decades, the ever-growing complexity of modern railway networks makes dynamic real-time scheduling of traffic virtually impossible. Recently, multi-agent reinforcement learning (MARL) has successfully tackled challenging tasks where many agents need to be coordinated, such as multiplayer video games . However, the coordination of hundreds of agents in a real-life setting like a railway network remains challenging and the Flatland environment used for the competition models these real-world properties in a simplified manner. Submissions had to bring as many trains (agents) to their target stations in as little time as possible. While the best submissions were in the OR category, participants found many promising MARL approaches. Using both centralized and decentralized learning based approaches, top submissions used graph representations of the environment to construct tree-based observations. Further, different coordination mechanisms were implemented, such as communication and prioritization between agents. This paper presents the competition setup, four outstanding solutions to the competition, and a cross-comparison between them.
@inproceedings{laurent2021flatland, title = {Flatland competition 2020: MAPF and MARL for efficient train coordination on a grid world}, author = {Laurent, Florian and Schneider, Manuel and Scheller, Christian and Watson, Jeremy and Li, Jiaoyang and Chen, Zhe and Zheng, Yi and Chan, Shao-Hung and Makhnev, Konstantin and Svidchenko, Oleg and Ivanov, Dmitry and others}, booktitle = {NeurIPS 2020 Competition and Demonstration Track}, pages = {275--301}, year = {2021}, organization = {PMLR}, } - Balancing Rational and Other-Regarding Preferences in Cooperative-Competitive EnvironmentsDmitry Ivanov , Vladimir Egorov , and Aleksei ShpilmanIn Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS) , 2021
Recent reinforcement learning studies extensively explore the interplay between cooperative and competitive behaviour in mixed environments. Unlike cooperative environments where agents strive towards a common goal, mixed environments are notorious for the conflicts of selfish and social interests. As a consequence, purely rational agents often struggle to achieve and maintain cooperation. A prevalent approach to induce cooperative behaviour is to assign additional rewards based on other agents’ well-being. However, this approach suffers from the issue of multi-agent credit assignment, which can hinder performance. This issue is efficiently alleviated in cooperative setting with such state-of-the-art algorithms as QMIX and COMA. Still, when applied to mixed environments, these algorithms may result in unfair allocation of rewards. We propose BAROCCO, an extension of these algorithms capable to balance individual and social incentives. The mechanism behind BAROCCO is to train two distinct but interwoven components that jointly affect each agent’s decisions. Our meta-algorithm is compatible with both Q-learning and Actor-Critic frameworks. We experimentally confirm the advantages over the existing methods and explore the behavioural aspects of BAROCCO in two mixed multi-agent setups.
@inproceedings{ivanov2021balancing, title = {Balancing Rational and Other-Regarding Preferences in Cooperative-Competitive Environments}, author = {Ivanov, Dmitry and Egorov, Vladimir and Shpilman, Aleksei}, booktitle = {Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)}, pages = {Pages--1536}, year = {2021}, }
2020
- DEDPUL: Difference-of-Estimated-Densities-based Positive-Unlabeled LearningDmitry IvanovIn 19th IEEE International Conference on Machine Learning and Applications (ICMLA) , 2020
Positive-Unlabeled (PU) learning is an analog to supervised binary classification for the case when only the positive sample is clean, while the negative sample is contaminated with latent instances of positive class and hence can be considered as an unlabeled mixture. The objectives are to classify the unlabeled sample and train an unbiased PN classifier, which generally requires to identify the mixing proportions of positives and negatives first. Recently, unbiased risk estimation framework has achieved state-of-the-art performance in PU learning. This approach, however, exhibits two major bottlenecks. First, the mixing proportions are assumed to be identified, i.e. known in the domain or estimated with additional methods. Second, the approach relies on the classifier being a neural network. In this paper, we propose DEDPUL, a method that solves PU Learning without the aforementioned issues. The mechanism behind DEDPUL is to apply a computationally cheap post-processing procedure to the predictions of any classifier trained to distinguish positive and unlabeled data. Instead of assuming the proportions to be identified, DEDPUL estimates them alongside with classifying unlabeled sample. Experiments show that DEDPUL outperforms the current state-of-the-art in both proportion estimation and PU Classification.
@inproceedings{ivanov2020dedpul, title = {DEDPUL: Difference-of-Estimated-Densities-based Positive-Unlabeled Learning}, author = {Ivanov, Dmitry}, booktitle = {19th IEEE International Conference on Machine Learning and Applications (ICMLA)}, pages = {782--790}, year = {2020}, }
2019
- Identifying bid leakage in procurement auctions: Machine learning approachDmitry Ivanov , and Alexander NesterovIn Proceedings of the 2019 ACM Conference on Economics and Computation (EC) , 2019
Bid leakage is a corrupt scheme in a first-price sealed-bid auction in which the procurer leaks the opponents’ bids to a favoured participant. The rational behaviour of such participant is to bid close to the deadline in order to receive all bids, which allows him to ensure his win at the best price possible. While such behaviour does leave detectable traces in the data, the absence of bid leakage labels makes supervised classification impossible. Instead, we reduce the problem of the bid leakage detection to a positive-unlabeled classification. The key idea is to regard the losing participants as fair and the winners as possibly corrupted. This allows us to estimate the prior probability of bid leakage in the sample, as well as the posterior probability of bid leakage for each specific auction. We extract and analyze the data on 600,000 Russian procurement auctions between 2014 and 2018. We find that around 9% of the auctions are exposed to bid leakage, which results in an overall 1.5% price increase. The predicted probability of bid leakage is higher for auctions with a higher reserve price, with too low or too high number of participants, and if the winner has met the auctioneer in earlier auctions.
@inproceedings{ivanov2019identifying, title = {Identifying bid leakage in procurement auctions: Machine learning approach}, author = {Ivanov, Dmitry and Nesterov, Alexander}, booktitle = {Proceedings of the 2019 ACM Conference on Economics and Computation (EC)}, pages = {69--70}, year = {2019}, }