Sleeping Reinforcement Learning

We thank the Reviewer for the time spent reviewing our work, and for having appreciated the significativeness of our work. We also thank the Reviewer for the comments on the results which we will use to expand the discussion on the results exploiting the additional page. Below, our answer to the Reviewer's questions.

Could the authors outline any significant technical challenges for the stochastic per-stage regime where the type of the distribution of the action availability is unknown? In particular, why doesn't your current estimation method for $C^{ind}$ works for $C^{markov}$? The distribution does not depend on the episode, so couldn't we simply estimate the conditional probability that an action might be available given the current state, previous state, previous action and previous availability?

We can adapt the design of the estimator for $C^{ind}$ to handle $C^{markov}$ by incorporating conditional probabilities, as the Reviewer correctly suggests. However, we conjecture that the resulting regret bound would remain of the same order (with exponential dependence on $A$) as in our current approach (Theorem 4.1), which relies on the augmented MDP approach. That said, we believe our method allows us to avoid several non-strictly necessary calculations. We will add a comment on that in the paper.

Going back to the exponential dependency on $A$: the lower bound construction in Theorem 4.2 requires the availability to change based on previous availability $\mathcal{A}\_{k,h-1}$. Do you think the exponential dependency on A can be removed if the availability depends only on $s_{k,h}, s_{k,h-1}$ and $a_{k,h-1}$?

Yes, this dependency can be removed in the described scenario and the regret bound we would obtain should be very similar to the independent availability scenario, as the additional complexity in the Markovian case is generated, as the Reviewer properly noticed by looking at the lower bound construction, by the challenge in estimating the transition probabilities over the action sets. We will add a comment on that using the additional page. Thank you for pointing it out.

We thank the Reviewer for the time spent reviewing our paper and for having appreciated the motivation, clarity and novelty of our work. Below, our answer to the Reviewer's comments.

It may be better to also provide a lower bound for the setting of independent per-stage disclosure.

It is possible to also provide a lower bound for the setting of independent per-stage disclosure? I believe this may help better understand the problem.

We thank the Reviewer for giving us the opportunity to elaborate on this. After careful consideration, we argue that a tight lower bound for the independent per-stage disclosure case is the same as that of standard MDPs, i.e., $\mathbb{E}[R(T)] \ge {\Omega}(H\sqrt{SAT})$ (see Domingues et al., 2021). Clearly, the lower bound for standard MDPs is a lower bound for the independent per-stage disclosure case, since the latter includes a smaller class of problems in which all actions are always available, i.e., $C^{\text{ind}}_h(\mathcal{A}|s) = 1$ for every $(s,h) \in \mathcal{S}\times [H]$. Concerning the tightness, we need to carefully compare it with the upper bound of Theorem 5.1. First of all, the lower bound $\mathbb{E}[R(T)] \ge {\Omega}(H\sqrt{SAT})$ (Domingues et al., 2021) is for the expected regret (as customary in the literature), while our upper bound for the per-stage disclosure case of Theorem 5.1 is for the regret in high probability. Thus, we need to convert the latter to the expected regret in order to perform the comparison. To do so, we start from the first regret bound of Theorem 5.1 (disregarding constants and logarithmic terms, but not terms depending on $\delta$):

Notice that by disregarding the dependence on $\delta$ and for sufficiently large $T$, we obtain the second regret bound of Theorem 5.1 (still in high probability). To get the upper bound for the expected regret, we make the choice of $\delta = \frac{2^A}{T}$, whenever $T \ge 2^A$, obtaining (since $R(T) \le T$ always):

The latter is of order $\widetilde{O} \left( H \sqrt{SAT }\right)$ whenever $T \ge \Omega(H^{10}S^5A2^{2A})$. We will adjust the presentation of the result in the final version of the paper, clarifying the difference between expected regret and regret with high probability bounds, and, consequently, the discussion on the result and the future works. Thank you for rising this point.

In Lines 130-132, $V_{ED}^* (A)$, $V_{SD}^*(A)$, $V_{LLC}^*(A)$ are used before definition.

We agree with the Reviewer that (at least) an informal definition is needed also in this part. It was an oversight, we fixed it. Thank you.

Typo in Line 195.

Thanks, we fixed it.

We thank the Reviewer for the time spent reviewing our work. Below, our answer to the Reviewer's questions and concerns.

