2
$\begingroup$

I have three question about three algorithms.

I have a game with $n$ players. The action space of player $i$ is given by $\mathcal{A}_i=\{a_1, a_2, \cdots, a_m\}=\mathcal{A}$. The joint action space is hence $\mathcal{A}^n$.

1) I have an algorithm which I think called reinforcement learning (RL). RL plays the game in repeated play at time $t=0,1,\cdots$ as follow:

  • For time $t\geqslant0$:
    • Player $n$ play a random strategy from $\mathcal{A}$ (say action $a_i$) with uniform probability $\pi_i^t$. The probability vector is given by $\hat \pi^t=(\pi_1^t, \cdots, \pi_m^t)$.
    • If player $n$ is satisfied with its payoff then update the probability as follow:
    • $\pi_i=\pi_i+\epsilon(1-\pi_i)$ (Increase the winning action's chance).
    • $\pi_j=\pi_j-\epsilon\pi_j\;\forall\,j\in\{1,\cdots,m\}\backslash\{i\}$ (Decrease the losing actions' chances).

Is this algorithm known? Where did it converges? Correlated equilibrium (CE)? Nash equilibrium (NE)?

2) Also Fictitious play algorithm, did it converge to NE?

3) What about Trial and error algorithm?

I know that No regret matching algorithm converges to a CE but what about the previous two?

I would like to get some help, good references.

$\endgroup$
2
$\begingroup$

The reward obtained by player $i$ depends on the actions that were taken by other players as well. Therefore just increasing the probability of the action of $i$ which gave a satisfactory reward does not capture the spirit of the game. The same action would give lower reward if other players used other actions, or other distributions over their actions.

Also have to define what is meant by satisfactory. With compared to what is it satisfactory?

If it was just a single agent trying to learn the better actions; i.e. all the other players are part of the environment and they are always playing a stationary distribution over their actions, then you can simply explore the long run reward of each action and chose the best action for the player. But this won't be a Nash Equ, as other players are not playing their best response.

| cite | improve this answer | |
$\endgroup$

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.