Suchergebnisse

Nous considérons le problème du contrôle optimal actualisé à horizon infini formalisé dans le cadre des processus de décision Markoviens. Nous nous focalisons sur plusieurs variations approchées du schéma itération sur les politiques: itérations sur les politiques approché (API), itérations sur les politiques conservatif (CPI), une adaptation naturelle de l'algorithme ''Policy Search by Dynamic Programming'' au cas de l'horizon infini (PSDP), et itérations sur les politiques non-stationnaires (NSPI). Pour tous ces algorithmes, nous décrivons des bornes de performance en fonction de l'erreur $\epsilon$ à chaque itération, et faisons une comparaison en portant une attention particulière aux coefficients de concentration impliqués, au nombre d'itérations et à la mémoire requis. Notre analyse souligne plusieurs points: 1) Les garanties de performance de CPI peuvent être arbitrairement meilleures que celle d'API, mais au prix d'une augmentation---exponentielle en $\frac{1}{\epsilon}$---du nombre d'itérations. 2) PSDP combine les avantages d'API et CPI: sa garantie de performance est similaire à celle de CPI, et elle est obtenue en un nombre d'itérations identique à celui d'API. 3) Contrairement à API qui requiert une mémoire constante, la mémoire dont CPI et PSDP ont besoin est proportionnelle au nombre d'itérations, ce qui peut être problématique lorsque le facteur d'actualisation $\gamma$ est proche de 1 ou lorsque l'erreur d'approximation $\epsilon$ est proche de 0; nous montrons que l'algorithme NSPI permet de faire un compromis entre la bonne mémoire d'API et la meilleure performance de PSDP. Enfin, des simulations numériques de ces schémas algorithmiques confirment notre analyse.

Nous considérons le problème du contrôle optimal actualisé à horizon infini formalisé dans le cadre des processus de décision Markoviens. Nous nous focalisons sur plusieurs variations approchées du schéma itération sur les politiques: itérations sur les politiques approché (API), itérations sur les politiques conservatif (CPI), une adaptation naturelle de l'algorithme ''Policy Search by Dynamic Programming'' au cas de l'horizon infini (PSDP), et itérations sur les politiques non-stationnaires (NSPI). Pour tous ces algorithmes, nous décrivons des bornes de performance en fonction de l'erreur $\epsilon$ à chaque itération, et faisons une comparaison en portant une attention particulière aux coefficients de concentration impliqués, au nombre d'itérations et à la mémoire requis. Notre analyse souligne plusieurs points: 1) Les garanties de performance de CPI peuvent être arbitrairement meilleures que celle d'API, mais au prix d'une augmentation---exponentielle en $\frac{1}{\epsilon}$---du nombre d'itérations. 2) PSDP combine les avantages d'API et CPI: sa garantie de performance est similaire à celle de CPI, et elle est obtenue en un nombre d'itérations identique à celui d'API. 3) Contrairement à API qui requiert une mémoire constante, la mémoire dont CPI et PSDP ont besoin est proportionnelle au nombre d'itérations, ce qui peut être problématique lorsque le facteur d'actualisation $\gamma$ est proche de 1 ou lorsque l'erreur d'approximation $\epsilon$ est proche de 0; nous montrons que l'algorithme NSPI permet de faire un compromis entre la bonne mémoire d'API et la meilleure performance de PSDP. Enfin, des simulations numériques de ces schémas algorithmiques confirment notre analyse.

