Learning To Collaborate In Markov Decision Processes

Abstract

We consider a two-agent 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 first agent faces non-stationarity in rewards and transitions because of the adaptive behavior of the second agent. We design novel online learning algorithms for agent A1 whose regret decays as \(O(T^\{\max\\{1-\frac\{3\}\{7\} \cdot \alpha, \frac\{1\}\{4\}\\}\})\) 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 learning parity with noise problem is computationally hard. We show th

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyradanovic2019learning

Related papers

• Efficient Policy Learning For Non-stationary Mdps Under Adversarial Manipulation (2019)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Learning To Switch Among Agents In A Team Via 2-layer Markov Decision Processes (2020)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Online Convex Optimization In Adversarial Markov Decision Processes (2019)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Online Learning In Unknown Markov Games (2020)0.00
• Interactive Inverse Reinforcement Learning For Cooperative Games (2021)0.00