2
$\begingroup$

I have the following situation. An agent plays a game and wants to maximize the accumulated reward as usual, but it can choose its adversary. There are $n$ adversaries.

In episode $e$, the agent must first select an adversary. Then for each step $t$ in the episode $e$, it plays the game against the chosen adversary. Every step $t$, it receives a reward following the chosen action in step $t$ (for the chosen adversary). How to maximize the expected rewards using DQN? It is clear that choosing the "wrong" (the strongest) adversary won't be a good choice for the agent. Thus, to maximize the accumulated rewards, the agent must take two actions at two different timescales.

I started solving it using two DQNs, one to decide the adversary to play against and one to play the game against the chosen adversary. I have two duplicate hyperparameters (batch_size, target_update_freq, etc), one for each DQN. Have you ever seen two DQNs like this? Should I train the DQNs simultaneously?

The results that I am getting is not that good. The accumulated reward is decreasing, the loss isn't always decreasing...

$\endgroup$
  • 1
    $\begingroup$ Are episodes in any way connected so that a series of episodes form a "meta-episode" with clear time sequence, consequences for picking a particular opponent in episode 1 as opposed to episode 3, and an accumulation of reward over multiple episodes that matters (e.g. winning a series of games)? $\endgroup$ – Neil Slater Jun 20 at 8:31
  • $\begingroup$ I think they should be connected right? but I don't know how. Right now in my modeling, once I choose an adversary and play against it, I see the reward and move to the next episode by resetting the environment. Should I count the number of times I won against an adversary as a meta-episode or something? $\endgroup$ – zdm Jun 20 at 13:27
  • 1
    $\begingroup$ It depends what your goal is. Is there any larger structure in the game other than an episode? Does the choice of opponent have any other effect than influencing the results of an individual episode? For instance, does it affect the list of opponents possible for the next episode? If not, then perhaps there is no connection and the answer will be different. That is why I am checking in comments for clarification $\endgroup$ – Neil Slater Jun 20 at 13:31
  • 1
    $\begingroup$ Yes, right now I am thinking of no connection. I thought of playing it with $n$ independent DQNs---one for each adversary---and then select the one with the best reward. But this does not work for large $n$. $\endgroup$ – zdm Jun 20 at 14:17
3
$\begingroup$

From comments, you say there is no "outer" goal for picking an adversary other than scoring highly in an individual episode.

You could potentially model the initial adversary choice as a partially separate Markov Decision Process (MDP), where choosing the opponent is a single-step episode with return equal to whatever reward the secondary MDP - which played the game - obtains. However, this "outer" MDP is not much of an MDP at all, it is more like a contextual bandit. In addition, the performance of the inner game-playing agent will vary both with the choice of opponent, and over time as it learns to play better against each opponent. This makes the outer MDP non-stationary. It also requires the inner MDP to know what opponent it is facing in order to correctly predict correct choices and/or future rewards.

That last part - the need for any "inner" agent to be aware of the opponent it is playing against - is likely to be necessary whatever structure you chooose. That choice of opponent needs to be part of the state for this inner agent, because it will have an impact on likely future rewards. A characterisation of the opponents also needs to be part of whatever predictive models you could use for the outer agent.

A more natural, and probably more useful, MDP model for your problem is to have a single MDP where the first action $a_0$ is to select the opponent. This matches the language you use to describe the problem, and resolves your issue about trying to run a hierarchy of agents. Hierarchical reinforcement learning is a real thing, and very interesting for solving problems which can be broken down into meaningful sub-goals that an agent could discover autonomously, but it does not appear to apply for your problem.

This leaves you with a practical problem of creating a model that can switch between choosing between two sets of radically different actions. The select an opponent action only occurs at the first state of the game, and the two sets of actions do not overlap at all. However, in terms of the theoretical MDP model this is not an issue at all. It is only a practical issue of how you get to fit your Q function approximator to the two radically different action types. There a a few ways around that. Here are a couple that might work for you:

One shared network

Always predict for all kinds of action choice, so the agent still makes predictions for switching opponents all the way to the end of the game. Then filter the action choices down to only those available at any time step. When $t=0$ only use the predictions for actions for selecting an opponent, for $t \ge 1$ only use predictions relating to moves in the game.

Two separate approximators

Have two function approximators in your agent, use one for predicting reward at $t=0$ that covers different opponent choices, and use the other for the rest of the game. If $n$ is small and there is no generalisation between opponents (i.e. no opponent "stats" that give some kind of clue towards the end results), then for the first approximator, you could even use a Q table.

For update steps you need to know whether any particular action value was modelled in one or other of the Q functions - and this will naturally lead you to bootstrap

$$\hat{q}_{o}(s_0, a_0, \theta_0) \leftarrow r_1 + \gamma \text{max}_{a'}\hat{q}_{p}(s_1, a', \theta_1)$$

where $\hat{q}_{o}$ is your approximate model for action values of selecting opponents (and $a_0$ must be an opponent choice) at the start of the game, and $\hat{q}_{p}$ is the nodel you use for the rest of it (and $a'$ must be a position play in the game). I've misused $\leftarrow$ here to stand in for whatever process used to update the action value towards the new estimate - a tabular method that would be a rolling average with current estimate, in neural networks of course that is gradient descent using backpropagation.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I fully agree with your first three paragraphs, but not sure about the rest. Yeah, that could work, but I feel like completely separating the problems would work better; treat the opponent selection as a MAB, and the playing as an MDP. Inside the MDP, you could augment the state representation to include a one-hot vector to represent the opponent, or even some other kind of representation if meaningful features are available that could allow for generalisation across similar opponents. Treating everything as a single MDP would just exacerbate the credit assignment problem? $\endgroup$ – Dennis Soemers Jun 21 at 12:12
  • $\begingroup$ @DennisSoemers: "Treating everything as a single MDP would just exacerbate the credit assignment problem?" I don't think so. That issue is a core part of the problem definition and would either appear as "credit assignment" in a single MDP view or high variance and non-stationarity in a two MDP view. In terms of number of samples required, and the values passing between steps for value updates, the two views (single MDP with differing action spaces vs two MDPs) are practically identical. $\endgroup$ – Neil Slater Jun 21 at 14:26
  • $\begingroup$ Say I use MAB to select opponents. Should I do (1) or (2)? Here is (1): in each round of the MAB, I select an opponent, and train the DQN (given the chosen opponent). After training, I get the best reward from the trained DQN, and update MAB probabilities and go to the next round of the MAB. Here is (2): in each round of the MAB, I select an opponent, and play one episode of the DQN (given the chosen opponent). After the terminal state is reached, I get the reward, and update MAB probabilities and go to the next round. $\endgroup$ – zdm Jul 3 at 21:11
  • $\begingroup$ @zdm: If you are able to do this as an experiemnt, then you can test your idea. If you want some theoretical or practical advice from an expert then I think that you should ask a new question on the site. On a short think through, with (1) you will need to train N DQNs (one for each opponent) in sequence and keep them. It may be more reliable than (2) in the long term, but (2) may find your best initial choice earlier and require a lot less training as it will start to focus on the probably best opponents before needing to fully converge. $\endgroup$ – Neil Slater Jul 4 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.