Is it possible to add some numerical results to verify your results?

To numerically validate the algorithm and show the impact of action availability on performance, we consider a modification of the well-known Frozen Lake environment (https://gymnasium.farama.org/environments/toy_text/frozen_lake/). In the original version, the agent must traverse a frozen lake (i.e., a grid) from a start to a goal position, avoiding holes in the surface (i.e., unavailable positions in the grid). We modify it by letting such holes open and close stochastically (i.e., the unavailability of each position is sampled at each time step from a Bernoulli with parameter $p$). We assume the start and goal to be fixed in the top-left and bottom-right corners of the grid, respectively.

The agent can move up, down, left, right, or stay. If the agent selects an action that would move it to an unavailable state, it stays in the current position. The reward function is defined as follows: the agent receives reward $1$ for state-action pairs that have the goal as next state, and $0$ otherwise. The episode stops at the end of the time horizon (not when we reach the goal state). Given that all positions (except the start, the goal, and the position occupied by the agent) have the same probability of being frozen at any time step, it is easy to see that the optimal policy tries to move along the diagonal that connects the start to the goal. To compute the value of the optimal policy, we perform a Montecarlo simulation for each evaluated setting. We compare our S-UCBVI (Algorithm 7) with standard UCBVI (Azar et al., 2017), observing that the latter interacts with the environment as shown in Figure 1. We compare them in terms of reward, to highlight that both algorithms converge, yet UCBVI converges to a suboptimal objective.

We evaluate grids of size $G \times G$, with $G \in \\{2,3,4\\}$, varying the stochasticity parameter as $p \in \\{0,0.5,0.75\\}$. We consider a time horizon of $H=10$ for each episode and $K= 2 \cdot 10^5$ episodes.

The Reviewer can find the plots of the experiments here:

https://drive.google.com/file/d/19WlZpKUHoSoYxx4PgT3jNLqyfmrm9twu/view?usp=sharing

and the code here:

https://drive.google.com/file/d/1NBoDjr9P_eaUcO1Na4nyzE71q4zgAKwR/view?usp=sharing

As expected, when $p=0$, we observe no performance difference. Instead, as the environment stochasticity increases, we observe a greater gap in the performances of the two algorithms, with S-UCBVI (our algorithm) achieving the optimal value (obtained via Montecarlo simulations as described above), represented as an horizontal line, and UCBVI not reaching such optimum. This is due to the fact that UCBVI cannot observe action availabilities, effectively playing in an environment with a lower optimum.

Is it possible to reduce the bound gaps [...] between Theorem 4.1 and 4.2?

The lower bound of Theorem 4.2 that shows an exponential dependence in the cardinality of the action set represents a statistical barrier in the learning for Sleeping MDPs with Markovian per-stage availability. For this reason, as common in the literature (e.g., MDPs with adversarial transitions [1]), the goal is no longer matching such an exponential lower bound, but rather finding structures (e.g., independent action availability) that overcome such barriers. The result of Theorem 4.1, indeed, has to be interpreted as just an exemplification of the fact that, when accepting such an exponential dependence, the Sleeping MDPs with Markovian per-stage availability can be addressed through the augmented MDP method. We will clarify this in the paper.

[1] Tian, Y., Wang, Y., Yu, T. and Sra, S. Online Learning in Unknown Markov Games. ICML 2021

In the definition of three regrets, is there a typo? I guess $T$ and $K$ should be the same thing, the number of episodes.

We checked and the notation is correct and compliant with (Azar et al., 2017) where $T = KH$ is the total number of interactions (see Section 2), $K$ is the number of episodes and $H$ is the horizon of the single episode.

Is it possible to reduce the lower bound condition for $T$ with a factor $H^{10}$ in Theorem 5.1?

Just like in (Azar et al., 2017), for the UCBVI algorithm and its analysis, it is challenging to remove such a dependence on the horizon $H$ from the minimum $T$ condition. This is exacerbated, in our case compared to (Azar et al., 2017), since we consider stage-dependent transitions (doubling the exponent of $H$). Nevertheless, there exist works [2] that succeed in mitigating such a condition at the price of more complex (and less effective in practice) algorithms. Importing such techniques to the Sleeping MDP setting can be an interesting future work.

[2] Zhang, Z., Chen, Y., Lee, J. D., and Du, S. S. Settling the sample complexity of online reinforcement learning. COLT 2024.