Timezone: »
Oral
Learning to Collaborate in Markov Decision Processes
Goran Radanovic · Rati Devidze · David Parkes · Adish Singla
We consider a twoagent MDP framework where agents repeatedly solve a task in a collaborative setting. We study the problem of designing a learning algorithm for the first agent (A1) that facilitates a successful collaboration even in cases when the second agent (A2) is adapting its policy in an unknown way. The key challenge in our setting is that the presence of the second agent leads to nonstationarity and nonobliviousness of rewards and transitions for the first agent.
We design novel online learning algorithms for agent A1 whose regret decays as $O(T^{1\frac{3}{7} \cdot \alpha})$ with $T$ learning episodes provided that the magnitude of agent A2's policy changes between any two consecutive episodes are upper bounded by $O(T^{\alpha})$. Here, the parameter $\alpha$ is assumed to be strictly greater than $0$, and we show that this assumption is necessary provided that the {\em learning parity with noise} problem is computationally hard. We show that sublinear regret of agent A1 further implies nearoptimality of the agents' joint return for MDPs that manifest the properties of a {\em smooth} game.
Author Information
Goran Radanovic (Harvard University)
Rati Devidze (Max Planck Institute for Software Systems)
David Parkes (Harvard University)
Adish Singla (Max Planck Institute (MPISWS))
Related Events (a corresponding poster, oral, or spotlight)

2019 Poster: Learning to Collaborate in Markov Decision Processes »
Wed Jun 12th 01:30  04:00 AM Room Pacific Ballroom
More from the Same Authors

2021 Poster: Learning Representations by Humans, for Humans »
Anna Hilgard · Nir Rosenfeld · Mahzarin Banaji · Jack Cao · David Parkes 
2021 Spotlight: Learning Representations by Humans, for Humans »
Anna Hilgard · Nir Rosenfeld · Mahzarin Banaji · Jack Cao · David Parkes 
2021 Workshop: HumanAI Collaboration in Sequential DecisionMaking »
Besmira Nushi · Adish Singla · Sebastian Tschiatschek 
2020 Poster: The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation »
Zhe Feng · David Parkes · Haifeng Xu 
2020 Poster: Adaptive RewardPoisoning Attacks against Reinforcement Learning »
Xuezhou Zhang · Yuzhe Ma · Adish Singla · Jerry Zhu 
2020 Poster: Policy Teaching via Environment Poisoning: Trainingtime Adversarial Attacks against Reinforcement Learning »
Amin Rakhsha · Goran Radanovic · Rati Devidze · Jerry Zhu · Adish Singla 
2019 Poster: Fairness without Harm: Decoupled Classifiers with Preference Guarantees »
Berk Ustun · Yang Liu · David Parkes 
2019 Oral: Fairness without Harm: Decoupled Classifiers with Preference Guarantees »
Berk Ustun · Yang Liu · David Parkes 
2019 Poster: Efficient learning of smooth probability functions from Bernoulli tests with guarantees »
Paul Rolland · Ali Kavis · Alexander Niklaus Immer · Adish Singla · Volkan Cevher 
2019 Oral: Efficient learning of smooth probability functions from Bernoulli tests with guarantees »
Paul Rolland · Ali Kavis · Alexander Niklaus Immer · Adish Singla · Volkan Cevher 
2019 Poster: Optimal Auctions through Deep Learning »
Paul Duetting · Zhe Feng · Harikrishna Narasimhan · David Parkes · Sai Srivatsa Ravindranath 
2019 Oral: Optimal Auctions through Deep Learning »
Paul Duetting · Zhe Feng · Harikrishna Narasimhan · David Parkes · Sai Srivatsa Ravindranath