Markov Chains with Rewinding
Preprint
Abstract
Motivated by techniques developed in recent progress on lower bounds for sublinear time algorithms (Behnezhad, Roghani and Rubinstein, STOC 2023, FOCS 2023, and STOC 2024) we introduce and study a new class of randomized algorithmic processes that we call Markov Chains with Rewinding. In this setting, an algorithm interacts with a (partially observable) Markovian random evolution by strategically rewinding the Markov chain to previous states. Depending on the application, this may lead the evolution to desired states faster, or allow the agent to efficiently learn or test properties of the underlying Markov chain that may be infeasible or inefficient with passive observation. We study the task of identifying the initial state in a given partially observable Markov chain. Analysis of this question in specific Markov chains is the central ingredient in the above cited works and we aim to systematize the analysis in our work. Our first result is that any pair of states distinguishable with any rewinding strategy can also be distinguished with a non-adaptive rewinding strategy (one whose rewinding choices are determined before observing any outcomes of the chain). Therefore, while rewinding strategies can be shown to be strictly more powerful than passive strategies (those that do not rewind back to previous states), adaptivity does not give additional power to a rewinding strategy in the absence of efficiency considerations. The difference becomes apparent however when we introduce a natural efficiency measure, namely the query complexity (i.e., the number of observations they need to identify distinguishable states). Our second main contribution is to quantify this efficiency gap. We present a non-adaptive rewinding strategy whose query complexity is within a polynomial of that of the optimal (adaptive) strategy, and show that such a polynomial loss is necessary in general.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Local Computation Algorithms for Maximum Matching: New Lower Bounds2023
- Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time2023
- Query Complexity of the Metric Steiner Tree Problem2023
- Time-Optimal Sublinear Algorithms for Matching and Vertex Cover2022
- Sublinear Algorithms for (Δ + 1) Vertex Coloring2019
- Constant-Time Approximation Algorithms via Local Improvements2008
- A probabilistic algorithm for k-SAT and constraint satisfaction problems2003
- "Go with the winners" algorithms2002
- Approximating the Minimum Spanning Tree Weight in Sublinear TimeLecture Notes in Computer Science, 2001
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989