Elamur Research⌕
☰
home / papers / 2018 / Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration

Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration

Paper · 2018 · Evan Zheran Liu, Kelvin Guu, Panupong Pasupat et al.

Summary

The paper tackles a core obstacle in teaching RL agents to operate websites (for example, booking a flight or forwarding an email). Rewards come only at the end of an episode and only for fully correct action sequences, so random exploration rarely succeeds. Pre-training on demonstrations through behavioral cloning tends to overfit. The authors instead use a handful of demonstrations to restrict where the agent explores. From each demonstration they build a lattice of "workflows": state-independent sequences of action constraints, such as "click something near a given text, then type a goal field into an input." A simple, environment-blind workflow policy learns via a REINFORCE variant which constraints work. Its successful episodes fill a replay buffer that trains DOMNet, a neural policy that reasons over the HTML DOM tree and the goal. On MiniWoB, the Alaska Airlines booking interface and new harder tasks, the method sets state-of-the-art results using only a few demonstrations. This makes web-operating assistants far more practical to train.

Key points

  • Framework: Workflow-guided exploration (WGE) uses demonstrations to prune exploration rather than to imitate them directly. This lets an expressive neural policy (DOMNet) be trained with less risk of overfitting.

  • Constraint language: Workflow steps are built from a small set of operators:

    • Click and Type actions;
    • element selectors Tag, Text, Like, Near (within 30px), SameRow, SameCol and a Class filter;
    • Field references to the goal.

    Nesting is capped at 3 levels.

  • Sample efficiency: WGE needs only 3–10 demonstrations per task. Earlier MiniWoB work (Shi et al., 2017) used about 200 demonstrations, roughly 10 minutes per task. Compared with behavioral cloning, WGE is over 100x more sample-efficient.

  • Evaluation: The method is tested on the MiniWoB (World of Bits) benchmark, the Alaska Airlines flight-booking site, and a new task suite. The new suite covers noisy environments, natural-language variation and longer horizons.

  • Setup: Agents receive +1/−1 reward only at episode end. Goals are given either as key-value structures or as natural-language utterances.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States506 works · 330,052 citations🎓Tsinghua UniversityBeijing · China415 works · 94,028 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksInformation Systems · 1,730 works

Cite

Cite as Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi and Percy Liang. 2018. Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration. arXiv:1802.08802.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1802.08802 · arXiv 1802.08802

@misc{liu2018reinforcement,
  title = {{Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration}},
  author = {Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi and Percy Liang},
  year = {2018},
  doi = {10.48550/arxiv.1802.08802},
  eprint = {1802.08802},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1802.08802}
}

References

