Document Open Access Logo

Stochastic Control via Entropy Compression

Authors Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.83.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Dimitris Achlioptas
Fotis Iliopoulos
Nikos Vlassis

Cite As Get BibTex

Dimitris Achlioptas, Fotis Iliopoulos, and Nikos Vlassis. Stochastic Control via Entropy Compression. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 83:1-83:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.83

Abstract

Consider an agent trying to bring a system to an acceptable state by repeated probabilistic action. Several recent works on algorithmizations of the Lovász Local Lemma (LLL) can be seen as establishing sufficient conditions for the agent to succeed. Here we study whether such stochastic control is also possible in a noisy environment, where both the process of state-observation and the process of state-evolution are subject to adversarial perturbation (noise). The introduction of noise causes the tools developed for LLL algorithmization to break down since the key LLL ingredient, the sparsity of the causality (dependence) relationship, no longer holds. To overcome this challenge we develop a new analysis where entropy plays a central role, both to measure the rate at which progress towards an acceptable state is made and the rate at which noise undoes this progress. The end result is a sufficient condition that allows a smooth tradeoff between the intensity of the noise and the amenability of the system, recovering an asymmetric LLL condition in the noiseless case.

Subject Classification

Keywords
  • Stochastic Control
  • Lovasz Local Lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Achlioptas, F. Iliopoulos, and N. Vlassis. Stochastic Control via Entropy Compression. ArXiv e-prints, July 2016. URL: https://arxiv.org/abs/1607.06494, URL: http://arxiv.org/abs/1607.06494.
  2. Dimitris Achlioptas and Fotis Iliopoulos. Focused stochastic local search and the Lovász local lemma. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 2024-2038. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch141.
  3. Dimitris Achlioptas and Fotis Iliopoulos. Random walks that find perfect objects and the Lovász local lemma. J. ACM, 63(3):22, 2016. URL: http://dx.doi.org/10.1145/2818352.
  4. Mikko Alava, John Ardelius, Erik Aurell, Petteri Kaski, Supriya Krishnamurthy, Pekka Orponen, and Sakari Seitz. Circumspect descent prevails in solving random constraint satisfaction problems. Proceedings of the National Academy of Sciences, 105(40):15253-15257, 2008. URL: http://dx.doi.org/10.1073/pnas.0712263105.
  5. Noga Alon. A parallel algorithmic version of the local lemma. Random Struct. Algorithms, 2(4):367-378, 1991. URL: http://dx.doi.org/10.1002/rsa.3240020403.
  6. József Beck. An algorithmic approach to the Lovász local lemma. I. Random Structures Algorithms, 2(4):343-365, 1991. URL: http://dx.doi.org/10.1002/rsa.3240020402.
  7. Dimitri P. Bertsekas. Dynamic Programming and Optimal Control, Vol. II. Athena Scientific, 2012. Google Scholar
  8. Krishnendu Chatterjee, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. Optimal cost almost-sure reachability in POMDPs. Artif. Intell., 234:26-48, 2016. URL: http://dx.doi.org/10.1016/j.artint.2016.01.007.
  9. Lonnie Chrisman. Reinforcement learning with perceptual aliasing: The perceptual distinctions approach. In AAAI, pages 183-188. Citeseer, 1992. Google Scholar
  10. Artur Czumaj and Christian Scheideler. Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), pages 30-39, 2000. Google Scholar
  11. Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609-627. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam, 1975. Google Scholar
  12. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531-2597, 2010. Google Scholar
  13. Jerzy Filar and Koos Vrieze. Competitive Markov Decision Processes. Springer-Verlag New York, Inc., New York, NY, USA, 1996. Google Scholar
  14. David G. Harris and Aravind Srinivasan. A constructive algorithm for the Lovász local lemma on permutations. In SODA, pages 907-925. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.68.
  15. Nicholas J. A. Harvey and Jan Vondrák. An algorithmic proof of the Lovász local lemma via resampling oracles. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1327-1346. IEEE Computer Society, 2015. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7352273, URL: http://dx.doi.org/10.1109/FOCS.2015.85.
  16. Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1):99-134, 1998. Google Scholar
  17. Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996. Google Scholar
  18. Kashyap Babu Rao Kolipaka and Mario Szegedy. Moser and Tardos meet Lovász. In STOC, pages 235-244. ACM, 2011. URL: http://dx.doi.org/10.1145/1993636.1993669.
  19. Vladimir Kolmogorov. Commutativity in the algorithmic lovász local lemma. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 780-787. IEEE Computer Society, 2016. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7781469, URL: http://dx.doi.org/10.1109/FOCS.2016.88.
  20. Michael L. Littman, Judy Goldsmith, and Martin Mundhenk. The computational complexity of probabilistic planning. Journal of Artificial Intelligence Research, 9(1):1-36, 1998. Google Scholar
  21. Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems. In AAAI/IAAI, pages 541-548, 1999. Google Scholar
  22. Michael Molloy and Bruce Reed. Further algorithmic aspects of the local lemma. In STOC'98 (Dallas, TX), pages 524-529. ACM, New York, 1999. Google Scholar
  23. Robin A. Moser. A constructive proof of the Lovász local lemma. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 343-350. ACM, 2009. URL: http://dx.doi.org/10.1145/1536414.1536462.
  24. Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2):Art. 11, 15, 2010. URL: http://dx.doi.org/10.1145/1667053.1667060.
  25. Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender. Complexity of finite-horizon Markov decision process problems. Journal of the ACM (JACM), 47(4):681-720, 2000. Google Scholar
  26. Christos H. Papadimitriou. On selecting a satisfying truth assignment (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 163-169. IEEE Computer Society, 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185365.
  27. Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of Markov decision processes. Mathematics of operations research, 12(3):441-450, 1987. Google Scholar
  28. Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley &Sons, 2014. Google Scholar
  29. Bart Selman, Henry A. Kautz, and Bram Cohen. Local search strategies for satisfiability testing. In David S. Johnson and Michael A. Trick, editors, Cliques, Coloring, and Satisfiability, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 11-13, 1993, volume 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 521-532. DIMACS/AMS, 1993. URL: http://dimacs.rutgers.edu/Volumes/Vol26.html.
  30. Aravind Srinivasan. Improved algorithmic versions of the Lovász local lemma. In Shang-Hua Teng, editor, SODA, pages 611-620. SIAM, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347150.
  31. Nikos Vlassis, Michael L. Littman, and David Barber. On the computational complexity of stochastic controller optimization in POMDPs. ACM Transactions on Computation Theory (TOCT), 4(4):12, 2012. URL: http://dx.doi.org/10.1145/2382559.2382563.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact