2025-11-15T23:58:12.055440

An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs

Liu, Wei, Zimmert
We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coefficient (DEC), but left a gap between the regret upper and lower bounds that scales with the size of the model class. To tighten this gap, Foster et al. (2023b) introduced optimistic DEC, achieving a bound that scales only with the size of the value-function class. However, their optimism-based exploration is only known to handle the stochastic setting, and it remains unclear whether it extends to the adversarial setting. We introduce Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than optimistic DEC and can be much smaller in special cases. Importantly, the removal of optimism allows it to handle adversarial environments without explicit reward estimators. By applying Dig-DEC to hybrid MDPs with stochastic transitions and adversarial rewards, we obtain the first model-free regret bounds for hybrid MDPs with bandit feedback under several general transition structures, resolving the main open problem left by Liu et al. (2025). We also improve the online function-estimation procedure in model-free learning: For average estimation error minimization, we refine the estimator in Foster et al. (2023b) to achieve sharper concentration, improving their regret bounds from $T^{3/4}$ to $T^{2/3}$ (on-policy) and from $T^{5/6}$ to $T^{7/9}$ (off-policy). For squared error minimization in Bellman-complete MDPs, we redesign their two-timescale procedure, improving the regret bound from $T^{2/3}$ to $\sqrt{T}$. This is the first time a DEC-based method achieves performance matching that of optimism-based approaches (Jin et al., 2021; Xie et al., 2023) in Bellman-complete MDPs.
academic

Un Coefficient de Décision-Estimation Amélioré sans Modèle avec Applications aux MDP Adversariels

Informations de Base

  • ID de l'article: 2510.08882
  • Titre: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
  • Auteurs: Haolin Liu (University of Virginia), Chen-Yu Wei (University of Virginia), Julian Zimmert (Google Research)
  • Classification: cs.LG (Apprentissage Automatique)
  • Date de publication: Octobre 2025
  • Lien de l'article: https://arxiv.org/abs/2510.08882v1

Résumé

Cet article étudie le problème de la prise de décision avec observations structurées (DMSO). Les travaux antérieurs ont caractérisé la complexité du DMSO par le coefficient de décision-estimation (DEC), mais ont laissé un écart entre les bornes supérieures et inférieures du regret lié à la taille de la classe de modèles. Foster et al. (2023b) ont introduit le DEC optimiste pour réduire cet écart, en obtenant des bornes dépendant uniquement de la taille de la classe de fonctions de valeur. Cependant, l'exploration basée sur l'optimisme ne peut traiter que les environnements stochastiques, et il n'est pas clair si elle peut s'étendre aux environnements adversariels.

Cet article propose Dig-DEC, une méthode DEC sans modèle qui supprime l'optimisme et pilote l'exploration uniquement par le gain d'information. Dig-DEC est toujours inférieur ou égal au DEC optimiste et peut être significativement plus petit dans certains cas. Surtout, la suppression de l'optimisme permet de traiter les environnements adversariels sans estimateur de récompense explicite. En appliquant Dig-DEC aux MDP hybrides avec transitions stochastiques et récompenses adversarielles, nous obtenons les premières bornes de regret sans modèle pour les MDP hybrides avec retours bandit dans diverses structures de transitions générales.

Contexte et Motivation de la Recherche

  1. Problème à résoudre: Le cadre existant du coefficient de décision-estimation (DEC) présente un écart entre la taille de la classe de modèles et la taille de la classe de fonctions de valeur, et les méthodes basées sur l'optimisme ne peuvent pas traiter efficacement les environnements adversariels.
  2. Importance du problème:
    • La prise de décision en ligne est un problème fondamental de l'apprentissage par renforcement
    • Les applications pratiques font souvent face à des environnements hybrides partiellement stochastiques et partiellement adversariels
    • Il existe un écart entre les garanties théoriques et les performances pratiques des méthodes existantes
  3. Limitations des méthodes existantes:
    • Le modèle de Foster et al. basé sur DEC/E2D doit supporter le coût d'estimation du modèle log|M|
    • Bien que le DEC optimiste améliore la complexité, il dépend du principe d'optimisme et ne peut pas traiter les paramètres adversariels
    • La méthode MDP hybride de Liu et al. (2025) ne peut traiter que les retours d'information complète, le cas bandit reste un problème ouvert
  4. Motivation de la recherche: Développer un cadre unifié qui améliore les résultats existants dans les environnements stochastiques et traite pour la première fois le cas des retours bandit pour les MDP hybrides.

