1 Introduction↩︎

4pt

Reinforcement Learning [2] is a popular tool for learning an optimal decision policy through sampled interactions with a Markov Decision Process (MDP), a general framework encompassing countless applications, ranging from robotics [3], [4] to algorithms design [5], conversational agents [6], and others.

Although powerful, the efficiency of RL is a long-standing issue. The theory says that the regret of a RL algorithm, i.e., the difference between the value of the deployed policy and the optimal policy in hindsight, inescapably scales with \(\sqrt{H}\) in the worst case [7], [8], \(H\) being the total number of episodes of interactions with the MDP. Even if the real world is arguably better behaved than the worst-case MDP, the most successful algorithms [9], [10] still take thousands of interaction episodes to learn a competitive policy in simulation, which draws pessimism for RL to be applied for learning in the real world.

A promising direction to improve RL efficiency is meta RL [11], in which a distribution over the set of tasks we can face is considered. In meta RL, we first have a training phase on some tasks sampled from the latter distribution, for which the learning efficiency is less of an issue (e.g., a simulator is available). Then, we exploit the collected knowledge to achieve faster learning in a test task, which is assumed to come from the same distribution.

Much of the previous work in meta RL focuses on algorithms for the training stage [12]–[16], or analyse generalization of the trained model to the test task [17]–[21].

Here we study meta RL from a different perspective. We assume to have spent infinite time in the training phase, such that the task distribution can be recovered (we mean the full specifications of all the MDPs in the set, not just the task distribution itself), and we aim to minimize the regret against the optimal policy in the test task. Especially,

Does perfect meta RL training provably improve the learning efficiency on the test task against standard RL?

We believe that a positive answer is an essential theoretical ground for motivating meta RL, as there is little incentive to undergo a costly training (at least in terms of computation) without guarantees of improved efficiency on the test task.

Even in simple settings, in which the distribution is supported on a finite set of \(M\) tasks, meta RL provides little hope, as the regret still scales with \(\sqrt{H}\) in the worst case, with only marginal gains in the statistical efficiency w.r.t. standard RL [1], [22]. Nonetheless, under a common separation assumption on set of tasks [1], [23], i.e., there exists at least one reachable state-action pair that reveals one task against the others, the prospects of meta RL become brighter. [1] show that \(\mathcal{O}(M^2 \log (MH))\) regret can be achieved by first identifying the test task (with high probability) and then deploying the best policy for the latter. Their approach is somewhat wasteful in the identification, as the algorithm performs a sequence of one-vs-one tests on candidate tasks, which induces the \(M^2\) factor. However, it is unclear if the latter is necessary or better algorithms could be developed.

In this paper, we provide a nuanced study of the statistical barriers of test-time regret minimization in meta RL. First, we provide a lower bound \(\Omega (TM \log(H))\) for test-time regret minimization under separation, where \(T\) is the horizon of an interaction episode with the test MDP. Our lower bound demonstrates that the “wasteful” algorithm by [1] is nearly optimal and one factor \(M\) is unavoidable under separation alone. The way the lower bound is derived philosophically confirms that probing the MDP to first identify the test task and then exploit the collected information is not just reasonable but also optimal. Nevertheless, we note that a linear dependence with \(M\) is not desirable if we aim to scale meta RL to large task distributions.

Thus, we formulate stronger yet reasonable requirements under which the latter limitation may be overcome. To formalize our desiderata, we call strong identifiability a family of assumptions that allow for fast rates in \(H\) and \(M\) simultaneously, for which we provide three instances.

The first assumes the tasks can be partitioned in coherent clusters, such that the algorithm can efficiently identify the cluster to which the test task belongs, and then identify the latter within that cluster down the hierarchy. Clusters are fairly natural in practice, e.g., in a meta RL problem applied to movie recommendation systems, in which the set of tasks consists of different users with specific tastes. We could first provide recommendations to probe whether the test user especially likes a movie genre, and then provide fine-grained recommendations within the genre catalogue.

The second assumes that the test task can be identified following a tree structure. This means that the algorithm can split a subset from the current set of candidate tasks by collecting information on a single state-action pair, which allows to eliminate a large chunk of candidates at every iteration. This may happen in practice whenever the test task can be identified testing a sequence of revealing characteristics.

The third strong identifiability assumption we analyse is admitting the presence of a small number of revealing policies, which allow for collecting highly informative data irrespective of the test task, then to perform the identification without further interactions. To provide intuition on such policies, let us think of a meta RL problem in which the set of tasks consists of morphologies of terrains we aim to explore without daylight. A revealing policy would light a torch to probe the surroundings before taking the right direction for the test morphology.

Contributions.   Our main contributions are:

• We revise an analysis of domain randomization [1] through the lenses of meta RL, adapting their result on sim-to-real gap into a regret upper bound \(\mathcal{O}(M^2 \log(M H))\) for our setting (Section 3);

• We derive a lower bound \(\Omega (TM \log(H))\) to test-time regret minimization under separation (Section 4) through original techniques that formally link our problem to Best Policy Identification [24]. The proof requires a tailored lower bound to the sample complexity of BPI, which can be of independent interest (Appendix 9);

• We present structural assumptions beyond separation, called strong identifiability (Section 5). Those include: A clustering assumption that leads to a regret upper bound of order \(\mathcal{O}(T (K^2 + N^2) \log(N H))\), where \(K\) is the number of clusters and \(N\) is the size of the largest cluster; A tree structure assumption that leads to a regret of order \(\mathcal{O}(T d \log (d H) )\), where \(d = \log_{1 / \beta} M\) is the depth of the tree and \(\beta\) is the splitting factor; A revealing policies assumption that leads to a regret of order \(\mathcal{O}(T I \log (M H))\), where \(I\) is the number of revealing policies;

• We provide additional sharp rates to the test-time regret for meta learning in bandits (Appendix 10).

Complete proofs of the theorems are in Appendix 8.

2 Problem Formulation↩︎

We first present the necessary background on MDPs and meta RL (Sections 2.1, 2.2) before formulating the learning problem we will address in the paper (Section 2.3).

