Apprentissage par renforcement épisodique dans les MDPs finis : Les limites inférieures de Minimax revisitées.

Résumé Dans cet article, nous proposons de nouvelles bornes inférieures indépendantes du problème sur la complexité d'échantillonnage et le regret dans les MDPs épisodiques, avec un accent particulier sur le cas non-stationnaire dans lequel le noyau de transition est autorisé à changer à chaque étape de l'épisode. Notre principale contribution est une borne inférieure de Ω((H 3 SA/ε 2) log(1/δ)) sur la complexité d'échantillonnage d'un algorithme (ε, δ)-PAC pour l'identification de la meilleure politique dans un MDP non-stationnaire, en s'appuyant sur une construction de "MDPs durs" qui est différente de celles utilisées précédemment dans la littérature. En utilisant cette même classe de MDPs, nous fournissons également une preuve rigoureuse de la borne de regret Ω(√ H 3 SAT) pour les MDPs non-stationnaires. Enfin, nous discutons des liens avec les bornes inférieures de PAC-MDP.