29 problems

A restless multi-armed bandit problem has $N$ projects, of which up to $M$ can be selected at each time, where $1\leqslant M<N$. Each project is modeled as a binary-action Markov d…

Let $S\geq 2$ and $A\geq 2$ be integers, let $D\geq 4\left\lceil\log_A S\right\rceil$, and consider horizon-$T$ algorithms for MDPs with $S$ states, $A$ actions, and diameter at mo…

Consider a sequential decision process, or Markov decision process, with state $s$, action set $\Delta(\mathcal{A}(s))$, successor state $s'$, discount factor $\gamma$, and an empo…

Extension conjecture. The main results obtained for MDPs should extend to generalized ADPs with state-dependent discounting under suitable stability and irreducibility assumptions.

Uniformly mixing complexity conjecture. Theorem should also imply an optimal complexity of $\widetilde{O}(SA\frac{\tau_{\mathrm{unif}}}{\varepsilon^2})$ for this setting by an anal…

Let Heuristic 2 be the renewal-based policy described for the robot example, and let the reward distribution be the particular distribution used in that example. Heuristic 2 optima…

Consider the actual and virtual systems, and let state $1$ be a designated state. Suppose that on every slot the system is forced to revisit state $1$ with some probability…

Let $S^{a}(t)$ and $S^{v}(t)$ denote the states of the actual and virtual systems, respectively, and suppose their conditional transition probabilities and conditional expected cos…

The authors' conjecture. These results are only the first results provided by this new geometric interpretation of MDPs.

Let $M$ denote the number of observed trajectories, and let $\hat{Q}_{10}$ and $\hat{P}$ be, respectively, highly aggregated and more finely aggregated models of the same deteriora…

Uniform absorption conjecture. If $\boldsymbol{\mathcal{O}}$ is $w$-compact, then $\boldsymbol{\mathfrak{M}}$ is uniformly absorbing.

Coverability coefficient conjecture. The coverability coefficient of the underlying MDP and policy class should characterize the instance-dependent complexity of agnostic reinforce…

A reductive process has transition dynamics that can be represented by an upper-triangular structure, while an RMC is a recursive Markov chain. Weak reductivity conjecture. Allowin…

An average-reward Markov decision process is accessed through samples, and an algorithm may choose its samples adaptively based on previous observations. Adaptive-sampling lower bo…

VI-LCB optimality conjecture. VI-LCB is optimal for all ranges of $C^\star$.

Adaptive optimality conjecture. The LCB approach, together with value iteration, is adaptively optimal for solving offline MDPs for all ranges of $C^\star$.

Let $n$ be the number of channels, let $c$ be the switching cost, and let $\boldsymbol{\pi^*}$ denote the policy defined by … Here Case I is the full-observation setting considered…

Consider a non-absorbing random walk on $[1,\ldots,N]$ with two-step coupling, and let the two-step approximation be constructed by matching the two-step conditional mean, so that…

Consider a multi-agent Markov decision process with a tree dependence structure, and let the fast decaying property refer to the property defined for such problem instances in the…

Consider a discounted Markov decision problem and the sublinear-time complexity result of Proposition 3, which uses prior knowledge of the ratio $\frac{c_2}{c_1}$. Generalization c…

Let $\gamma$ be the discount factor of a discounted Markov decision problem, and let the diameter be the maximal expected time to move from any state to any other state. Diameter-c…

Consider a discounted Markov decision problem with discount factor $\gamma$, and let $P^{\pi}$ denote the transition matrix associated with policy $\pi$. Spectral-gap complexity co…

Let $\mathcal{S}$ be the state space of a discounted Markov decision problem, and let $|\mathcal{S}|$ denote its number of states. State-complexity conjecture. The term…

A CVaR Markov decision process has a Bellman equation that is contracting, and let a sampling-based approximate dynamic programming approach be applied to it. Sampling-based approx…

Let $K$ be the number of users and let $TTE$ denote the threshold above which the surplus number of users has negligible effect; at most $E=TTE$ lines can have non-zero entries at…