Multi-Reward Best Policy Identification

We thank the reviewer for their thoughtful review and the time spent on our paper. Below, we address each concern in detail.

I was pushed into first reading other articles to get a rough understanding of what is going on

We acknowledge the current format assumes familiarity with related literature. We will add a background section to make the technique accessible to a broader audience.

How do you compute $U$ in Algorithm 1 without knowing the rewards gaps?

We briefly explain the procedure in lines 178-182 and we do not assume knowledge of the gaps in the algorithm.

We use the current estimate of the model $M_t$ and the set of rewards to compute the sub-optimality gaps. We use the data gathered up to time $t$ to estimate the transition function $P_t$ and perform value iteration for each reward to find the sub-optimality gaps. These estimates are used in place of the true gaps to compute $U$.

This technique is known as "certainty-equivalence" principle, meaning that we use the current estimates as if they were exact when computing $\omega_t^\star$. Note that, as more data is gathered, the estimate of the transition function improves, and $\omega_t^\star$ tends to $\omega^\star$.

I think the algorithms are not sufficiently explained. In the tabular case $M_t$ should be explained in more detail

Currently, the main text provides a brief description: lines 178-182 outline how $M_t$ is updated by estimating the transition function $P_t$, and lines 183-189 explain how to compute the instance-dependent quantities to determine $U$.

In the revised manuscript we will provide a more detailed explanation of the algorithm.

Why is there no dependence on $\alpha$ in the theoretical results?

The main theoretical results are asymptotic in $\delta$, causing $\alpha$ dependence to vanish. Intermediate results do show $\alpha$ dependency (e.g., see Remark C.2, line 1099).

The use of Borel-Cantelli in the proofs is not correct as it is. The events are not independent

We rely on Observation 1 in [70] (in the text of the proof there is a typo, since there is no Lemma 4 in [70]). We use the fact that there exists another stochastic process (the one provided by the forcing policy) such that the sum of the probabilities with which action $a$ is chosen is infinite. This sum lower bounds the sequence of probabilities of selecting action $a$ and satisfies the independence conditions required by the Borel-Cantelli Lemma.

What is the connection of Theorem 3.1 and 3.3?

Both theorems are for MDPs. Deriving Theorem 3.1 requires additional steps compared to the bandit setting, and the optimal allocation $\omega_{opt}$ must satisfy the forward Chapman Kolmogorov equation.

To explain how the two theorems are connected, we consider an information-theoretical approach.

Firstly, note that the optimal exploration strategy induces the stationary distribution $\omega_{opt} =\arg\sup_{\omega \in \Omega(M)} \inf_{r,M'\in Alt(M_r)} \mathbb{E}\_{(s,a)\sim\omega}[{\rm KL}\_{M|M'}(s,a)]$, and $T^\star$ can be interpreted as the average amount of information extracted per time-step from the MDP at stationarity under $\omega_{opt}$.

Secondly, as $T^\star$ is a hard non-convex optimization problem, we instead use $U^\star$ in the design of our algorithm.

As more data is collected, the estimate of the model $M_t$ tends to $M$, and one can show that $\omega_t^\star$ approaches the optimal stationary distribution $\omega^\star$. Asymptotically, the algorithm will visit the MDP according to $\omega^\star$, so the amount of information extracted approaches $U^\star$. Hence, with a proper stopping rule, this is roughly why, as $\delta \to 0$, the sample complexity of the algorithm approaches the value $U^\star$ in Theorem 3.3.

You mention an upper bound for $U$, which has an additional $1/\Delta^2$ compared to the theoretical bound. Is there a better bound?

Please note that also $U$ has a dependency on $1/\Delta_r^2$. In general, we believe that it is hard to find a better dependency in the gaps that does not depend on some specific property of the MDP.

Is there any theoretical understanding on how $\tau$ scales in the number of rewards?

The result in Theorem 3.1 indicates that the scaling depends on the "worst" reward in the considered set. Practically, according to $U^\star$, the sample complexity is dictated by the minimum sub-optimality gap $1/(\inf_{r\in {\cal R}} \Delta_r^2)$ (and $\tau$ will scale as $U^\star \ln(1/\delta)$). This scaling is consistent with the scaling obtained in classical reward-free exploration, see for example [17; A]. In [A], the authors show a similar result in a different setting, where the sample complexity also scales according to the worst reward (with a similar $1/\Delta^2$ scaling, though their gap definition is slightly different).

How does your algorithm compare to just train for one reward after the other? Typically card pole plots show the number of episode, not the number of steps. Does your algorithm help for generalisation?

The optimization problem formulated to compute $\omega^\star$ shows that the scaling depends on the worst-case reward in the set (i.e., the reward with the minimum sub-optimality gap) rather than the number of rewards. Consequently, a sequential exploration process would generally not be optimal (since that would scale according to the number of rewards). Such an approach would likely increase training time and associated costs.

Regarding the Cartpole swing-up experiments, each episode may have a different number of steps. Further note that we use a modified version of the Cartpole swing-up problem, designed to assess the exploration properties of RL algorithms.