Contributions Principales

  1. Proposition de la mesure de complexité Dig-DEC: Introduction du coefficient de décision-estimation à double gain d'information, suppression de l'optimisme, pilotage de l'exploration uniquement par le gain d'information
  2. Cadre théorique unifié: Construction d'un cadre algorithmique générique capable de traiter simultanément les environnements stochastiques et hybrides
  3. Amélioration de l'estimation de fonction en ligne:
    • Erreur d'estimation moyenne: améliorée de T^{3/4}/T^{5/6} à T^{2/3}/T^{7/9}
    • Erreur quadratique: améliorée de T^{2/3} à √T, atteignant pour la première fois dans les MDP Bellman-complets les mêmes performances que les méthodes optimistes
  4. Résolution d'un problème ouvert: Première borne de regret sans modèle pour les MDP hybrides avec retours bandit

Explication Détaillée de la Méthode

Définition de la Tâche

Cadre DMSO: Étant donné un espace de modèles M, un espace de stratégies Π, un espace d'observations O et une classe de fonctions de valeur V. À chaque tour t:

  • L'environnement choisit un modèle Mt ∈ M
  • L'apprenant choisit une stratégie πt ∈ Π
  • Observation ot ~ Mt(·|πt)
  • Objectif: minimiser le regret Reg(π*) = Σt(VMt(π*) - VMt(πt))

Environnement Φ-restreint: Partition de M×Π par des ensembles d'information Φ, où chaque ensemble d'information ϕ contient une stratégie unique πϕ.

Architecture du Modèle

1. Cadre Générique (Algorithme 1)

L'idée centrale est de résoudre le problème de point-selle suivant:

min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} AIR^{Φ,D}_η(p,ν;ρt)

où la mesure de divergence est:

D^π(ν||ρ) = E_{M~ν}E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ) + E_{ϕ~ρ}[D^π(ϕ||M)]]

2. Définition de Dig-DEC

dig-dec^{Φ,D}_η = max_{ρ∈Δ(Φ)} min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} 
E_{π~p}E_{(M,π*)~ν}[V_M(π*) - V_M(π) - (1/η)E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ)] - (1/η)E_{ϕ~ρ}[D^π(ϕ||M)]]

3. Mécanisme de Mise à Jour Postérieure

Selon le choix de D:

  • Erreur d'estimation moyenne: Utilisation d'un algorithme par lots (Algorithme 2)
  • Erreur d'estimation quadratique: Utilisation d'un algorithme d'apprentissage à deux niveaux (Algorithme 3)

Points d'Innovation Technique

  1. Conception du Double Gain d'Information:
    • Le terme KL pour la régularisation, évitant le mécanisme d'optimisme
    • Le terme D^π pour capturer les différences de distribution, réalisant une amélioration stricte
  2. Suppression de l'Optimisme: Remplacement du terme V_ϕ(π_ϕ) du DEC optimiste par le terme de régularisation KL(ν_{ϕ}, ρ)
  3. Procédures d'Estimation Améliorées:
    • Erreur moyenne: utilisation d'estimateurs sans biais remplaçant les estimateurs biaisés
    • Erreur quadratique: reprogrammation de la procédure à deux échelles de temps, amélioration de la borne Est de T^{1/3} à une constante

Configuration Expérimentale

Environnements de Vérification Théorique

  1. Paramètre stochastique:
    • MDP de classe bilinéaire
    • MDP avec dimension d'éluder de Bellman bornée
    • MDP avec couverture bornée
  2. Paramètre hybride:
    • Classe bilinéaire hybride
    • MDP de couverture hybride
    • Caractéristiques de récompense linéaire connues

Indicateurs d'Évaluation

  • Borne de regret: Borne supérieure de EReg(π*)
  • Comparaison de complexité: dig-dec vs o-dec vs DEC classique
  • Taux de convergence: Dépendance en puissance de T

Méthodes de Comparaison

  • DEC optimiste de Foster et al. (2023b)
  • Cadre AIR de Liu et al. (2025)
  • Méthodes optimistes classiques (Jin et al. 2021, Xie et al. 2023)

Résultats Expérimentaux

Résultats Principaux

Améliorations en Environnement Stochastique (Tableau 1):

Catégorie de ParamètreFoster et al. (2023b)Méthode Proposée
Bilinéaire/BE (erreur moyenne)T^{3/4}/T^{5/6}T^{2/3}/T^{7/9}
Bellman-complet (erreur quadratique)T^{2/3}√T

Percée en Environnement Hybride (Tableau 2):

Catégorie de ParamètreLiu et al. (2025)Méthode Proposée
Bilinéaire (erreur moyenne)Information complète uniquementT^{5/6}/T^{13/15}
Bellman-complet (erreur quadratique)Non applicableT^{3/4}

Vérification des Avantages Théoriques

Théorème 13: Dans le paramètre stochastique, dig-dec^{Φ,D}_η ≤ o-dec^{Φ,D}_η + η

Théorème 14: Construction d'une instance de bandit à trois bras, prouvant qu'il existe des cas où:

  • Méthode de Foster et al.: EReg(a) ≥ Ω(√T)
  • Méthode proposée: EReg(a) ≤ 1