Notation.  Let \(\mathcal{A}\) a space of size \(|\mathcal{A}|\) with elements \(a \in \mathcal{A}\). Then, \(\mathcal{P}(\mathcal{A}) := (p \in [0, 1]^{|\mathcal{A}|} | \sum_{a \in \mathcal{A}} p(a) = 1)\) is the simplex for a finite \(\mathcal{A}\). Let \(p, q \in \mathcal{P}(\mathcal{A})\), their \(\ell 1\)-distance is \(\| p - q \|_1 = \sum_{a \in \mathcal{A}} |p (a) - q(a)|\), their total variation is \(\mathop{\mathrm{TV}}(p, q) = \sup_{a \in \mathcal{A}} |p(a) - q(a)|\), their Kullback-Leibler divergence is \(\mathop{\mathrm{KL}}(p, q) = \sum_{a \in \mathcal{A}} p(a) \log (p (a) / q(a))\) and \(\mathop{\mathrm{KL}}_{p | q} := \mathop{\mathrm{KL}}(p, q) + \mathop{\mathrm{KL}}(q, p)\). We will denote sets and sequences as \((a_i)_{i \in [I]} := (a_1, \ldots, a_I)\), where \([I] := (1, \ldots, I)\) for some constant \(I \in \mathbb{N}\).

2.1 Markov Decision Processes and RL↩︎