Lastly, with a sequential training the ability to generalize may be limited, especially for very different rewards, reducing the effectiveness of such an approach.

Other ref.

[A]. Jedra et al. "Nearly optimal latent state decoding in block mdps." AISTATS 2023.

We thank the reviewer for their feedback and for the time and effort spent reviewing our paper. Below we provide detailed responses to the main concerns raised by the reviewer.

Simple environments for deep RL

We appreciate the reviewer's concern. However, the selected environments are intentionally designed as hard exploration challenges, as referenced in [36,40,43] Additionally, we included experiments for a real-world application in appendix D.3 (a radio network control problem). These experiments show the effectiveness of our algorithm in a realistic environment using an industry-level network simulator.

Optimality is only considered and defined for stationary deterministic policy

For finite MDPs, the optimal policy is stationary and deterministic (see Theorems 6.2.9 and 6.2.10 in [39]). Therefore, in this context, the lower bound holds, and the performance of our algorithm is asymptotically optimal with respect to $U^\star$.

Theoretical guarantees for the deep RL extension

We acknowledge the absence of theoretical guarantees for the deep RL extension. However, our primary goal was to establish a foundational understanding of the multi-reward setting for finite MDPs, which is crucial for building towards more complex cases.

Providing theoretical guarantees for deep RL would merit its own manuscript.

Main technical challenges and novelties of extending the prior results from single-reward RL to multiple-reward RL.

For the lower bound, as in prior work, the proof builds upon classical change of measure arguments. The main difference with respect to the single-reward setting lies in the additional optimization over the set of rewards.

However, there are several differences compared to prior work, highlighted throughout the paper. For example:

1. Concerning the relaxed characteristic rate, deriving a tractable optimization problem for $U^\star$ in presence of a continuous set of rewards is challenging, since the minimum sub-optimality gap can be non-convex (see Sec. B.4 of the appendix). To address this issue, we show that it is sufficient to consider a finite set of rewards. This finding is used in our numerical results (see Sec. D.1.2 in the appendix or Sec. 3.4 in the main text).

2. Regarding the algorithm, we remove the need for an MDP-specific constant in the forced exploration (see line 195), which limited the usability of NaS [17]. We further provide a novel high-probability forced exploration result (see also remark C.2, page 35).

3. Regarding the extension to Deep-RL, prior works in BPI mostly consider the tabular case. Furthemore, the extension of [40] to the multi-reward setting is non-trivial. First, by inspecting $U^\star$, we design an exploration procedure that explores according to the difficulty of the rewards. Secondly, we experimented with various architectural changes of the neural networks to accommodate the multi-reward setting.

I am not fully convinced that reward-free RL cannot solve the concerned scenario [...] reward-free RL is more general and can be useful when it is hard to accurately learn rewards or when rewards are sparse.

As correctly noted by the reviewer, considering a set of known rewards can provide superior performance with respect to the more general reward-free RL setting and this is the main motivation behind our setting.

Determining the best policy for any possible reward is a harder problem that is unlikely to occur in some practical problems. Hence, for applications where there are only a finite number of rewards to optimize, the multi-reward setting would provide a better model choice w.r.t. the reward-free setting. We provide a concrete example of this scenario in Appendix D.3.

Regarding the sparsity of the reward, our method can also handle scenarios with sparse rewards, as demonstrated in our numerical results.

Lastly, while the comparison may not be completely fair, there are currently no other pure exploration algorithms in the multi-reward setting (and reward-free RL is one of the closest to our setting). For this reason, we compare to different reward-free methods, as well as an adaptation to the multi-reward setting of PSRL [35] that we provide in the appendix.

Do we treat MR-BPI as dedicated exploration strategies for multi-objective RL?

The multi-reward setting, as well as reward-free RL, share some similarities to multi-objective RL. In multi-objective RL, one seeks to identify the Pareto frontier of non-dominated policies. This objective is, in general, a significantly harder challenge compared to identifying the optimal policies for a finite set of rewards.

Is there any particular reason for choosing the discounted setting instead of the episodic one?

While most reward-free approaches focus on episodic settings, in practice, many algorithms used in industry employ the discounted setting. Our goal was to strike a balance between providing theoretical results and developing a practical algorithm that practitioners can readily apply.

We believe the discounted setting can be extended to episodic, leveraging recent advances in [A].

Why do we need the canonical basis of rewards? Could you provide a concrete example of ”set of rewards” with your notation?

Each element of the canonical basis is a vector of size $SA$. For example, $e_1$ represents a sparse reward where $r(s_1,a_1)=1$ and $0$ otherwise, expressed in vector form as $e_1 = \begin{bmatrix} 1 & 0 & \dots & 0 \end{bmatrix}^\top$. Similarly, $e_2$ is a reward vector that assigns a reward of $1$ to the second state-action pair and $0$ otherwise.