Nous considérons le problème du contrôle optimal actualisé à horizon infini formalisé dans le cadre des processus de décision Markoviens. Nous nous focalisons sur plusieurs variations approchées du schéma itération sur les politiques: itérations sur les politiques approché (API), itérations sur les politiques conservatif (CPI), une adaptation naturelle de l'algorithme ''Policy Search by Dynamic Programming'' au cas de l'horizon infini (PSDP), et itérations sur les politiques non-stationnaires (NSPI). Pour tous ces algorithmes, nous décrivons des bornes de performance en fonction de l'erreur $\epsilon$ à chaque itération, et faisons une comparaison en portant une attention particulière aux coefficients de concentration impliqués, au nombre d'itérations et à la mémoire requis. Notre analyse souligne plusieurs points: 1) Les garanties de performance de CPI peuvent être arbitrairement meilleures que celle d'API, mais au prix d'une augmentation---exponentielle en $\frac{1}{\epsilon}$---du nombre d'itérations. 2) PSDP combine les avantages d'API et CPI: sa garantie de performance est similaire à celle de CPI, et elle est obtenue en un nombre d'itérations identique à celui d'API. 3) Contrairement à API qui requiert une mémoire constante, la mémoire dont CPI et PSDP ont besoin est proportionnelle au nombre d'itérations, ce qui peut être problématique lorsque le facteur d'actualisation $\gamma$ est proche de 1 ou lorsque l'erreur d'approximation $\epsilon$ est proche de 0; nous montrons que l'algorithme NSPI permet de faire un compromis entre la bonne mémoire d'API et la meilleure performance de PSDP. Enfin, des simulations numériques de ces schémas algorithmiques confirment notre analyse.

National audience ; Étant donné un processus de décision Markovien (PDM) avec $n$ états et $m$ actions, nous étudions le nombre d'étapes requises par l'algorithme itérations sur les politiques (IP) pour converger vers la politique optimale $\gamma$ actualisée. Nous considérons deux variations d'IP: IP-Howard qui change les actions dans tous les états qui ont un avantage strictement positif, et IP-Simplexe qui change uniquement une action dans l'état qui a l'avantage maximal. Nous montrons que IP-Howard termine après au plus $$ n(m-1) \left \lceil \frac{1}{1-\gamma}\log \left( \frac{1}{1-\gamma} \right) \right \rceil = O \left( \frac{ n m}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) $$ itérations, améliorant d'un facteur $O(\log n)$ un résultat de Hansen et al. (2013), tandis que IP-Simplexe termine après au plus $$ n^2(m-1) \left( 1 + \frac{2}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) = O \left( \frac{n^2 m}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) $$ itérations, améliorant d'un facteur $O(\log n)$ un résultat de Ye (2011). Sous des hypothèses structurelles du PDM, nous considérons ensuite des majorants qui sont indépendants du facteur d'actualisation $\gamma$: étant données une mesure $\tau_t$ du temps maximal pour quitter les zones transientes et une mesure $\tau_r$ du temps maximal pour revisiter les états dans les classes récurrentes sous l'ensemble des politiques, nous montrons que IP-Simplexe termine après au plus $$ n^2 (m-1) \left(\lceil \tau_r \log (n \tau_r) \rceil +\lceil \tau_r \log (n \tau_t) \rceil \right) \left[ (m-1) \lceil n \tau_t \log (n \tau_t)\rceil + \lceil n \tau_t \log (n^2 \tau_t ) \rceil\right] =\tilde O \left( n^3 m^2 \tau_t \tau_r \right) $$ itérations. Ceci généralise un résultat récent de Post & Ye (2012) sur les PDMs déterministes dans lesquels on a $\tau_t=\tau_r=n$. Nous expliquons pourquoi des résultats analogues semblent difficiles à obtenir pour IP-Howard. Enfin, sous l'hypothèse supplémentaire (restrictive) que l'espace d'états est ...

