Sur l'optimalité des algorithmes d'optimisation des politiques par lots

Résumé :

L'optimisation des politiques par lots consiste à exploiter les données existantes pour construire des politiques avant d'interagir avec un environnement. Bien que l'intérêt pour ce problème se soit considérablement accru au cours des dernières années, ses fondements théoriques restent sous-développés. Pour faire progresser la compréhension de ce problème, nous fournissons trois résultats qui caractérisent les limites et les possibilités de l'optimisation des politiques par lots dans le cadre du bandit stochastique à bras finis. Tout d'abord, nous introduisons une classe d'algorithmes d'indexation ajustés à la confiance qui unifie les principes optimistes et pessimistes dans un cadre commun, ce qui permet une analyse générale. Pour cette famille, nous montrons que tout algorithme d'indice ajusté en fonction de la confiance est optimal minimax, qu'il soit optimiste, pessimiste ou neutre. Notre analyse révèle que l'optimalité dépendante de l'instance, couramment utilisée pour établir l'optimalité des algorithmes de bandit stochastique en ligne, ne peut être atteinte par aucun algorithme dans le cadre du traitement par lots. En particulier, pour tout algorithme qui fonctionne de manière optimale dans un certain environnement, il existe un autre environnement où le même algorithme souffre d'un regret arbitrairement plus grand. Par conséquent, pour établir un cadre permettant de distinguer les algorithmes, nous introduisons un nouveau critère de minimax pondéré qui tient compte de la difficulté inhérente à la prédiction de la valeur optimale. Nous démontrons comment ce critère peut être utilisé pour justifier les principes pessimistes couramment utilisés pour l'optimisation des politiques de lots.