Découvertes Expérimentales

  1. Importance du gain d'information: Le terme KL capture les informations de distribution ignorées par le DEC optimiste
  2. Amélioration de la procédure d'estimation: Les estimateurs sans biais améliorent significativement l'effet des inégalités de concentration
  3. Avantages de la suppression de l'optimisme: Permet à l'algorithme de s'étendre naturellement aux environnements adversariels

Travaux Connexes

Directions de Recherche Principales

  1. Développement du Cadre DEC:
    • Foster et al. (2021b, 2023a): Établissement de la théorie DEC fondamentale
    • Foster et al. (2023b): Introduction du DEC optimiste
    • Chen et al. (2025): Extension à d'autres paramètres
  2. Recherche sur les MDP Adversariels:
    • Neu et al. (2013): MDP adversariels tabulaires
    • Luo et al. (2021): MDP adversariels linéaires
    • Liu et al. (2025): Théorie des MDP hybrides
  3. Apprentissage par Renforcement sans Modèle:
    • Jin et al. (2021): Dimension d'éluder de Bellman
    • Xie et al. (2023): Théorie de la couverture

Avantages de Cet Article

  1. Unification théorique: Premier cadre DEC traitant simultanément les environnements stochastiques et hybrides
  2. Innovation technique: Conception du double gain d'information, suppression de la dépendance à l'optimisme
  3. Résolution de problèmes: Résolution du problème ouvert laissé par Liu et al. (2025)

Conclusion et Discussion

Conclusions Principales

  1. Dig-DEC fournit une caractérisation de complexité plus précise, permettant des améliorations arbitrairement grandes dans certains cas
  2. La suppression de l'optimisme permet à l'algorithme de traiter naturellement les environnements adversariels
  3. La procédure d'estimation améliorée a une importance théorique et pratique

Limitations

  1. Restrictions d'hypothèses: Le paramètre hybride nécessite des caractéristiques de récompense linéaire connues (Hypothèse 4)
  2. Contraintes techniques: Certains cas de MDP de faible rang ne peuvent toujours pas être traités
  3. Complexité de calcul: L'efficacité de calcul pratique de l'optimisation de point-selle n'est pas discutée en détail

Directions Futures

  1. Relâcher les restrictions des Hypothèses 3 et 4
  2. Étudier les limites fondamentales de l'apprentissage sans modèle
  3. Développer des algorithmes de calcul plus efficaces

Évaluation Approfondie

Points Forts

  1. Contributions Théoriques Significatives:
    • Proposition d'une nouvelle mesure de complexité dig-dec
    • Traitement unifié des environnements stochastiques et adversariels
    • Résolution d'un problème ouvert important
  2. Innovation Technique Forte:
    • Conception du double gain d'information ingénieuse
    • Amélioration efficace de la procédure d'estimation
    • Techniques d'analyse avancées
  3. Résultats Convaincants:
    • Bornes théoriques serrées et pratiques
    • Construction d'instances prouvant des améliorations strictes
    • Couverture de plusieurs classes de MDP classiques

Insuffisances

  1. Vérification Expérimentale Limitée: Principalement une analyse théorique, manque d'implémentation d'algorithmes réels et de vérification empirique
  2. Portée d'Application Restreinte: Les hypothèses sur les MDP hybrides sont fortes, limitant la généralité de la méthode
  3. Complexité de Calcul: La solvabilité pratique et l'efficacité de l'optimisation de point-selle nécessitent une recherche supplémentaire

Impact

  1. Valeur Théorique: Fournit une nouvelle direction pour le développement de la théorie DEC, pouvant inspirer les recherches ultérieures
  2. Potentiel Pratique: Fournit des orientations théoriques pour la conception d'algorithmes d'apprentissage par renforcement pratiques
  3. Avancement du Domaine: Percée dans le domaine d'intersection de l'apprentissage sans modèle et des MDP adversariels

Scénarios Applicables

  1. Recherche Théorique: Extension du cadre DEC, analyse de complexité
  2. Conception d'Algorithmes: Algorithmes d'apprentissage par renforcement nécessitant de traiter des environnements hybrides
  3. Domaines d'Application: Trading financier, systèmes de recommandation et autres environnements partiellement adversariels

Références

Les références clés incluent:

  • Foster et al. (2021b, 2023a, 2023b): Fondements de la théorie DEC
  • Liu et al. (2025): Recherche sur les MDP hybrides
  • Jin et al. (2021): Dimension d'éluder de Bellman
  • Xie et al. (2023): Théorie de la couverture
  • Xu and Zeevi (2023): Cadre AIR

Cet article a réalisé des progrès importants dans la théorie du coefficient de décision-estimation, résolvant des problèmes clés du domaine par des innovations techniques ingénieuses, et apportant une contribution précieuse au développement de la théorie de l'apprentissage par renforcement. Bien qu'il y ait de la place pour l'amélioration dans la vérification des applications pratiques, sa valeur théorique et son caractère innovant en font un travail important dans ce domaine.