{"id":826651,"date":"2022-03-15T06:04:38","date_gmt":"2022-03-15T13:04:38","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-project&#038;p=826651"},"modified":"2022-03-24T14:53:45","modified_gmt":"2022-03-24T21:53:45","slug":"towards-a-generalized-policy-iteration-theorem","status":"publish","type":"msr-project","link":"https:\/\/www.microsoft.com\/en-us\/research\/project\/towards-a-generalized-policy-iteration-theorem\/","title":{"rendered":"Towards a generalized policy iteration theorem"},"content":{"rendered":"<section class=\"mb-3 moray-highlight\">\n\t<div class=\"card-img-overlay mx-lg-0\">\n\t\t<div class=\"card-background  has-background- card-background--full-bleed\">\n\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"2429\" height=\"812\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban.jpg\" class=\"attachment-full size-full\" alt=\"Dr Jekyll and Mr Hyde\" style=\"object-position: 50% 44%\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban.jpg 2429w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban-300x100.jpg 300w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban-1024x342.jpg 1024w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban-768x257.jpg 768w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban-1536x513.jpg 1536w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban-2048x685.jpg 2048w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2022\/03\/2560px-Dr_Jekyll_and_Mr_Hyde_poster_ban-240x80.jpg 240w\" sizes=\"(max-width: 2429px) 100vw, 2429px\" \/>\t\t<\/div>\n\t\t<!-- Foreground -->\n\t\t<div class=\"card-foreground d-flex mt-md-n5 my-lg-5 px-g px-lg-0\">\n\t\t\t<!-- Container -->\n\t\t\t<div class=\"container d-flex mt-md-n5 my-lg-5 align-self-center\">\n\t\t\t\t<!-- Card wrapper -->\n\t\t\t\t<div class=\"w-100 w-lg-col-5\">\n\t\t\t\t\t<!-- Card -->\n\t\t\t\t\t<div class=\"card material-md-card py-5 px-md-5\">\n\t\t\t\t\t\t<div class=\"card-body \">\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\n\n<h1 id=\"towards-a-generalized-policy-iteration-theorem\">Towards a generalized policy iteration theorem<\/h1>\n\n\n\n<p>We intend to advance the theoretical understanding of actor-critic algorithms under the lens of policy iteration.<\/p>\n\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/div>\n<\/section>\n\n\n\n\n\n<p>Policy Iteration consists in a loop over two processing steps: policy evaluation and policy improvement. Policy Iteration has strong convergence properties when the policy evaluation is exact and the policy improvement is greedy. However, the convergence of a generalized setting where policy evaluation is approximate and stochastic and the policy improvement is a local update remains an open problem, which this umbrella project intends to address.<\/p>\n\n\n\n<p>Several challenges need to be addressed, either independently or jointly:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Approximation in the policy evaluation: in practice, value updates do not return the exact value of the current policy,<\/li><li>Stochasticity in the updates: in practice, they are performed from samples either directly collected by interacting with the environment, or from a replay buffer,<\/li><li>Soft policy updates: although the greedy update is practical, it is often preferrable for stability and exploration to perform soft updates that slowly move the current policy towards the greedy one,<\/li><li>Function approximation: in complex domain, one must use function approximation, such as neural networks, to represent both the policy and its value. <\/li><\/ul>\n\n\n\n<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/a-deeper-look-at-discounting-mismatch-in-actor-critic-algorithms\/\">Our first contribution<\/a> (AAMAS 2022) triggered this research direction. The paper explores empirically the mismatch between actor-critic updates used by practitioners and those prescribed by the policy gradient theorem. It suggests two interpretations of the performance improvement provided by the modified update, and naturally begs the question of the underlying properties updates should verify to guarantee convergence to optimality.        <\/p>\n\n\n\n<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/dr-jekyll-mr-hyde-the-strange-case-of-off-policy-policy-updates\/\">Our second contribution<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (NeurIPS 2021) consists in casting the actor-critic architecture into the generalization policy iteration framework, and proving the necessary and sufficient conditions for density-agnostic policy gradient policy updates to converge to optimality when coupled with exact policy evaluation. These conditions relate to asymptotic coverage of the state-space when applying the policy update, which advocates for a specific algorithm family that we call <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/github.com\/microsoft\/Dr-Jekyll-and-Mr-Hyde-The-Strange-Case-of-Off-Policy-Policy-Updates\/\" target=\"_blank\" rel=\"noreferrer noopener\">Dr Jekyll & Mr Hyde<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> because of its two-sided behavior.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button is-style-fill-github\"><a data-bi-type=\"button\" class=\"wp-block-button__link\" href=\"https:\/\/github.com\/microsoft\/Dr-Jekyll-and-Mr-Hyde-The-Strange-Case-of-Off-Policy-Policy-Updates\/\" target=\"_blank\" rel=\"noreferrer noopener\">Get the code<\/a><\/div>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/beyond-the-policy-gradient-theorem-for-efficient-policy-updates-in-actor-critic-algorithms\/\">Our third contribution<\/a> (AISTATS 2022) shows that similar results may be obtained for updates that are not policy gradients and that these updates may address some slowness in learning that policy gradients may suffer from.<\/p>\n\n\n\n<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/publication\/global-optimality-and-finite-sample-analysis-of-softmax-off-policy-actor-critic-under-state-distribution-mismatch\/\">Our latest contribution<\/a> (submitted to JMLR) establishes the global optimality and convergence rate of an off-policy actor critic algorithm in the tabular setting without using density ratio to correct the discrepancy between the state distribution of the behavior policy and that of the target policy. Our work goes beyond existing works on the optimality of policy gradient methods in that existing works use the exact policy gradient for updating the policy parameters while we use an approximate and stochastic update step.<\/p>\n\n\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>We intend to advance the theoretical understanding of actor-critic algorithms under the lens of policy iteration. Policy Iteration consists in a loop over two processing steps: policy evaluation and policy improvement. Policy Iteration has strong convergence properties when the policy evaluation is exact and the policy improvement is greedy. However, the convergence of a generalized [&hellip;]<\/p>\n","protected":false},"featured_media":826822,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[13556],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-826651","msr-project","type-msr-project","status-publish","has-post-thumbnail","hentry","msr-research-area-artificial-intelligence","msr-locale-en_us","msr-archive-status-active"],"msr_project_start":"","related-publications":[797176,824389,826675,826684,826693],"related-downloads":[],"related-videos":[],"related-groups":[],"related-events":[],"related-opportunities":[],"related-posts":[],"related-articles":[],"tab-content":[],"slides":[],"related-researchers":[],"msr_research_lab":[437514],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/826651"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-project"}],"version-history":[{"count":11,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/826651\/revisions"}],"predecessor-version":[{"id":829792,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/826651\/revisions\/829792"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/826822"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=826651"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=826651"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=826651"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=826651"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=826651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}