Contrasting Exploration in Parameter and Action Space
Anirudh Vemula, Wen Sun, Drew Bagnell
vemula@cmu.edu, {wensun,dbagnell}@cs.cmu.edu

Empirical Successes of Black-Box Policy Search• Most of the success in tetris isby blackbox policy search• Cross-entropy method
achieves a score of 35 millionlines!
• Whereas, natural policy
gradient gets 7000 lines• Gabillon et. al. 2013

• Very successful in obtaining good policies for diverse
robotic tasks such as locomotion and helicopter control•Tesch et. al. 2011, Bagnell and Schneider 2003

Exploration in Model-Free Policy SearchParameter Space Exploration

Action Space Exploration

Find a direction of improvement directly in parameter
space through random exploration• Purely zeroth order approach• Eg: Cross-entropy method, Evolutionary strategies,
Augmented Random search etc.
•

Find a direction of improvement in action space
through random exploration• Leverage Jacobian of policy to update parameters• A combination of zeroth and first order approach• Eg: REINFORCE and its extensions•Jacobian of the policyr✓ J(✓) = r⇡ J(✓)r✓ ⇡Directly estimate using a zeroth order approache.g. finite differencing<latexit sha1_base64="jE0vn/K1uKLLYPEgfKQvbmSeiCs=">AAACKHicbVBNS0JBFJ1nX2ZfVss2QxLYRt6LoFoEUptoZZApqMh946iD8+Y9Zu4LRPw7bforbQoq3PZLGvUFfnRg4HDOudy5x4+kMOi6Iye1srq2vpHezGxt7+zuZfcPnkwYa8bLLJShrvpguBSKl1Gg5NVIcwh8ySt+73bsV565NiJUj9iPeCOAjhJtwQCt1MwW6wp8Cc06djkCvc9PySm9pn9OJGbk+bj1mtmcW3AnoMvES0iOJCg1sx/1VsjigCtkEoypeW6EjQFoFEzyYaYeGx4B60GH1yxVEHDTGEwuHdITq7RoO9T2KaQTdXZiAIEx/cC3yQCwaxa9sfifV4uxfdkYCBXFyBWbLmrHkmJIx7XRltCcoexbAkwL+1fKuqCBoS03Y0vwFk9eJuWzwlXBezjPFW+SNtLkiByTPPHIBSmSO1IiZcLIC3kjn+TLeXXenW9nNI2mnGTmkMzB+fkFI2Kljw==</latexit>

Estimate using a zeroth order approach

AnalysisParameter space

LinearContextual
BanditModel-Free RL

d2
O( 2 )✏✓ 2 3◆d Q
O✏3<latexit sha1_base64="rCJ+YHaHpBOLHSY0NeiflweMA0w=">AAACC3icbVC9TsMwGHTKXyl/BUYWiwqpLFVSIQFbBQsbRSK0UhMqx3Vaq44d2Q5SFeUBWHgVFgZArLwAG2+D02aAlpMsne7uk7/vgphRpW372yotLa+srpXXKxubW9s71d29OyUSiYmLBROyGyBFGOXE1VQz0o0lQVHASCcYX+Z+54FIRQW/1ZOY+BEachpSjLSR+tWaFyE9woil11ndCyXC6eC+maUeiRVlght+bFJ2w54CLhKnIDVQoN2vfnkDgZOIcI0ZUqrn2LH2UyQ1xYxkFS9RJEZ4jIakZyhHEVF+Oj0mg0dGGcBQSPO4hlP190SKIqUmUWCS+epq3svF/7xeosMzP6U8TjThePZRmDCoBcybgQMqCdZsYgjCkppdIR4h04g2/VVMCc78yYvEbTbOG87NSa11UbRRBgfgENSBA05BC1yBNnABBo/gGbyCN+vJerHerY9ZtGQVM/vgD6zPH3Akm20=</latexit>

Action space

1O( 4 )✏<latexit sha1_base64="8e0Tx2jDANA7GWnTPsl5Jt5WU0k=">AAACCXicbVA9T8MwEHX4LOUrwMhiqJDKUiWoErBVsLBRJEIrNaVyXKe16tiR7SBVUWYW/goLAyBW/gEb/wanzQAtTzrp6b073d0LYkaVdpxva2FxaXlltbRWXt/Y3Nq2d3bvlEgkJh4WTMh2gBRhlBNPU81IO5YERQEjrWB0mfutByIVFfxWj2PSjdCA05BipI3Usw/8COkhRiy9zqp+KBFO3Sz1SawoE/y+nh337IpTcyaA88QtSAUUaPbsL78vcBIRrjFDSnVcJ9bdFElNMSNZ2U8UiREeoQHpGMpRRFQ3nbySwSOj9GEopCmu4UT9PZGiSKlxFJjO/HA16+Xif14n0eFZN6U8TjTheLooTBjUAua5wD6VBGs2NgRhSc2tEA+RyUOb9MomBHf25XnindTOa+5NvdK4KNIogX1wCKrABaegAa5AE3gAg0fwDF7Bm/VkvVjv1se0dcEqZvbAH1ifP+fBmpg=</latexit><latexit sha1_base64="tJD79VNqmFSEVJUFTVDkQifgsfw=">AAACIHicbVBPSwJBHJ21f2b/rI5dhiRQAtk1IbtJXbylkCm4KrPjrA7Ozi4zs4Es+1W69FW6dKioW32aZnUPpT0YeLz3+/Gb95yAUalM88vIrK1vbG5lt3M7u3v7B/nDo3vphwKTNvaZL7oOkoRRTtqKKka6gSDIcxjpONObxO88ECGpz+/ULCB9D405dSlGSkvDfM32kJpgxKLbuGi7AuEoGFQag2oc2SSQlPlc82JrcAHPoS3p2EODCmyVSsN8wSybc8BVYqWkAFI0h/lPe+Tj0CNcYYak7FlmoPoREopiRuKcHUoSIDxFY9LTlCOPyH40TxjDM62MoOsL/biCc/X3RoQ8KWeeoyeTPHLZS8T/vF6o3Fo/ojwIFeF4ccgNGVQ+TOqCIyoIVmymCcKC6r9CPEG6JqVLzekSrOXIq6RdKV+VrVa1UL9O28iCE3AKisACl6AOGqAJ2gCDR/AMXsGb8WS8GO/Gx2I0Y6Q7x+APjO8f13uiMw==</latexit>