National audience ; Étant donné un processus de décision Markovien (PDM) avec $n$ états et $m$ actions, nous étudions le nombre d'étapes requises par l'algorithme itérations sur les politiques (IP) pour converger vers la politique optimale $\gamma$ actualisée. Nous considérons deux variations d'IP: IP-Howard qui change les actions dans tous les états qui ont un avantage strictement positif, et IP-Simplexe qui change uniquement une action dans l'état qui a l'avantage maximal. Nous montrons que IP-Howard termine après au plus $$ n(m-1) \left \lceil \frac{1}{1-\gamma}\log \left( \frac{1}{1-\gamma} \right) \right \rceil = O \left( \frac{ n m}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) $$ itérations, améliorant d'un facteur $O(\log n)$ un résultat de Hansen et al. (2013), tandis que IP-Simplexe termine après au plus $$ n^2(m-1) \left( 1 + \frac{2}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) = O \left( \frac{n^2 m}{1-\gamma} \log \left( \frac{1}{1-\gamma} \right)\right) $$ itérations, améliorant d'un facteur $O(\log n)$ un résultat de Ye (2011). Sous des hypothèses structurelles du PDM, nous considérons ensuite des majorants qui sont indépendants du facteur d'actualisation $\gamma$: étant données une mesure $\tau_t$ du temps maximal pour quitter les zones transientes et une mesure $\tau_r$ du temps maximal pour revisiter les états dans les classes récurrentes sous l'ensemble des politiques, nous montrons que IP-Simplexe termine après au plus $$ n^2 (m-1) \left(\lceil \tau_r \log (n \tau_r) \rceil +\lceil \tau_r \log (n \tau_t) \rceil \right) \left[ (m-1) \lceil n \tau_t \log (n \tau_t)\rceil + \lceil n \tau_t \log (n^2 \tau_t ) \rceil\right] =\tilde O \left( n^3 m^2 \tau_t \tau_r \right) $$ itérations. Ceci généralise un résultat récent de Post & Ye (2012) sur les PDMs déterministes dans lesquels on a $\tau_t=\tau_r=n$. Nous expliquons pourquoi des résultats analogues semblent difficiles à obtenir pour IP-Howard. Enfin, sous l'hypothèse supplémentaire (restrictive) que l'espace d'états est ...

National audience ; En apprentissage par renforcement, la recherche locale de politique est une approche classique permettant de prendre en compte de grands espaces d'état. Formellement, elle consiste à chercher localement dans un espace de politiques paramétrées la solution qui va maximiser la fonction de valeur associée, moyennée selon une loi prédéfinie sur les états. La première contribution de cet article montre que si l'espace de politiques est convexe, \emph{tout optimum local} (approché) présente une \emph{garantie globale de performance}. Malheureusement, supposer la convexité de l'espace de recherche est une hypothèse forte : elle n'est pas satisfaite par les représentations usuelles des politiques et définir une paramétrisation non triviale qui satisfasse cette propriété est difficile. Une solution naturelle pour palier ce problème est d'optimiser la fonction objectif associée grâce à une montée de gradient fonctionnel, la recherche étant contrainte à l'enveloppe convexe de l'espace de politiques. Il s'avère que l'algorithme résultant est une légère généralisation du schéma d'itération conservative de la politique. Ainsi, notre seconde contribution consiste à souligner cette connexion originale entre recherche locale de politique et programmation dynamique approchée.

National audience ; En apprentissage par renforcement, la recherche locale de politique est une approche classique permettant de prendre en compte de grands espaces d'état. Formellement, elle consiste à chercher localement dans un espace de politiques paramétrées la solution qui va maximiser la fonction de valeur associée, moyennée selon une loi prédéfinie sur les états. La première contribution de cet article montre que si l'espace de politiques est convexe, \emph{tout optimum local} (approché) présente une \emph{garantie globale de performance}. Malheureusement, supposer la convexité de l'espace de recherche est une hypothèse forte : elle n'est pas satisfaite par les représentations usuelles des politiques et définir une paramétrisation non triviale qui satisfasse cette propriété est difficile. Une solution naturelle pour palier ce problème est d'optimiser la fonction objectif associée grâce à une montée de gradient fonctionnel, la recherche étant contrainte à l'enveloppe convexe de l'espace de politiques. Il s'avère que l'algorithme résultant est une légère généralisation du schéma d'itération conservative de la politique. Ainsi, notre seconde contribution consiste à souligner cette connexion originale entre recherche locale de politique et programmation dynamique approchée.

National audience ; On considère l'algorithme LSTD($\lambda$) (least-squares temporal-difference) avec traces d'éligibilité proposé par Boyan (2002). Cet algorithme renvoie, pour une politique fixée, une approximation linéaire de la fonction de valeur $v$ pour les processus décisionnels de Markov admettant un grand espace d'états. On se restreint dans cet article au cas des chaînes de Markov $\beta$-mélangeantes. Sous cette hypothèse, on estime la vitesse de convergence de cet algorithme pour n'importe quelle valeur de $\lambda\in(0,1)$. La borne d'erreur obtenue étend et améliore celle introduite par Lazaric et al. (2012) pour le cas $\lambda=0$. L'analyse proposée permet de quantifier l'influence du paramètre $\lambda$, de l'espace linéaire de projection et du nombre d'échantillons utilisés.