52 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. P. Abbeel and A. Ng. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine Learning (ICML), 2004. find
  2. J. Allen, N. Chambers, G. Ferguson, L. Galescu, H. Jung, M. Swift, and W. Taysom. PLOW: A collaborative task learning agent. In Association for the Advancement of Artificial Intelligence (AAAI), pp. 1514–1519, 2007. find
  3. D. Andre. Programmable reinforcement learning agents. PhD thesis, University of California, Berkeley, 2003. find
  4. J. Andreas, D. Klein, and S. Levine. Modular multitask reinforcement learning with policy sketches. arXiv preprint arXiv:1611.01796, 2016. find
  5. M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, P. Abbeel, and W. Zaremba. Hindsight experience replay. arXiv preprint arXiv:1707.01495, 2017.
  6. C. G. Atkeson and S. Schaal. Robot learning from demonstration. In International Conference on Machine Learning (ICML), volume 97, pp. 12–20, 1997. find
  7. P. Bacon, J. Harb, and D. Precup. The option-critic architecture. In Association for the Advancement of Artificial Intelligence (AAAI), pp. 1726–1734, 2017. find
  8. N. Baram, O. Anschel, I. Caspi, and S. Mannor. End-to-end differentiable adversarial imitation learning. In International Conference on Machine Learning (ICML), pp. 390–399, 2017. find
  9. M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research (JAIR), 47: 253–279, 2013.
  10. S. Bitzer, M. Howard, and S. Vijayakumar. Using dimensionality reduction to exploit constraints in reinforcement learning. In International Conference on Intelligent Robots and Systems (IROS), pp. 3219–3225, 2010. find
  11. T. Brys, A. Harutyunyan, H. B. Suay, S. Chernova, M. E. Taylor, and A. Now’e. Reinforcement learning from demonstration through shaping. In International Joint Conference on Artificial Intelligence (IJCAI), 2015. find
  12. N. Chentanez, A. G. Barto, and S. P. Singh. Intrinsically motivated reinforcement learning. In Advances in Neural Information Processing Systems (NIPS), pp. 1281–1288, 2005. find
  13. C. Daniel, G. Neumann, O. Kroemer, and J. Peters. Hierarchical relative entropy policy search. Journal of Machine Learning Research (JMLR), 17:3190–3239, 2016. find
  14. B. Deka, Z. Huang, and R. Kumar. Erica: Interaction mining mobile apps. In User Interface Software and Technology (UIST), pp. 767–776, 2016. find
  15. T. G. Dietterich. The MAXQ method for hierarchical reinforcement learning. In International Conference on Machine Learning (ICML), 1998. find
  16. C. Finn, S. Levine, and P. Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International Conference on Machine Learning (ICML), pp. 49–58, 2016. find
  17. W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NIPS), 2017.
  18. K. Hauser, T. Bretl, K. Harada, and J. Latombe. Using motion primitives in probabilistic sample-based planning for humanoid robots. Algorithmic foundation of robotics, 7:507–522, 2008. find
  19. T. Hester, M. Vecerik, O. Pietquin, M. Lanctot, T. Schaul, B. Piot, A. Sendonaris, G. Dulac-Arnold, I. Osband, J. Agapiou, J. Z. Leibo, and A. Gruslys. Deep Q-learning from demonstrations. In Association for the Advancement of Artificial Intelligence (AAAI), 2018. find
  20. J. Ho and S. Ermon. Generative adversarial imitation learning. In Advances in Neural Information Processing Systems (NIPS), pp. 4565–4573, 2016. find
  21. I. Hosu and T. Rebedea. Playing Atari games with deep reinforcement learning and human checkpoint replay. In Evaluating General Purpose AI, 2016. find
  22. A. Hussein, E. Elyan, M. M. Gaber, and C. Jayne. Deep reward shaping from demonstrations. In International Joint Conference on Neural Networks, 2017. find
  23. M. Jaderberg, V. Mnih, W. M. Czarnecki, T. Schaul, J. Z. Leibo, D. Silver, and K. Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611.05397, 2016.
  24. B. Kim, A. massoud Farahmand, J. Pineau, and D. Precup. Learning from limited demonstrations. In Advances in Neural Information Processing Systems (NIPS), pp. 2859–2867, 2013. find
  25. T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
  26. G. Konidaris and A. G. Barto. Building portable options: Skill transfer in reinforcement learning. In International Joint Conference on Artificial Intelligence (IJCAI), 2007. find
  27. S. Levine and V. Koltun. Guided policy search. In International Conference on Machine Learning (ICML), 2013. find
  28. L. Li, T. J. Walsh, and M. L. Littman. Towards a unified theory of state abstraction for mdps. In International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2006. find
  29. B. Marthi and C. Guestrin. Concurrent hierarchical reinforcement learning. In International Joint Conference on Artificial Intelligence (IJCAI), 2005. find
  30. V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. P. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning (ICML), 2016. find
  31. A. Nair, B. McGrew, M. Andrychowicz, W. Zaremba, and P. Abbeel. Overcoming exploration in reinforcement learning with demonstrations. arXiv preprint arXiv:1709.10089, 2017. find
  32. A. Y. Ng, D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In International Conference on Machine Learning (ICML), volume 99, pp. 278–287, 1999. find
  33. I. Osband, C. Blundell, A. Pritzel, and B. V. Roy. Deep exploration via bootstrapped DQN. In Advances In Neural Information Processing Systems, pp. 4026–4034, 2016.
  34. R. Parr and S. J. Russell. Reinforcement learning with hierarchies of machines. In Advances in Neural Information Processing Systems (NIPS), pp. 1043–1049, 1998. find
  35. C. Perez-D’Arpino and J. A. Shah. C-learn: Learning geometric constraints from demonstrations for multi-step manipulation in shared autonomy. In International Conference on Robotics and Automation (ICRA), pp. 4058–4065, 2017. find
  36. T. Pham, T. Tran, D. Phung, and S. Venkatesh. Column networks for collective classification. In Association for the Advancement of Artificial Intelligence (AAAI), 2017. find
  37. M. Phillips, V. Hwang, S. Chitta, and M. Likhachev. Learning to plan for constrained manipulation from demonstrations. Autonomous Robots, 40(1):109–124, 2016. find
  38. D. A. Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural Computation, 3(1):88–97, 1991. find
  39. M. Roderick, C. Grimm, and S. Tellex. Deep abstract Q-networks. arXiv preprint arXiv:1710.00459, 2017. — [arXiv:1710.00459](https://arxiv.org/abs/1710.00459) find
  40. S. Ross and J. A. Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.5979, 2014. find
  41. S. Ross, G. Gordon, and A. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Artificial Intelligence and Statistics (AISTATS), 2011. find
  42. T. Shi, A. Karpathy, L. Fan, J. Hernandez, and P. Liang. World of bits: An open-domain platform for web-based agents. In International Conference on Machine Learning (ICML), 2017. find
  43. B. Stone and S. Soper. Amazon Unveils a Listening, Talking, Music-Playing Speaker for Your Home. Bloomberg L. P., 2014. find
  44. W. Sun, A. Venkatraman, G. J. Gordon, B. Boots, and J. A. Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International Conference on Machine Learning (ICML), 2017. find
  45. R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction, volume 1. MIT Press MIT press Cambridge, 1998. find
  46. R. S. Sutton, D. Precup, and S. Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Articial intelligence, 112:181–211, 1999. find
  47. M. Vecerik, T. Hester, J. Scholz, F. Wang, O. Pietquin, B. Piot, N. Heess, T. Rothorl, T. Lampe, and M. Riedmiller. Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint arXiv:1707.08817, 2017. — [arXiv:1707.08817](https://arxiv.org/abs/1707.08817) find
  48. Y. Wang, J. Berant, and P. Liang. Building a semantic parser overnight. In Association for Computational Linguistics (ACL), 2015. find
  49. T. Weber, S. Racanière, D. P. Reichert, L. Buesing, A. Guez, D. J. Rezende, A. P. Badia, O. Vinyals, N. Heess, Y. Li, et al. Imagination-augmented agents for deep reinforcement learning. arXiv preprint arXiv:1707.06203, 2017. find
  50. R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229–256, 1992. find
  51. T. Yeh, T. Chang, and R. Miller. Sikuli: using GUI screenshots for search and automation. In User Interface Software and Technology (UIST), 2009. find
  52. B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In Association for the Advancement of Artificial Intelligence (AAAI), 2008. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/liu-2018-reinforcement-learning-web-interfaces-using/