2
$\begingroup$

Imagine we have a two player game with some sort of sparse reward (few actions are rewarded over the course of a game). My understanding is that ordinarily, the reward administered to actions would decrease by discount factor $\gamma$ each timestep as $t_\text{from reward}$ increases.

If we were attempting to learn a policy for a two player turn-based game (such as tic-tac-toe), a generally accepted strategy seems to be inverting the environment every other move such that the agent is always playing from the same perspective. However, if we naively administered reward for the agent's actions by our previous policy, we would end up rewarding self-destructive behavior of the agent every other timestep. Thus, it would make sense to me to give alternatingly negative reward.

Is it common practice to achieve this behavior by assigning a negative discount factor $\gamma$? Although this would make sense to me, I haven't seen examples where $\gamma < 0$ in published literature. Alternatively, is there a better way to set up the environment for these sorts of games such that we can still administer rewards as we would for single player games? Thank you.

$\endgroup$
1
  • $\begingroup$ Interesting problem. Please, tell us what RL algorithm you consider. $\endgroup$ – Karel Macek Sep 22 '17 at 7:33
1
$\begingroup$

In a simple two-player zero-sum game (i.e. my win is your loss and vice-versa), then there is no need to alter the model, just the action selection. If you have Player A and Player B, arbitrarily decide that your reward function is positive for Player A. Then any estimate of total return (all rewards summed, aka "utility") for Player B is just the negative of the estimate for Player A. So you can share one state value model between the players.

The only thing you need to "invert" between players is when making action choice. Player A should choose the action that maximises the reward. Player B should choose the action that minimises it, and can use the same estimates from the same model to do so. This is called minimax, and is used in game playing algorithms even without RL - for instance it might be used based on some expert-provided heuristic, and is a commonly used concept in game theory. You can think of RL in this context as attempting to learn the best heuristic estimates for each game state, based on learning from experience.

A negative discount factor would not achieve similar results - I'm not entirely sure what it would do, but it could well make the learning process fail. Most two player games are episodic with reward only considered at end of the episode (a win, draw or loss), in which case discounting is not much use anyway.

$\endgroup$
0

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.