A finite-horizon time-homogeneous Markov Decision Process [25] is defined by a tuple¹ \(\mathcal{M}_i := (\mathcal{S}, \mathcal{A}, p_i, r_i, s_1, T)\) where \(\mathcal{S}\) is a finite set of states (\(S = |\mathcal{S}|\)), \(\mathcal{A}\) is a finite set of actions (\(A = |\mathcal{A}|\)), \(p_i: \mathcal{S}\times \mathcal{A}\to \mathcal{P}(\mathcal{S})\) is a transition model such that \(p_i (s' | s, a)\) denotes the conditional probability of transitioning to \(s'\) taking action \(a\) in state \(s\), \(r_i: \mathcal{S}\times \mathcal{A}\to [0, 1]\) is a reward function such that \(r_i (s, a)\) is the reward collected by taking action \(a\) in \(s\), \(s_1\) is the initial state,² and \(T < \infty\) is the horizon of an episode.

An episode of interaction between an agent and the MDP \(\mathcal{M}_i\) goes as follows. At each step \(t \in [T]\), the agent observes \(s_t \in \mathcal{S}\) and takes \(a_t \in \mathcal{A}\). The environment transitions to \(s_{t + 1} \sim p_i (\cdot | s_t, a_t)\) and the agent collects \(r_i (s_t, a_t)\). Hence, an episode can be summarized through a sequence \(\tau = (s_t, a_t)_{t \in [T]}\) called a trajectory.

The agent selects its actions by means of a non-stationary Markovian policy \(\pi := (\pi_t: \mathcal{S}\to \mathcal{P}(\mathcal{A}))_{t \in [T]} \in \Pi\) where \(\pi_t (a | s)\) denotes the conditional probability of action \(a\) in state \(s\) at time step \(t\), and \(\Pi\) is the set of policies. We define the value at step \(t\) of playing policy \(\pi\) in state \(s\) of \(\mathcal{M}_i\) as \[V_{it}^\pi (s) := \mathop{\mathrm{\mathbb{E}}}_{\pi, \mathcal{M}_i} \left[ \sum_{ t' = t}^T r_i (s_{t'}, a_{t'}) \;\Big| \;s_t = s \right],\] where the expectation is on all the sources of randomness, i.e., the action selection induced by \(\pi\) and the state transitions induced by \(p_i\), which may be stochastic. We further denote \(V_i (\pi) := V_{i1} (s_1)\) the value of the policy in the initial state. The objective function of the agent in \(\mathcal{M}_i\) can then be written as \(\max_{\pi \in \Pi} V_i (\pi)\), where we denote as \(\pi^*\) the policy attaining the maximum and \(V^*_i := V_i (\pi^*)\). RL [2] is a paradigm for learning an (approximately) optimal policy \(\pi\), such that \(V_i^* - V_i (\pi) \leq \epsilon\) for some \(\epsilon > 0\), from sampled interactions with an unknown MDP \(\mathcal{M}_i\).

2.2 Meta Reinforcement Learning↩︎

Meta RL [12], initially introduced by [26], extends the RL paradigm to a set of \(M\) MDPs \(\mathcal{M}:= (\mathcal{M}_i)_{i \in [M]} = (\mathcal{S}, \mathcal{A}, p_i, r_i, s_1, T)_{i \in [M]}\) having the same \(\mathcal{S}, \mathcal{A}, s_1, T\), but possibly different transition model \(p_i\) and reward \(r_i\). Just like in RL, the latter MDPs are typically unknown to the agent. In a process called training, the agent can collect interactions with a number of tasks³ drawn from \(\mathcal{M}\) according to a task distribution \(P \in \mathcal{P}(\mathcal{M})\) such that the probability of drawing \(\mathcal{M}_i\) is \(P(\mathcal{M}_i)\). In training, the agent collects information into a prior model, e.g., a policy, a model of transitions, or an algorithm, that is then used to address a RL problem on a test task \(\mathcal{M}_i\) assumed to be drawn from the same task distribution \(P\).

Bayesian RL [11] formulates the target of the training as learning a Bayes-optimal policy⁴ \(\pi_{\text{BO}}\in \mathop{\mathrm{arg\,max}}_{\pi \in \Pi} \mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_i \sim P} [V_{i} (\pi)]\) under the distribution \(P\). As we describe below, here we study meta RL from a frequentist perspective rather than a Bayesian formulation.

2.3 Test-Time Regret Minimization↩︎

In this paper, instead of focusing on the training phase of meta RL, we assume perfect knowledge of the set of tasks \(\mathcal{M}\), such that every transition model \(p_i\) and reward \(r_i\) are fully known to the agent. With this prior knowledge, we aim to minimize the test-time regret over \(H\) episodes \[\label{eq:test-time-regret} R_H (\mathcal{M}_i, \mathbb{A}) := \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{h = 1}^H V^*_i - V_i (\pi_h) \right]\tag{1}\] where \(\mathcal{M}_i \in \mathcal{M}\) is any test task, \(\pi_h\) is the policy deployed in episode \(h\) by algorithm \(\mathbb{A}\), and the expectation is over realizations of the episodes \(1, \ldots, H\) taken from \(\mathcal{M}_i\). The motivation for this objective is that comparing against the optimal policy for the test task, instead of an optimal policy on average over the task distribution [22], gives a regret measure that is robust to the worst-case task, arguably a minimal requirement given the perfect training assumption. We see the latter as a necessary first step towards a more realistic setting with approximate knowledge of \(\mathcal{M}\) only. If we cannot succeed with the former, the latter is hopeless.

Two other important observations are in order. First, in this paper we study the regret of adaptive algorithms \(\mathbb{A}\), that is, the deployed policy is Markovian within an episode, but can change from episode to episode. This is only slightly restrictive as the policy \(\pi_h\) is computed having the full history of realizations in previous episodes \(\mathcal{H}_h = ((s_{t,h},a_{t,h},r_{t,h})_{t \in [T]})_{h' \in [h]}\), which means an algorithm \(\mathbb{A}\) corresponds to a non-Markovian policy with low switching cost [27]. Second, the expression in 1 is different from the notion of Bayesian regret that is common Bayesian RL [11], in which the regret is taken in expectation over the task distribution \(P\) instead of taking the worst-case task. As a result, the optimal algorithm \(\mathbb{A}\) for the test-time regret does not correspond to the Bayes-optimal policy in general, although it holds \(R_H (\mathcal{M}_i, \pi_{\text{BO}}) = \mathcal{O}( M \cdot R_H(\mathcal{M}_i, \mathbb{A}))\) for any algorithm \(\mathbb{A}\) from [1].

3 Previous Fast Rates for Test-Time Regret↩︎

In this section, we discuss the known results for the test-time regret minimization objective we described above. In this paper we especially care for fast rates, i.e., those settings in which the knowledge of the set of tasks and its structure allow to overcome the statistical barrier for regret minimization in finite-horizon RL, which we know is of order \(\Theta(\mathsf{poly}(T, S, A)\sqrt{H})\) from lower bounds and minimax algorithms [8], [28].

[1] address a regret minimization problem that is very close to our test-time regret formulation, although their narrative is centered around domain randomization rather than meta RL. When the set of tasks is finite, they provide a lower bound of order \(\Omega (\sqrt{D M H})\), in which \(D\) is the diameter of a communicating infinite-horizon MDP [1].⁵ The latter result demonstrates that additional assumptions are needed to break the \(\sqrt{H}\) barrier of RL.

To this end, [1] introduce a separation condition within the set of tasks \(\mathcal{M}\). Formally,

The latter assumption guarantees the existence of a revealing state-action pair to tell apart a task from another. This allows to design an algorithm which repeatedly tests that revealing state-action pair to identify the test task efficiently. First, we need to further make sure that the revealing state-action can be reached with meaningful probability.⁶

With the combination of the latter assumptions, we can directly adapt the algorithmic solution in [1] to the finite-horizon setting.⁷ We report the pseudocode of the resulting procedure in Algorithm 1.

The procedure consists of two stages: An “Identify” stage aiming at identifying the test task with high probability (lines 2-11) and a “Commit” stage in which the collected information is exploited (line 12). The “Identify” stage works as follows. At each iteration, a pair of MDPs are drawn from the set of potential test tasks (line 3). A sampling routine (Algorithm 2) is invoked (line 5) to collect samples from the state-action pair where the transition models of the two tasks differ the most (see line 4). The collected information is used to eliminate the task that is less likely to be the test task within the drawn pair (lines 6-10). The “Identify” stage ends when the set of potential tasks \(\mathcal{D}\) is reduced to a single candidate. The “Commit” stage then runs the optimal policy of the candidate task for the remaining episodes.

We can provide the following regret upper bound for Algorithm 1 by adapting [1].

The latter result is promising as it provides a fast rate with only logarithmic dependencies on \(H\), but it also scales super-linearly with the size of the set \(\mathcal{M}\), which is less than ideal for larger task sets. A natural question that arises is whether this is the best we can achieve under the considered separation condition. The latter is arguably a very important question as the separation condition is the minimal structural assumption that makes test-time regret minimization “interesting”, statistically separating the problem from RL. In the next section, we provide an answer through a lower bound specifically designed for this setting.

4 A Lower Bound for Test-Time Regret Minimization under Separation↩︎

In this section, we analyze the statistical barrier for test-time regret minimization under separation (Assumption 1) by providing a novel lower bound. Formally,

Interesting observations come through the lenses of the result above. The lower bound shows that the regret rate of Algorithm 1 [1] matches the optimal dependencies in \(H, T\) factors, while it nearly matches the dependencies with \(\lambda\) and the size of the set of tasks \(M\). The factor of \(1 / \lambda\) is not surprising, tying the complexity of the problem to how hard it is to distinguish one task from another. The result has a fairly negative flavor on the dependency with \(M\) instead. It demonstrates that the regret of any algorithm achieving fast rate \(\log (H)\) has to scale at least linearly with \(M\) under separation, essentially implying that those algorithms are unfit for large sets of tasks.

Unfortunately, the latter settings in which the size of \(\mathcal{M}\) may grow exponentially with the size of the tasks, or even be infinite (e.g., when tasks are continuous), are extremely relevant in practice, and it is arguably where the promises of meta RL for improved efficiency are the most enticing.

An open question remains on whether there exist relevant meta RL settings in which the structure of the problem can be further exploited to achieve fast rates \(\log(H)\) while avoiding the dependence with \(M\). In the next section, we discuss structural assumptions that go beyond the separation condition and allow to obtain the most efficient algorithms for test-time regret minimization.

Before that, we briefly sketch the main components of the proof of Theorem [thr:mdp95lower95bound], which make use of original techniques and constructions that may be of independent interest. We defer thorough derivations to Appendix 8.2. Note that a gentler introduction to the lower bound in the meta bandit setting is reported in Appendix 10.

4.1 Proof Sketch↩︎

The key to our proof is to design a hard instance that links test-time regret minimization to the problem of best policy identification [24], and then invokes a lower bound to the sample complexity of the latter to derive the result. While instance-dependent lower bounds of this kind exist in the literature [29]–[31], as a preliminary step we derive a result that is specifically tailored to our setting. Here we do not report derivations, which are non-trivial adaptations from a lower bound for BPI in infinite-horizon MDPs [29]. We leave a detailed description to Appendix 9.

In Figure 3, we report a visualization of the instance constructed to derive the lower bound, which consists of \(M\) MDPs having \(2M + 3\) states and \(2\) actions each, a high-rewarding state \(s_H\), and an absorbing state \(s_L\) with zero reward. It is easy to see that the optimal policy for \(\mathcal{M}_i\) goes to the state \(s_i\) and then takes action \(a_1\), which gives the highest probability to visit \(s_H\). However, taking action \(a_1\) in every other state \(s_j \in (s_1, \ldots, s_M) \setminus s_i\) is only slightly sub-optimal, meaning that regret minimization is hard. Instead, it is easier to identify the test task \(\mathcal{M}_i\) first, by playing action \(a_1\) in the states \(s_j \in (s_{M + 1}, \ldots, s_{2M})\), for which at least one \((s_j, a_1)\) pair is guaranteed to reveal the test task against any other, and then to play the optimal policy thereafter. To formalize the latter intuition, we note that identifying the test task is equivalent to a BPI problem for this instance and we center the proof around the event \[\mathcal{E} := \big\{\text{``best policy is identified within H episodes''}\big\}.\] Then, we show that the regret is lower bounded by \(\Omega (\sqrt{H})\) when \(\mathcal{E}\) does not hold, which implies that solving the BPI problem is necessary to obtain the best rate.⁸ At this point, we invoke the BPI lower bound in Lemma 3, which simultaneously guarantees that \(\mathcal{E}\) holds with probability at least \(1 - \delta\) and that the regret is lower bounded by \[R_H (\mathcal{M}_i, \mathbb{A}) \geq \mathop{\mathrm{\mathbb{E}}}[\tau] \Delta_2\] where \(\mathop{\mathrm{\mathbb{E}}}[\tau] \geq TM / \lambda^2 \log (1 / 2.4 \delta)\) is the sample complexity of the BPI problem on the constructed instance and \(\Delta_2 := V^*_i - V (\pi) = \log (H) / \sqrt{H}\) is the value gap of playing a sub-optimal policy to identify the task. Theorem [thr:mdp95lower95bound] is obtained through additional algebraic manipulations.

5 Strong Identifiability: Beyond Separation for Faster Rates↩︎

In the previous section, we have settled the statistical complexity of test-time regret minimization in meta RL with a finite set of tasks under a common separation condition (Assumption 1 has been previously considered in [1] as is, while a stronger version of the condition has been used in [23]).

Especially, we provided a lower bound to the test-time regret of order \(\Omega (T M \log (H) / \lambda)\) and we showed that an “Identify-then-Commit” strategy [1] leads to a nearly matching upper bound \(\mathcal{O}(T M^2 \log(M H) / \lambda^4)\). Most importantly, our analysis shows that a linear dependence with the size \(M\) of the set of tasks cannot be avoided under the considered separation condition, at least if we aim for a fast rate in \(H\). In this section, we present stronger yet reasonable assumptions that allow for faster rates of the test-time regret. These assumptions implicitly discriminate the problem instances, which we call strongly identifiable, that are truly worth framing into a meta RL paradigm, as the latter provides undeniable statistical benefits over RL.

Next, we provide three instances of strong identifiability, with specialized algorithms and corresponding analyses, while investigating a broader range of strongly identifiable problems is an interesting directions for future works.

5.1 Meta RL with Clustering↩︎

Let us assume that the tasks in \(\mathcal{M}\) can be grouped in coherent clusters admitting a peculiar and testable property that allows to efficiently discriminate one cluster from the others. Formally,

Further, we consider a slightly stronger reachability condition within a cluster, which essentially assures that a state can be reached throughout the cluster with the same policy.

The combination of latter assumptions allows to take a different algorithmic approach w.r.t. the standard separation condition (Assumption 1). Essentially, we can split the “Identify” stage of Algorithm 1 into two separate phases: First, we identify the cluster to which the test task belongs with high probability, then, we call Algorithm 1 to identify the test task within the cluster selected in the previous step. We call this procedure “Double-Identify-then-Commit” to underline the two-phase structure of the “Identify” stage. We report the pseudocode of the procedure in Algorithm 4.

Since both the number of clusters \(K\) and the size of each cluster are smaller than the size \(M\) of the set of MDPs \(\mathcal{M}\) under Assumption 3, the set of MDPs is strongly identifiable. Thus, we can expect the “Identify” stage of Algorithm 4 to be more efficient than the same stage of Algorithm 1 taking \(\mathcal{M}\) as input, which is confirmed by the result below.

While the latter proves a significant speed-up of the “Identify” stage, which can be relevant in practical settings, the regret does not essentially escape the quadratic dependency on the number of tasks \(M\). Indeed, if we look into the rate we get \(K^2 + N^2 \approx K^2 + M^2 / K^2\) as opposed to \(M^2\) with the separation condition (Assumption 1) alone. At this point, it is interesting to ask which kind of structure can lead to a regret rate that is truly sublinear in the number of tasks \(M\). In the next section, we achieve that by considering a tree structure on the set of MDPs \(\mathcal{M}\).

5.2 Meta RL with a Tree Structure↩︎

Let us suppose that for any set of candidate test MDPs we extract from the original set there always exist a state-action pair from which we can collect information to split the candidates in two subsets. For instance, we can think of a set of indoor physical domains with peculiar configurations, e.g., some with a window on the right-hand side and some without. If those states not only exist, but they are also easy to reach, we can then sequentially split the original set of MDPs to increasingly smaller subsets, until a single candidate remains. To formalize this intuition, we first define what we mean for a state-action to be easy-to-reach.

Then, we can formally define our structural assumption.

The latter induces a tree structure on the set of MDPs, such that we can render the identification problem as traversing a (binary) decision tree. The routine works as follows, we start with the initial set of MDPs \(\mathcal{M}\), then we look for a state-action pair inducing a large enough split, which we visit several times to understand whether the test task belongs to \(\mathcal{D}^+\) or \(\mathcal{D}^-\). We can iterate these steps again on the resulting set, i.e., \(\mathcal{D}^+\) or \(\mathcal{D}^-\), so that the set of candidate MDPs iteratively shrinks towards one single MDP, which is our candidate test task for the remaining episodes. The pseudocode for the procedure is reported in Algorithm 5.

Clearly, the cost of the “Identify” stage of Algorithm 5, i.e., the number of times the while loop between lines 2-12 has to be executed, is tied to the depth of the tree structure, which is \(\log_{1 / \beta} (M)\) in the worst case. With this consideration, we can derive the following regret upper bound.

5.3 Meta RL with a few Revealing Policies↩︎

What happens if we assume that we can extract from \(\mathcal{M}\) a small set of revealing policies that allow to traverse all of the revealing state-action pairs in expectation? We formalize this intuition in the following assumption. Then, we provide an algorithm and corresponding regret analysis that shows the quadratic dependence with \(M\) can be escaped.

Before stating the assumption, we define the set of revealing state-action pairs \(\overline{\mathcal{S}\mathcal{A}} \subseteq{\mathcal{S}\times \mathcal{A}}\) such that \(\forall \mathcal{M}_i, \mathcal{M}_j \in \mathcal{M}, \exists (s,a) \in \overline{\mathcal{S}\mathcal{A}} : \| (p_i - p_j) (\cdot | s, a) \|_1 \geq \lambda\). Then,

In Algorithm 6, we report the pseudocode of a procedure that exploits Assumption 7 to increase the efficiency of the data collection for the “Identify” stage. First, the policies in \(\Pi_I\) are repeatedly deployed with the goal of collecting \(n\) samples for each revealing state-action pair in \(\overline{\mathcal{S}\mathcal{A}}\) within an “Explore” stage (lines 3-11). Then, differently from previous approaches, the “Identify” stage (lines 13-21) is carried out offline with the previously collected data, until the set of tasks \(\mathcal{D}\) is reduced to one candidate. Finally, in the “Commit” stage (line 22), the optimal policy \(\hat{\pi}\) in the identified test task \(\hat{\mathcal{M}}\) is deployed for the remaining episodes.

Now, we provide an upper bound to its test-time regret.

The latter result provides a fast rate for the test-time regret when \(I < M^2\), i.e., the problem is strongly identifiable. However, Algorithm 6 takes a set of revealing policies as input, leaving to the training phase the burden of providing it. Here we discuss briefly how this requirement can be avoided, while we leave as future work a thorough investigation.

Sampling from revealing policies.   Instead of pre-computing a set of revealing policies, one may try to replicate the sampling of the “Explore” stage (lines 3-11) while interacting with the test task. In Algorithm 7 we describe an adaptive sampling procedure for this purpose. The idea is to iteratively compute a policy that maximizes the (expected) visitation of the revealing state-action pairs left uncovered. The latter objective can be encoded into a trajectory reward defined as in line 4. Once such a policy is computed (line 5), it can be deployed in the test task to collect a trajectory (line 6) and to update the set of the remaining state-action pairs to be covered (line 7). The process repeats until of the revealing state-action pairs have been visited (lines 3-9).

To implement Algorithm 7, two technical hurdles have to be overcome. First, the trajectory reward in line 4 is non-standard. A naive solution is to encode in the state space the necessary information to define the reward on a state level or, alternatively, to adapt algorithms to deal with trajectory rewards [32], [33]. Secondly, the problem in line 5 is akin to a robust MDP, which is known to be intractable in general [34]. To address the latter, a policy gradient method [35] can be used to get an approximate solution efficiently, although this may slow down convergence of the while loop (lines 3-9) as opposed to deploying (in line 6) the exact solution of the problem.

6 Related Works↩︎

While we are not aware of any previous work explicitly addressing test-time regret minimization under perfect training within the meta RL paradigm, slight variations of our problem setting have been considered in different domains.

As we extensively reported in the previous sections, [1] provides theoretical results on the sim-to-real gap in domain randomization that can be transferred to our setting almost verbatim. Their sim stage coarsely correspond to our training, while their real stage is our test task, for which they study a notion of regret against the optimal policy specific to the task. Differently from our setting, they consider infinite-horizon MDPs and they analyse the regret rate of a Bayes-optimal policy instead of our adaptive algorithms. Notably, they assume to have recovered an exact Bayes-optimal policy from simulations, which is similar in nature to our perfect training assumption. In their setting of interest, they provide regret guarantees of order \(\mathcal{O}(M^2 \log (MH))\) for finite set of tasks under separation, \(\mathcal{O}(M^2 \sqrt{H})\) for finite set of tasks without separation, and \(\mathcal{O}(\sqrt{d_E H})\) for infinite set of tasks with function approximation, where \(d_E\) is the eluder dimension of the function class. Finally, they provide a lower bound \(\Omega (H)\) for finite sets without separation. We fill the gaps in their analysis providing a lower bound specialized for the separation condition and assumptions beyond separation for faster rates.

The work by [22] studies generalization guarantees of pre-training in RL, in terms of Bayesian and frequentist regret, zero-shot generalization or with additional test-time interaction. The latter setting in the frequentist regret formulation is the analogous to our test-time regret minimization, for which they provide a policy-collection elimination algorithm with regret of order \(\mathcal{O}(\sqrt{\mathbb{C} (P) H})\), where \(\mathbb{C} (P)\) is a measure of complexity of the task distribution. Although the complexity \(\mathbb{C} (P)\) can capture structured finite or infinite set of tasks, it does not allow for escaping the \(\sqrt{H}\) regret of standard RL.

[23] address regret minimization in Latent MDPs (LMDPs). In their setting, at every episode a task is drawn from a set of finite but unknown tasks, for which the agent tries to minimize the regret against an optimal policy for the specific task. Essentially, LMDPs formalism can be seen as a variation of our setting in which the test task is not persistent but changes at every episode, and the agent does not have full knowledge of the transition dynamics of the tasks, which have to be estimated from samples. In its full generality, LMDPs are statistically intractable. Analogously to our work, they consider a (stronger) version of the separation condition to achieve a regret rate of order \(\mathcal{O}(\sqrt{MH})\) for their inherently harder setting. Further variations of LMDPs have been studied, including reward-mixing MDPs [36], [37], analogous of LMDPs with fixed dynamics but changing rewards, LMDPs with side information partially revealing the current task [38], and mixture of MDPs [39].

7 Conclusion↩︎

In this paper, we provided a formal study on the statistical barriers of test-time regret minimization under strong structural assumptions, shedding light on when meta RL can be expected to provide significant benefits over standard RL.

First, we settled the complexity of test-time regret minimization under separation deriving a lower bound specialized for the assumption, for which only upper bounds were known in the literature. Then, to overcome the (super)linear dependency with the size of the set of tasks, we studied a family of structural assumptions beyond separation, i.e., the set of tasks can be grouped in coherent clusters, the test task can be identified following a tree structure, or a small set of revealing policies can be deployed to identify the test task.

Future works may extend our results in various directions. Additional structural assumptions fitting in the broad family of strong identifiability may be investigated, as well as separation conditions at the level of trajectory generation processes rather than single state-action pairs. Understanding the impact of approximate training, i.e., only imperfect estimates of the tasks’ transition dynamics are available, on our test-time regret minimization results is important to bring our analysis in a more realistic setting. Whether there exists minimal assumptions that allow for fast rates of order \(\log (H)\) for infinite set of tasks is also a question worth investigating.

Finally, we hope that our theoretical study can bring inspiration to design practical algorithms for improved efficiency of test-time learning in meta RL.

Acknowledgments↩︎

This research was Funded by the European Union (ERC, Bayes-RL, 101041250). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them.

The authors thank Shie Mannor for insightful discussions on an early draft of this work.

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

8 Missing Proofs↩︎

In this section, we provide complete derivations to prove the theoretical results presented in the paper.

8.1 Proof of Theorem [thr:mdp95upper95bound95separation]↩︎

Here we prove the upper bound to the test-time regret under separation of Algorithm 1, which is a straightforward adaptation of the derivations in [1] to the finite-horizon setting.

8.2 Proof of Theorem [thr:mdp95lower95bound]↩︎

Here we provide complete derivations for the proof of the lower bound to the test-time regret under separation, which we briefly sketched in Section 4. In the proof, we will refer to the hard instance depicted in Figure 3 of the main paper.

8.3 Proofs of Section 5↩︎

Here we report the proofs for the test-time regret upper bounds provided in Theorem [thr:mdp95upper95bound95clustering], [thr:mdp95upper95bound95tree], [thr:mdp95upper95bound95revealing95policies], respectively.

9 Best Policy Identification in Finite-Horizon MDPs: A Tailored Lower Bound↩︎

In Best Policy Identification [24], the learner interacts with an unknown MDP \(\mathcal{M}_i\) with the goal of minimizing the expected number of samples to be taken in order to tell an optimal policy \(\pi^* \in \mathop{\mathrm{arg\,max}}_{\pi \in \Pi} V_{i} (\pi)\) for \(\mathcal{M}_i\) with probability at least \(1 - \delta\), where \(\delta \in (0, 1)\) is a fixed confidence.

The literature provides theoretical guarantees on the latter expected number of samples, called sample complexity, in a variety of settings ranging from worst-case results for discounted [40], [41] and finite-horizon MDPs [42]–[45] to instance-dependent analyses [29]–[31], [46]–[48].

For the purpose of deriving a lower bound for test-time regret minimization (Theorem [thr:mdp95lower95bound]), we use, as a building block, an instance-dependent, non-asymptotic lower bound to the sample complexity of any \(\delta\)-PC (Probably Correct) BPI algorithm in finite-horizon MDPs.¹² To the best of our knowledge, the only result of this kind is given in [31]. Here we derive an alternative result that is tailored to our setting, i.e., in which the set of possible MDPs is restricted to a finite set \(\mathcal{M}\) fulfilling the \(\lambda\)-separation (Assumption 1).

9.0.0.1 Additional Notation.

Let \(\mathcal{H}_h := (s_t, a_t, r_t)_{t \in [T]}\) be a trajectory collected by executing a policy \(\pi_h\) at the episode \(h\). We denote \(\mathcal{F}_h := \sigma((\mathcal{H}_{h'})_{h' \in [h]})\) the sigma algebra of the trajectories up to episode \(h\), such that \((\mathcal{F}_{h'})_{h' \in [h]}\) is the corresponding filtration. We define

• \((\pi_{h'} : \mathcal{F}_{h' - 1} \to \mathcal{P}(\mathcal{A}))_{h' \in [h]}\) a sampling rule that determines the policy to be run at each episode given the past observations;

• \(\tau\) a stopping rule that gives the time at which the sampling process is stopped given past observations;

• \(\hat{\pi}_\tau \in \Pi\) a decision rule, which is the policy selected when \(\tau\) is triggered, i.e., the best guess on the optimal policy given past observations.

We denote as \(\mathop{\mathrm{\mathbb{E}}}[\tau]\) the sample complexity of the BPI problem. Notably, the identification can span several episodes of our finite-horizon MDP setting, which means that at any step \(h'\) such that \(mod (k', T) = 0\) the process will be reset to state \(s_1\). To simplify the analysis, we assume that whenever the stopping rule \(\tau\) is triggered, the process proceeds until the end of the episode, which means the sample complexity is a multiple of \(T\).

Now, we have all of the elements to derive our tailored lower bound. Specifically, we adapt to our BPI problem of interest the result [29], which was originally derived for the infinite-horizon and \(\delta\)-asymptotic setting. We obtain the following.

10 Meta Learning in Bandits↩︎

In this section, we analyze a simplified bandit version of the test-time regret minimization problem described in the paper. The aim of this study is to serve both as a gentle introduction to the more advanced results and techniques presented in the paper, which come more naturally in the bandit setting, as well as a standalone analysis that may be of independent interest.

We consider a class \(\mathcal{M}= (\mathcal{M}_i)_{i \in [M]}\) of bandits [50], each of them having a set of actions \(\mathcal{A}= (a_j)_{j \in [A]}\) with corresponding reward distributions \(R_i (a_j)\) for all \(i \in [M], j \in [A]\) with bounded mean \(\mu_{ij} \in [0, 1]\). First, we rephrase the separation condition presented in the paper (Assumption 1) as follows,

Just like in the MDP setting, we assume the reward distribution of all bandits \(\mathcal{M}_i \in \mathcal{M}\), as well as the set \(\mathcal{M}\) itself, to be fully known to the agent, who faces a test task (i.e., bandit) that is instead unknown but belonging to \(\mathcal{M}\). To evaluate the agent’s performance, we redefine the \(H\)-steps test-time regret for the task \(\mathcal{M}_i \in \mathcal{M}\) as \[\mathcal{R}_H (\mathcal{M}_i, \pi) = \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{h = 1}^H R_i(a^*) - R_i(a_h) \right] = \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{h = 1}^H \mu^* - \mu_h \right]\] where \(a^* \in \mathop{\mathrm{arg\,max}}_{a \in \mathcal{A}} \mu (a)\) is the optimal action in the bandit \(\mathcal{M}_i\), \(a_h \in \mathcal{A}\) is the action played by policy \(\pi\) at step \(h\), and \(\mu^*, \mu_h\) are the mean of their reward distribution, respectively. Just as we did in the paper for the more general MDP setting, we provide both a lower bound and a nearly minimax optimal algorithm for the test-time regret minimization in bandits.

10.1 Lower Bound↩︎

We now prove a lower bound to the test-time regret suffered by any algorithm in the introduced meta learning in bandits setting under the above separation condition (Assumption 8). Formally,

Proof. To prove the lower bound, we first construct a convenient instance in which it is hard to minimize the regret without knowing the task, while it is easy to identify the task playing sub-optimal actions. Then, we derive the lower bound on the regret suffered by any algorithm leveraging minimax lower bounds for standard bandits [50] and best arm identification results [51].

Let \(\mathcal{M}= (\mathcal{M}_i)_{i \in [M]}\) a problem instance in which every \(\mathcal{M}_i\) has \(|\mathcal{A}| = 2M\) actions and Gaussian reward distributions \(R_i (a_j) = \mathcal{N} (\mu_{ij}, 1)\). For each \(\mathcal{M}_i\), we specify the first set of \(M\) actions \((a_j)_{j = 1}^{M}\) as follows: The action \(a_i\) is the optimal action with mean \(\mu_i = \mu^*\), while all of the other actions are slightly sub-optimal \(\mu^* - \mu_j = \Delta_1 = 1 / \sqrt{H}\). The second set of actions \((a_j)_{j = M + 1}^{2M}\) is specified as follows: The actions \(\mathcal{A}_1 := (a_{M + i}, \ldots, a_{\frac{3M}{2} + i})\) have mean reward such that \(\mu^* - \mu_a = \Delta_2 = \log(H) / \sqrt{H}, \forall a \in \mathcal{A}_1\), and all of the other actions \(\mathcal{A}_2 := (a_{M + 1}, \ldots, a_{M + i - 1}) \cup (a_{\frac{3M}{2} + i + 1}, \ldots, 2M)\) have mean reward \(\mu_a < \mu_{M + i}\) such that \(\| R(a_{M + i}) - R (a) \|_1 \geq \lambda, \forall a \in \mathcal{A}_2\), fulfilling \(\lambda\)-separation. The instance is depicted in Figure 8.¹³

In general, there are two ways to approach the described instance. Since it is known that the second set of \(M\) actions is sub-optimal in every \(\mathcal{M}_i\), we can minimize the regret playing only the first set of actions. Otherwise, we can exploit the separation condition on the second set of arms to identify the task and then playing the optimal arm. To formalize this intuition, we borrow notation from best arm identification literature [51] similarly as we did in Appendix 9.

10.1.0.1 Additional Notation.

Let \(\mathcal{H}_h := (a_{h'}, r_{h'})_{h' \in [h]}\) be a trajectory collected by executing a policy \(\pi\). We denote \(\mathcal{F}_{h \geq 1}\) the corresponding filtration on \(\mathcal{H}_h\). We define

• \((\pi_{h'})_{h' = 1}^h\) a sampling rule over \(\mathcal{A}\) that determines the next action to play given past observations;

• \(\tau\) a stopping rule that gives the stopping time w.r.t. \(\mathcal{H}_h\);

• \(\hat{a}_\tau \in \mathcal{A}\) a decision rule, which is the action selected when \(\tau\) is triggered, i.e., the best guess on the optimal arm given past observations.

We denote as \(\mathop{\mathrm{\mathbb{E}}}[\tau]\) the sample complexity of the best arm identification problem. Further, we restrict \(\tau\) to the class of stopping rules such that \(\mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_i} [\tau] \leq H\), and we define the following event: \[\mathcal{E} = \Big\{ \hat{a}_\tau \in \mathop{\mathrm{arg\,max}}\nolimits_{a \in \mathcal{A}} \mu(a) \;: \;\text{``best arm is identified within H steps''} \Big\}.\] To derive the lower bound, we consider the two cases in which \(\mathcal{E}\) hold or does not hold with high probability, respectively.

10.1.0.2 Bad Event.

If the event \(\mathcal{E}\) does not hold with high probability, i.e., \(\mathbb{P} (\mathcal{E}) < 1 - \delta\), we can show that the regret scales with \(\Omega (\sqrt{H})\).

Let us consider any triplet \((\pi, \tau, \hat{a}_\tau)\). Without loss of generality, we take \(\mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_i}[\tau] = h\), from which we have \[\label{eq:regret95bad95event} \mathcal{R}_{H} (\mathcal{M}_i, \pi) = \mathcal{R}_{h} (\mathcal{M}_i, \pi) + (H - h) \Delta_1\tag{15}\] with probability at least \(\delta\).

First, we lower bound the term \(\mathcal{R}_{h} (\mathcal{M}_i, \pi)\) through regret minimization. We can restrict the action set to \(\tilde{\mathcal{A}}= (a_j)_{j = 1}^M\) as there is no incentive to play surely sub-optimal actions \(a_j\) for \(j > M\) when minimizing the regret. We take a policy \(\pi\) inducing pulls \((a_{h'})_{h' = 1}^h\) and corresponding counts \(T_j (h) := \sum_{h' = 1}^h \mathbf{1} (a_j = a_{h'})\) over the actions \(\tilde{\mathcal{A}}\) of \(\mathcal{M}_1\). Then, we select \(\mathcal{M}_i \in \mathcal{M}\) such that \(i = \mathop{\mathrm{arg\,min}}_{j \in [M]} \mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_1} [T_j (h)]\). We have that \[\max_{\mathcal{M}^* \in \mathcal{M}} \mathcal{R}_h (\mathcal{M}^*, \pi) \geq \max \left\{ \mathcal{R}_h (\mathcal{M}_1, \pi), \mathcal{R}_h (\mathcal{M}_i, \pi) \right\} \geq \frac{\mathcal{R}_h (\mathcal{M}_1, \pi) + \mathcal{R}_h (\mathcal{M}_i, \pi)}{2}.\] We can further expand the terms on the right hand-side by noting that \[\mathcal{R}_h (\mathcal{M}_1, \pi) \geq P_{\mathcal{M}_1} (T_1 (h) \leq h / 2) \frac{h \Delta_1}{2} \;\;\text{and} \;\;\mathcal{R}_h (\mathcal{M}_i, \pi) \geq P_{\mathcal{M}_i} (T_1 (h) > h / 2) \frac{h \Delta_1}{2}\] from which we can write \[\begin{align} \mathcal{R}_h (\mathcal{M}_1, \pi) + \mathcal{R}_h (\mathcal{M}_i, \pi) &> \frac{h \Delta_1}{2} \left( P_{\mathcal{M}_1} (T_1 (h) \leq h / 2) + P_{\mathcal{M}_i} (T_1 (h) > h / 2) \right) \\ &\geq \frac{h \Delta_1}{4} \exp \left( - \text{KL} (\mathbb{P}_{\mathcal{M}_1}, \mathbb{P}_{\mathcal{M}_i}) \right) \end{align}\] where the latter is obtained through the Bretagnolle-Huber inequality. Then, we can upper bound the KL divergence as \[\begin{align} \text{KL} & (\mathbb{P}_{\mathcal{M}_1}, \mathbb{P}_{\mathcal{M}_i}) \\ &= \mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_1} [T_1 (h)] \text{KL} (\mathcal{N} (\mu^*, 1), \mathcal{N} (\mu - \Delta_1, 1)) + \mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_1} [T_i (h)] \text{KL} (\mathcal{N} (\mu - \Delta_1, 1), \mathcal{N} (\mu^*, 1)) \\ &\leq \frac{(\Delta_1)^2}{2} \left( \mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_1} [T_1 (h)] + \mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_1} [T_i (h)] \right) \leq \frac{ h (\Delta_1)^2}{2} \end{align}\] from which we derive \[\max_{\mathcal{M}^* \in \mathcal{M}} \mathcal{R}_h (\mathcal{M}^*, \pi) \geq \frac{h \Delta_1}{8} \exp \left( - \frac{ h (\Delta_1)^2 }{2} \right).\] Finally, we substitute the latter in 15 to get \[\mathcal{R}_{H} (\mathcal{M}_i, \pi) \geq \frac{h \Delta_1}{8} \exp \left( - \frac{ h (\Delta_1)^2 }{2} \right) + (H - h) \Delta_1 \geq \frac{\sqrt{H}}{8} \exp \left( - \frac{1}{2} \right)\] with probability at least \(\delta\), where the last inequality is obtained by taking \(\Delta_1 = 1 / \sqrt{H}\) and noting that the left-hand side is minimized for \(\mathop{\mathrm{\mathbb{E}}}_{\mathcal{M}_i} [\tau] = h = H\).

10.1.0.3 Good Event.

The previous result states that the regret is at least \(\Omega (\sqrt{H})\) when the event \(\mathcal{E}\) does not hold with high probability. This hints that solving the best arm identification problem is necessary to minimize the regret. To derive the lower bound, we instantiate a proper best arm identification problem on the considered instance \(\mathcal{M}\).

Since the separation condition is fulfilled in the second set of actions, we can restrict our best arm identification problem to the action set \(\hat{\mathcal{A}}= (a_j)_{j = M + 1}^{2M}\). From Theorem 1 in [51], for any confidence \(\delta \in (0, 1)\), we have that \[\mathop{\mathrm{\mathbb{E}}}\nolimits_{\mathcal{M}_i} [\tau] \geq T^* (\mathcal{M}_i)^{-1} \log (1 / 2.4 \delta)\] where \[\label{eq:t95star} T^* (\mathcal{M}_i)^{-1} := \sup_{\omega \in \mathcal{P}(\hat{\mathcal{A}}) } \inf_{\mathcal{M}_j \in \mathcal{M}\setminus (\mathcal{M}_i) } \left( \sum_{k = M + 1}^{2M} \omega_k \text{KL} (R_i(a_k), R_j (a_k)) \right)\tag{16}\] holds with probability \(1 - \delta\). From the separation condition (Assumption 8) and the Pinsker’s inequality we have \[\text{KL} (R_i(a), R_j (a)) \geq 2 \text{TV}^2 (R_i(a), R_j (a)) \geq \frac{1}{2} \| R_i(a) - R_j (a) \|_1^2 \geq \frac{\lambda^2}{2}\] for every \(i \neq j\). By noting that the supremum in 16 is attained by \(\omega = (1 / M, \ldots, 1 / M)\) we get \[\mathop{\mathrm{\mathbb{E}}}\nolimits_{\mathcal{M}_i} [\tau] \geq \frac{2M}{\lambda^2} \log \left( \frac{1}{2.4\delta} \right).\]

Finally, we can derive the lower bound through \[\mathcal{R}_H (\mathcal{M}_i, \pi) \geq \mathop{\mathrm{\mathbb{E}}}\nolimits_{\mathcal{M}_i} [\tau] \Delta_2 = \frac{2M}{\lambda^2} \frac{\log(H)}{ \sqrt{H}} \log \left( \frac{1}{2.4\delta} \right) \geq \frac{2}{\sqrt{C} - \log (C) } \frac{M \log (H)}{\lambda} \log \left( \frac{1}{2.4\delta} \right)\] where the last inequality is obtained by exploiting \(H \leq C\) and that the mean of the reward distribution is bounded in \([0, 1]\) to write \(\lambda + \frac{\log (H)}{\sqrt{H}} \leq 1\), which gives \(\lambda \leq \frac{\sqrt{C} - \log(C)}{\sqrt{H}}\). ◻

10.2 Upper Bound↩︎

In this section, we provide a simple algorithm, which is practically a direct adaptation to the bandit setting of Algorithm 1, in turn inspired by [1], that nearly matches the lower bound presented in the previous section.

The idea of the algorithm is to exploit the knowledge of the class \(\mathcal{M}\) to quickly identify the test task \(\mathcal{M}^*\) and then commit to the optimal action \(a^*\) for \(\mathcal{M}^*\). The pseudocode of this simple procedure is provided in Algorithm 9.

The upper bound to the test-time regret suffered by Algorithm 9 is provided by the following result.

References↩︎