Apprendre avec de bonnes représentations de caractéristiques dans les bandits et dans le RL avec un modèle génératif

La construction de Du et al. (2019) implique que même si un apprenant reçoit des caractéristiques linéaires dans ℝd qui approchent les récompenses dans un bandit avec une erreur uniforme de ϵ, alors la recherche d'une action qui est optimale jusqu'à O(ϵ) nécessite d'examiner essentiellement toutes les actions. Nous utilisons le théorème de Kiefer-Wolfowitz pour prouver un résultat positif selon lequel en vérifiant seulement quelques actions, un apprenant peut toujours trouver une action qui est sous-optimale avec une erreur d'au plus O(ϵ√d). Ainsi, les caractéristiques sont utiles lorsque l'erreur d'approximation est faible par rapport à la dimensionnalité des caractéristiques. L'idée est appliquée aux bandits stochastiques et à l'apprentissage par renforcement avec un modèle génératif où l'apprenant a accès à des caractéristiques linéaires à d dimensions qui approximent les fonctions action-valeur pour toutes les politiques avec une précision de ϵ. Pour les bandits linéaires, nous prouvons une borne sur le regret d'ordre √dn log(k)+ϵn√d log(n) avec k le nombre d'actions et n l'horizon. Pour RL, nous montrons que l'itération approximative de la politique peut apprendre une politique qui est optimale jusqu'à une erreur additive d'ordre ϵ√d/(1-γ)^2 et en utilisant d/(ϵ^2(1-γ)^4) échantillons d'un modèle génératif. Ces limites sont indépendantes des détails plus fins des caractéristiques. Nous étudions également l'impact de la structure de l'ensemble des caractéristiques sur le compromis entre la complexité de l'échantillon et l'erreur d'estimation.