Our analysis explains the success of black-box
policy search methods like random search andevolutionary strategies in RL (OpenAI gym tasks
have very long horizons)•For tasks with long horizons, exploration inparameter space should be preferred•

If the parametric complexity required is large,
exploration in action space is better4p H
3O( 4 (Q +✏Experiments•

1Linear Contextual Bandit : Avg. Regret = T (E[ ci (✓i )]t=1<latexit sha1_base64="GMXmKWjPEB5gg+R6eh76HsHAPsc=">AAACWXicdVFNaxsxFNRu2sR1v9zk2IuoKdiHmt1QaHMI5INAj2mxm4B3u2jlt7aIpN1Ib0ON2D+ZSwjkrwQifxzapB0QDDPzkN4or6SwGEW3Qbjx7PnmVutF++Wr12/edt5t/7RlbTiMeClLc54zC1JoGKFACeeVAaZyCWf5xfHCP7sCY0WphzivIFVsqkUhOEMvZZ3LBOE3usOr6YD+gKkBbOg+TQrDuIsbN2x6iWI4y3N30owTW6vM4X7c/BpSnolegjNAlol+Sj/RRAmduZXU0P9k+/2s040G0RL0KYnXpEvWOM0618mk5LUCjVwya8dxVGHqmEHBJTTtpLZQMX7BpjD2VDMFNnXLahr60SsTWpTGH410qf454Ziydq5yn1zsaR97C/Ff3rjG4mvqhK5qBM1XFxW1pFjSRc90IgxwlHNPGDfCv5XyGfO1ov+Nti8hfrzyUzLaHewN4u+fuwdH6zZa5D35QHokJl/IAflGTsmIcHJD7oPNYCu4C8OwFbZX0TBYz+yQvxDuPADHirPp</latexit>

Model-Free RL :2kr✓ J(✓)k2  ✏eps-stationary point<latexit sha1_base64="UXLEw9TvSJOxNXeO9MaRLx7a7J0=">AAACFXicbVDLSgNBEJz1GeMr6tHLYBD0YNgNgnoLehFPEYwK2Rh6Jx0zODu7zvQKIfoVXvwVLx5UvAre/Bsnj4OvgoGiqpqerihV0pLvf3pj4xOTU9O5mfzs3PzCYmFp+dQmmRFYE4lKzHkEFpXUWCNJCs9TgxBHCs+iq4O+f3aDxspEn1A3xUYMl1q2pQByUrOwFd6GGiIFzZA6SMCPNoZkM7xtli/KPFR4zUNMrVT9fNEv+QPwvyQYkSIbodosfIStRGQxahIKrK0HfkqNHhiSQuFdPswspiCu4BLrjmqI0TZ6g7Pu+LpTWrydGPc08YH6faIHsbXdOHLJGKhjf3t98T+vnlF7t9GTOs0ItRguameKU8L7HfGWNChIdR0BYaT7KxcdMCDINZl3JQS/T/5LauXSXik43i5W9kdt5NgqW2MbLGA7rMIOWZXVmGD37JE9sxfvwXvyXr23YXTMG82ssB/w3r8Aoj2eng==</latexit>

Dependence on parameter dimensionality
Independent of horizon length<latexit sha1_base64="ARKzSkYpYz9ooGIPTJBi+ezaBXM=">AAACIXicbVDLSgMxFM34rPU16tJNsAi6KTMqaHdFN+5swVqhU0smvdOGZjJDckcoQ7/Fjb/ixoVKd+LPmNYufB0IHM65l5tzwlQKg5737szNLywuLRdWiqtr6xub7tb2jUkyzaHBE5no25AZkEJBAwVKuE01sDiU0AwHFxO/eQ/aiERd4zCFdsx6SkSCM7RSx60EMcM+ZzK/GgUSIjygQaQZz7t3R/XAiF7M7o5HeQCpETJRltNAi14fDztuySt7U9C/xJ+REpmh1nHHQTfhWQwKuWTGtHwvxXbONAouYVQMMgMp4wPWg5alisVg2vk04ojuW6VLo0Tbp5BO1e8bOYuNGcahnZwEMr+9ifif18owOmvnQqUZguJfh6JMUkzopC/aFRo4yqEljGth/0p5n9mG0LZatCX4vyP/JY2jcqXs109K1fNZGwWyS/bIAfHJKamSS1IjDcLJA3kiL+TVeXSenTdn/DU658x2dsgPOB+fUo+kWg==</latexit>

22Q))

TX

Dependence on horizon length
Dependence on action dimensionality
Independent of parameter dimensionality

min✓

TX
t=1

ci (✓))