Complexité des jeux d'informations partielles à états finis

Étant donné un jeu déterministe à somme partielle et à informations partielles avec seulement un nombre fini d'états,
dont les résultats possibles sont [perdre, dessiner, gagner] avec des valeurs [-1,0, + 1] respectivement,
quelle est la complexité de l'approximation de la valeur de tels un jeu additivement dans ?$\epsilon$

En particulier, je ne peux trouver aucun algorithme pour le faire.
Le reste de cet article est entièrement consacré à donner une description plus approfondie
du problème, donc si vous pouvez déjà comprendre ce que signifie la question en haut
de cet article, il n'y a aucune raison pour que vous lisiez le reste de cet article.

Compte tenu d' une machine arbitre avec les états , avec un état initial désigné s 0 , un état s a dont la paire de scores est [ - 1 , + 1 ] , un état s b dont la paire de scores est [ + 1 , - 1 ] , et des états de la forme$\{1,2,3,...,S\}$$s_0$$s_a$$[-1,+1]$$s_b$$[+1,-1]$

où:$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$

• $\mbox{player_to_move} \in \{1,2\}$
• est une fonction de { 1 , 2 , 3 , . . . , Num_of_choices } → { 1 , 2 , 3 , . . . , S $\mbox{next_state_table}$$\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
• $\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

Lorsque la machine est dans cet état:

• envoie à Player_1 et envoie p2_info à Player_2,$\mbox{p1_info}$$\mbox{p2_info}$
• $\mbox{num_of_choices}$$\{1,2,3,...,\mbox{num_of_choices}\}$
• $\mbox{next_state_table}$

$s_a$$s_b$

• s'arrête avec la paire de scores de cet état comme sortie

$s_0 = 1$

Quelle est la complexité du problème suivant?
Étant donné une telle machine d'arbitre et un entier positif N, émettez un nombre rationnel
qui est (additivement) à 1 / N de la valeur du jeu naturel pour le joueur 1.

Comme mentionné précédemment dans cette question, je ne peux trouver
aucun algorithme pour le faire.

REMARQUE: mon prétendu algorithme était incorrect; Je l'ai effacé.

$p$$p$

Pour une limite inférieure de la complexité, la question du rapprochement de la valeur d'un jeu stochastique simple , est pas connu pour être dans P . En utilisant l'astuce de randomisation que j'ai donnée ci-dessus, il est facile d'écrire un jeu stochastique simple comme un jeu arbitré avec une table de recherche de taille polynomiale.

$\epsilon$$0<\epsilon$

Entrée: un jeu tel que décrit dans ma question
doit afficher OUI si: la valeur du jeu pour le joueur 1 est supérieure à 1$\hspace{.025 in}\epsilon$
$\epsilon$

reste RE- dur même lorsque

player_to_move vaut toujours 1 (c'est-à-dire qu'un seul joueur est nécessaire)
et
s ₀ ≠ s _a et s _a n'est pas dans la plage (next_state_table)
(c'est-à-dire qu'il est littéralement impossible pour le joueur de perdre)
et
p1_info et p2_info et number_of_choices sont indépendants de l'état
(c.-à-d. que la seule rétroaction du joueur est de savoir s'il vient de gagner ou non)

.