Model-Based Multi-agent Reinforcement Learning for AI Assistants - 2023

Given a Markov Decision Processes (MDPs), an optimal criterion OPT gives a preference ordering over policies. Combining an MDP with an optimality criterion results in a Markov decision problem.

Discounting has uses other than giving convergence in infinite-horizon problems.

Model-based RL aims to model the state transition dynamics \(p(\cdot|s,a)\) and reward function \(r(s,a)\) of the environment. Some methods blur the line - Deep Q-learning with experience replay can be thought of using stored state-transition data to learn an empirical model of the transition dynamics and reward function.

Bayesian model-based RL starts by placing a prior on \(p(\cdot|s,a)\) and sometimes over \(r(s,a)\) - a Bayes-adaptive MDP (BAMDP) is a model which once solved, gives us an optimal policy that balances exploration and exploitation. The BAMDP agent has a distribution over the transition dynamics \(P(p|h)\) - this results in an augmented transition dynamics \(p^+\) which uses \(P(p|h)\) to model the one-step transition probabilities (which were modelled by \(p(\cdot|s,a)\) in classical MDPs).

A Markov decision problem represents a decision-making tasks which when solved, gives a policy that achieves the optimality criterion, meanwhile BAMDPs represent a learning and decision-making task. (#ASK Model-based solutions to MDPs also involve simultaneous learning and decision-making right?).

The BAMDP agent only knows \(p^+\) but not the true transition dynamics \(p\). BAMDP states include posteriors over the dynamics, and computing Q-functions involves averaging over all possible future trajectories and the corresponding posterior updates - the resulting actions balance the learning and reward maximization objectives. Such policies are called Bayes-optimal.

Bayes-adaptive Monte Carlo Planning (BAMCP) is a sampled-based anytime planning algorithm for solving BAMDPs based on Monte-Carlo Tree Search (MCTS). It uses a sampling model (i.e. a simulator). It involves 2 procedures : search and simulate. In each step, a transition dynamics model is sampled \(\tilde{p}\sim P(p|h)\) and used to simulate transitions. Tree nodes are maintained for augmented states (which represent the current environment state and agents epistemic uncertainty over the environment dynamics). The sampling of \(\tilde{p}\) (called root sampling) is the only difference compared to normal MCTS. After this search procedure is terminated, each root node contains the estimation Q-function values (where the states are the augmented states). This is used to choose an action which is performed in the real environment and a real transition is observed, and the augmented state is updated accordingly.

In POMDPs, where only noise observations of the state from \(O(o|s,a)\) are observed, we maintain a state belief \(b(\cdot|h_t)\) which is a distribution over the state-space. Bayes-adaptive POMDPs (BAPOMDPs) hence do not observe states, meaning there are multiple models of the transition dynamics consistent with its history of action-observation pairs. The augmented state for BAPOMDPs now include a distribution over the transition dynamics and one over the observation probabilities. Note that we are not guaranteed to converge to the true transition probabilities even in the limit of infinite data.

In Bayes-adaptive Partially-observable Monte Carlo Planning (BAPOMCP) - the root sampling procedure samples an augmented sample state which now includes distributions over the transition dynamics and the observation probabilities.

In MARL, we should consider whether:

• Agents are independent and self-interested or not.
• The setting is general-sum (individual rewards are different but not orthogonal), zero-sum (competitive and orthogonal) or fully-cooperative (all agents have the same reward thus they should co-operate).

Partially-observable stochastic games (POSGs) generalize POMDPs to the multi-agent setting - where we now have separate action states, observation dynamics and reward functions for each of the \(N\) agents. The agents all interact with the same environment and thus there is 1 transition dynamics function, and this depends on the joint actions of all the agents. If an agent could prediction the behaviour of other agents, the POSG reduces to a POMDP.

In MARL, is no consensus on what a good optimality criterion is. We may take some solution concepts from game theory like the joint policy achieving a Nash equilibrium (which can be a poor choice). Game theoretic approaches are an objective perspective, meanwhile the subjective perspective looks at the multi-agent system from the perspective of the (protagonist) agent.

Bayesian Best-response models explicitly model the behaviour of agent \(-i\) (agents other than the protagonist agent \(i\)) - specifically by modelling the internal state \(I_{-i}\) and other parts of the model \(f_{-i}\) (called the frame of the agent) which are static.

(#TODO Continue from Contribution section onwards).