DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2017.83

Stochastic Control via Entropy Compression

Authors: Dimitris Achlioptas, Fotis Iliopoulos, and Nikos Vlassis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{achlioptas_et_al:LIPIcs.ICALP.2017.83,
  author =	{Achlioptas, Dimitris and Iliopoulos, Fotis and Vlassis, Nikos},
  title =	{{Stochastic Control via Entropy Compression}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{83:1--83:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.83},
  URN =		{urn:nbn:de:0030-drops-74279},
  doi =		{10.4230/LIPIcs.ICALP.2017.83},
  annote =	{Keywords: Stochastic Control, Lovasz Local Lemma}
}

Search Results

Documents authored by Vlassis, Nikos

Stochastic Control via Entropy Compression

Abstract

Cite as

Thanks for your feedback!

Could not send message