National audience ; On considère l'algorithme LSTD($\lambda$) (least-squares temporal-difference) avec traces d'éligibilité proposé par Boyan (2002). Cet algorithme renvoie, pour une politique fixée, une approximation linéaire de la fonction de valeur $v$ pour les processus décisionnels de Markov admettant un grand espace d'états. On se restreint dans cet article au cas des chaînes de Markov $\beta$-mélangeantes. Sous cette hypothèse, on estime la vitesse de convergence de cet algorithme pour n'importe quelle valeur de $\lambda\in(0,1)$. La borne d'erreur obtenue étend et améliore celle introduite par Lazaric et al. (2012) pour le cas $\lambda=0$. L'analyse proposée permet de quantifier l'influence du paramètre $\lambda$, de l'espace linéaire de projection et du nombre d'échantillons utilisés.

National audience ; On considère l'algorithme LSTD($\lambda$) (least-squares temporal-difference) avec traces d'éligibilité proposé par Boyan (2002). Cet algorithme renvoie, pour une politique fixée, une approximation linéaire de la fonction de valeur $v$ pour les processus décisionnels de Markov admettant un grand espace d'états. On se restreint dans cet article au cas des chaînes de Markov $\beta$-mélangeantes. Sous cette hypothèse, on estime la vitesse de convergence de cet algorithme pour n'importe quelle valeur de $\lambda\in(0,1)$. La borne d'erreur obtenue étend et améliore celle introduite par Lazaric et al. (2012) pour le cas $\lambda=0$. L'analyse proposée permet de quantifier l'influence du paramètre $\lambda$, de l'espace linéaire de projection et du nombre d'échantillons utilisés.

International audience ; In the context of large space MDPs with linear value function approximation, we introduce a new approximate version of λ-Policy Iteration (Bertsekas & Ioffe, 1996), a method that generalizes Value Iteration and Policy Iteration with a parameter λ ∈ (0, 1). Our approach, called Least-Squares λ Policy Iteration, generalizes LSPI (Lagoudakis & Parr, 2003) which makes efficient use of training samples compared to classical temporaldifferences methods. The motivation of our work is to exploit the λ parameter within the least-squares context, and without having to generate new samples at each iteration or to know a model of the MDP. We provide a performance bound that shows the soundness of the algorithm. We show empirically on a simple chain problem and on the Tetris game that this λ parameter acts as a bias-variance trade-off that may improve the convergence and the performance of the policy obtained. ; Dans le contexte des Processus de Décision Markoviens (PDM) à grands espaces d'états avec approximation linéaire de la fonction de valeur, nous proposons un nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), qui généralise et hérite des propriétés intéressantes de deux algorithmes existants~: λ-Policy Iteration ($\lambda$PI) (Bertsekas et Ioffe, 1996) et Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Si le paramètre λ de λPI permet, comme dans la plupart des algorithmes du domaine, de faire un compromis biais-variance dans l'évaluation d'une politique, il introduit également de l'optimisme dans un schéma de type itération sur les politiques. A la manière de LSPI, l'algorithme que nous proposons ne nécessite pas de générer de nouveaux échantillons à chaque changement de politique (il est off-policy), les utilise de manière efficace (c'est une méthode du second ordre) et n'a pas besoin de disposer d'un modèle du PDM. Nous établissons un résultat analytique très général qui montre qu'il est raisonnable d'introduire de l'optimisme dans un schéma PI, dans le ...

National audience ; Dans le contexte des Processus de Décision Markoviens (PDM) à grands espaces d'états avec approximation linéaire de la fonction de valeur, nous proposons un nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), qui généralise et hérite des propriétés intéressantes de deux algorithmes existants~: λ-Policy Iteration (λPI) (Bertsekas et Ioffe, 1996) et Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Si le paramètre λ de λPI permet, comme dans la plupart des algorithmes du domaine, de faire un compromis biais-variance dans l'évaluation d'une politique, il introduit également de l'optimisme dans un schéma de type itération sur les politiques. A la manière de LSPI, l'algorithme que nous proposons ne nécessite pas de générer de nouveaux échantillons à chaque changement de politique (il est off-policy), les utilise de manière efficace (c'est une méthode du second ordre) et n'a pas besoin de disposer d'un modèle du PDM. Nous établissons un résultat analytique très général qui montre qu'il est raisonnable d'introduire de l'optimisme dans un schéma PI, dans le sens où il garantit la performance de la politique lorsque l'erreur d'approximation est contrôlée à chaque itération. Ce résultat s'applique en particulier à LSλPI. Finalement, nous vérifions empiriquement sur un problème simple de type chaîne d'états et sur le jeu de Tetris l'intérêt de ce nouvel algorithme, en montrant que le paramètre λ permet d'améliorer la convergence et la performance de la politique obtenues par LSPI.

International audience ; In the context of large space MDPs with linear value function approximation, we introduce a new approximate version of λ-Policy Iteration (Bertsekas & Ioffe, 1996), a method that generalizes Value Iteration and Policy Iteration with a parameter λ ∈ (0, 1). Our approach, called Least-Squares λ Policy Iteration, generalizes LSPI (Lagoudakis & Parr, 2003) which makes efficient use of training samples compared to classical temporaldifferences methods. The motivation of our work is to exploit the λ parameter within the least-squares context, and without having to generate new samples at each iteration or to know a model of the MDP. We provide a performance bound that shows the soundness of the algorithm. We show empirically on a simple chain problem and on the Tetris game that this λ parameter acts as a bias-variance trade-off that may improve the convergence and the performance of the policy obtained. ; Dans le contexte des Processus de Décision Markoviens (PDM) à grands espaces d'états avec approximation linéaire de la fonction de valeur, nous proposons un nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), qui généralise et hérite des propriétés intéressantes de deux algorithmes existants~: λ-Policy Iteration ($\lambda$PI) (Bertsekas et Ioffe, 1996) et Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Si le paramètre λ de λPI permet, comme dans la plupart des algorithmes du domaine, de faire un compromis biais-variance dans l'évaluation d'une politique, il introduit également de l'optimisme dans un schéma de type itération sur les politiques. A la manière de LSPI, l'algorithme que nous proposons ne nécessite pas de générer de nouveaux échantillons à chaque changement de politique (il est off-policy), les utilise de manière efficace (c'est une méthode du second ordre) et n'a pas besoin de disposer d'un modèle du PDM. Nous établissons un résultat analytique très général qui montre qu'il est raisonnable d'introduire de l'optimisme dans un schéma PI, dans le ...

International audience ; In the context of large space MDPs with linear value function approximation, we introduce a new approximate version of λ-Policy Iteration (Bertsekas & Ioffe, 1996), a method that generalizes Value Iteration and Policy Iteration with a parameter λ ∈ (0, 1). Our approach, called Least-Squares λ Policy Iteration, generalizes LSPI (Lagoudakis & Parr, 2003) which makes efficient use of training samples compared to classical temporaldifferences methods. The motivation of our work is to exploit the λ parameter within the least-squares context, and without having to generate new samples at each iteration or to know a model of the MDP. We provide a performance bound that shows the soundness of the algorithm. We show empirically on a simple chain problem and on the Tetris game that this λ parameter acts as a bias-variance trade-off that may improve the convergence and the performance of the policy obtained. ; Dans le contexte des Processus de Décision Markoviens (PDM) à grands espaces d'états avec approximation linéaire de la fonction de valeur, nous proposons un nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), qui généralise et hérite des propriétés intéressantes de deux algorithmes existants~: λ-Policy Iteration ($\lambda$PI) (Bertsekas et Ioffe, 1996) et Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Si le paramètre λ de λPI permet, comme dans la plupart des algorithmes du domaine, de faire un compromis biais-variance dans l'évaluation d'une politique, il introduit également de l'optimisme dans un schéma de type itération sur les politiques. A la manière de LSPI, l'algorithme que nous proposons ne nécessite pas de générer de nouveaux échantillons à chaque changement de politique (il est off-policy), les utilise de manière efficace (c'est une méthode du second ordre) et n'a pas besoin de disposer d'un modèle du PDM. Nous établissons un résultat analytique très général qui montre qu'il est raisonnable d'introduire de l'optimisme dans un schéma PI, dans le ...