Stochastic control via entropy compression

DOI10.4230/LIPICS.ICALP.2017.83zbMATH Open1441.68148arXiv1607.06494MaRDI QIDQ5111414FDOQ5111414

Authors: Fotis Iliopoulos, Nikos Vlassis, D. Achlioptas 

Publication date: 27 May 2020

Abstract: We consider an agent trying to bring a system to an acceptable state by repeated probabilistic action. Several recent works on algorithmizations of the Lovasz 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.

Full work available at URL: https://arxiv.org/abs/1607.06494

Recommendations

• A local lemma for focused stochastic algorithms
• Focused stochastic local search and the Lovász local lemma
• Entropy compression versus Lovász local lemma
• Random walks that find perfect objects and the Lovász local lemma
• New constructive aspects of the Lovász local lemma

zbMATH Keywords

stochastic controlLovász local lemma

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (3)

• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Intelligent control with relative entropy minimizing
• Title not available (Why is that?)

This page was built for publication: Stochastic control via entropy compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111414)