In some experiments we explored according to this canonical basis of rewards (as previously explained, see also Sec B.4 in the appendix). For a concrete example, we also refer the reviewer to section B.4.1 of the appendix.

Additional references

A. Al-Marjani et al. "Towards instance-optimality in online pac reinforcement learning." arXiv:2311.05638 (2023).

We appreciate the reviewer's feedback and understanding.

However, we have already acknowledged the differences between our work and these other settings (see lines 33-42 and the discussion in Section 5), and we are committed to further clarify the distinction.

We have already extensively compared our approach with reward-free RL in both the tabular and deep settings (both in the main text and in the appendix), as it is the closest existing framework to ours in terms of exploration objective.

Regarding multi-objective RL, we remark that our focus is on a different exploration objective, since we are not interested in identifying the Pareto frontier of non-dominated policies. Currently, there are no best policy identification techniques available for multi-objective RL, making a direct comparison impractical (which would merit a separate, dedicated study).

We hope these clarifications address the reviewer's concerns and help in understanding the scope and contributions of our work.

Thank you for your comments and valuable feedback. We appreciate the time and effort spent reviewing our paper, as well as your positive comments on the comprehensive analysis of theoretical and empirical results.

Below, we address each of your concerns and outline the corresponding revisions we plan to make to improve the paper.

The paper is inspired by [17], but it would be better to explicitly acknowledge this inspiration in the main part [...] a more in-depth discussion of the challenges in proof caused by the novel forcing policy would strengthen the paper’s contribution.

We would like to clarify that we acknowledge this inspiration in multiple points, including at the beginning of Sec. 3 (line 118), Sec. 3.1 (lines 133-134), and Sec. 3.3 (line 172). To further highlight this point we plan to include this sentence in the introduction: "Our work is inspired by [17] for single-reward BPI and extends the results and analysis to the multi-reward setting".

Regarding the challenges in the proof, we agree with the reviewer that expanding on these in the main text would enhance the paper and highlight an important contribution. We have already briefly described how our approach removes the need for an MDP-specific constant in the forced exploration (discussed at line 195), which previously limited the usability of NaS [17]. Due to lack of space, more details on the novelty of the forcing policy were left in the appendix. We will make sure to include these in the main part of the paper by using the extra page in the final version of the paper. More precisely, we will further enhance our discussion by highlighting the challenges addressed in our proof and emphasizing our improved result for the high-probability forced exploration theorem, which we believe is of independent interest.

Even though more details is covered in the appendix, the paper should provide some details on the convex optimization. For example, a discussion of the computational costs [...]. The computational cost of convex optimization may prevent it to deal with large-scale dataset.

We agree with the reviewer that the paper should provide more details on the convex optimization problem defining $U^\star$. We plan to include a subsection discussing the technical aspects of solving the optimization problem in the paper (note that currently in appendix D we provide the total runtime of our simulations), including implementation details and further results on the computational cost.

Lastly, for Deep-RL, our algorithm DBMR-BPI has similar computational complexity as DBMF-BPI [40], or Boostrapped DQN [43] at inference and training time (due to a vectorized implementation of DBMR-BPI).

The abstract would be better if providing a more impressive motivation for multi-reward RL, emphasizing its significance and potential impact.

We appreciate the suggestion and we agree that the abstract could better emphasize the motivation for multi-reward RL. In the introduction, we already highlight the practical importance and potential impact of Multi-Reward RL and its relevance with respect to existing similar settings. For instance, reward-free RL might not always applicable in industry. In some applications, there are only a finite number of rewards to optimize.

To illustrate this aspect concretely, in Section D.3 of the appendix, we present an example of applying DBMR-BPI to a radio network control problem using an industry-level network simulator, demonstrating how current reward-free exploration techniques are limited when the number of rewards is finite.

We will make sure to highlight these aspects in the abstract and include these consideration in the final version of the paper.

Didn’t put some innovative aspects in the main text, leaving vital details to be discovered in the appendix.

We agree with the reviewer that, due to the limitation in space, some important aspects were left to the appendix. We will integrate the main innovative aspects into a dedicated section by using the extra page in the final version of the paper. This section will include a summary of the theoretical and practical contributions, as well as their implications.

The assumption of a unique optimal policy limits the method’s applicability to a broader range of scenarios.

While we agree that the uniqueness assumption may be limiting for a continuous set of rewards, we believe that it is less restrictive when the set of rewards is finite, as it is generally easier to guarantee the uniqueness of an optimal policy in such cases.

Furthermore, note that, as discussed in Appendix A (Limitations section), the assumption on the uniqueness of the optimal policy is common in the BPI literature [18, 16, 17, 40, 20]. Addressing MDPs with multiple optimal policies or identifying $\varepsilon$-optimal policies necessitates the use of more complex overlapping hypothesis tests [67]. We refer the reader to this Appendix for more details and further consideration on this extension.

Lastly, while the theoretical results may require this assumption, in practice we experienced both MR-NaS and DBMR-BPI to perform well in the numerical experiments even in presence of multiple optimal rewards.