2020/10/28 by Kenny Young, Richard S. Sutton, Young, Kenny +1 · 1 citation
Computer Science · #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2010.15268
Despite empirical success, the theory of reinforcement learning (RL) with\nvalue function approximation remains fundamentally incomplete. Prior work has\nidentified a variety of pathological behaviours that arise in RL algorithms\nthat combine approximate on-policy evaluation and greedification. One prominent\nexample is policy oscillation, wherein an algorithm may cycle indefinitely\nbetween policies, rather than converging to a fixed point. What is not well\nunderstood however is the quality of the policies in the region of oscillation.\nIn this paper we present simple examples illustrating that in addition to\npolicy oscillation and multiple fixed points -- the same basic issue can lead\nto convergence to the worst possible policy for a given approximation. Such\nbehaviours can arise when algorithms optimize evaluation accuracy weighted by\nthe distribution of states that occur under the current policy, but greedify\nbased on the value of states which are rare or nonexistent under this\ndistribution. This means the values used for greedification are unreliable and\ncan steer the policy in undesirable directions. Our observation that this can\nlead to the worst possible policy shows that in a general sense such algorithms\nare unreliable. The existence of such examples helps to narrow the kind of\ntheoretical guarantees that are possible and the kind of algorithmic ideas that\nare likely to be helpful. We demonstrate analytically and experimentally that\nsuch pathological behaviours can impact a wide range of RL and dynamic\nprogramming algorithms; such behaviours can arise both with and without\nbootstrapping, and with linear function approximation as well as with more\ncomplex parameterized functions like neural networks.\n