Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
Year: 2021

Abstract:
Policy optimization is a widely-used method in reinforcement learning. Due to its local-search nature, however, theoretical guarantees on global optimality often rely on extra assumptions on the Markov Decision Processes (MDPs) that bypass the challenge of global exploration. To eliminate the need of such assumptions, in this work, we develop a general solution that adds dilated bonuses to the policy update to facilitate global exploration. To showcase the power and generality of this technique, we apply it to several episodic MDP settings with adversarial losses and bandit feedback, improving and generalizing the state-of-the-art. Specifically, in the tabular case, we obtain Õ( √ T ) regret where T is the number of episodes, improving the Õ(T /3) regret bound by [27]. When the number of states is infinite, under the assumption that the state-action values are linear in some low-dimensional features, we obtain Õ(T /3) regret with the help of a simulator, matching the result of [24] while importantly removing the need of an exploratory policy that their algorithm requires. To our knowledge, this is the first algorithm with sublinear regret for linear function approximation with adversarial losses, bandit feedback, and no exploratory assumptions. Finally, we also discuss how to further improve the regret or remove the need of a simulator using dilated bonuses, when an exploratory policy is available.1

text: √ T ) regret where T is the number of episodes,
improving the Õ(T 2/3) regret bound by [27]. When the number of states is infinite, under the assumption that the state-action values are linear in some low-dimensional features, we obtain Õ(T 2/3) regret with the help of a simulator, matching the result of [24] while importantly removing the need of an exploratory policy that their algorithm requires. To our knowledge, this is the first algorithm with sublinear regret for linear function approximation with adversarial losses, bandit feedback, and no exploratory assumptions. Finally, we also discuss how to further improve the regret or remove the need of a simulator using dilated bonuses, when an exploratory policy is available.1

heading: 1 Introduction
text: Policy optimization methods are among the most widely-used methods in reinforcement learning. Its empirical success has been demonstrated in various domains such as computer games [26] and robotics [21]. However, due to its local-search nature, global optimality guarantees of policy optimization often rely on unrealistic assumptions to ensure global exploration (see e.g., [1, 3, 24, 30]), making it theoretically less appealing compared to other methods.
Motivated by this issue, a line of recent works [7, 27, 2, 35] equip policy optimization with global exploration by adding exploration bonuses to the update, and prove favorable guarantees even without making extra exploratory assumptions. Moreover, they all demonstrate some robustness aspect of policy optimization (such as being able to handle adversarial losses or a certain degree of model misspecification). Despite these important progresses, however, many limitations still exist, including worse regret rates comparing to the best value-based or model-based approaches [27, 2, 35], or requiring full-information feedback on the entire loss function (as opposed to the more realistic bandit feedback) [7].
∗Equal contribution. 1In an improved version of this paper, we show that under the linear MDP assumption, an exploratory policy
is not even needed. See https://arxiv.org/abs/2107.08346.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
To address these issues, in this work, we propose a new type of exploration bonuses called dilated bonuses, which satisfies a certain dilated Bellman equation and provably leads to improved exploration compared to existing works (Section 3). We apply this general idea to advance the state-of-the-art of policy optimization for learning finite-horizon episodic MDPs with adversarial losses and bandit feedback. More specifically, our main results are:
• First, in the tabular setting, addressing the main open question left in [27], we improve their Õ(T 2/3) regret to the optimal Õ( √ T ) regret. This shows that policy optimization, which performs local
optimization, is as capable as other occupancy-measure-based global optimization algorithms [15, 20] in terms of global exploration. Moreover, our algorithm is computationally more efficient than those global methods since they require solving some convex optimization in each episode. (Section 4)
• Second, to further deal with large-scale problems, we consider a linear function approximation setting where the state-action values are linear in some known low-dimensional features and also a simulator is available, the same setting considered by [24]. We obtain the same Õ(T 2/3) regret while importantly removing the need of an exploratory policy that their algorithm requires. Unlike the tabular setting (where we improve existing regret rates of policy optimization), note that researchers have not been able to show any sublinear regret for policy optimization without exploratory assumptions for this problem, which shows the critical role of our proposed dilated bonuses. In fact, there are simply no existing algorithms with sublinear regret at all for this setting, be it policy-optimization-type or not. This shows the advantage of policy optimization over other approaches, when combined with our dilated bonuses. (Section 5)
• Finally, while the main focus of our work is to show how dilated bonuses are able to provide global exploration, we also discuss their roles in improving the regret rate to Õ( √ T ) in the linear setting
above or removing the need of a simulator for the special case of linear MDPs (with Õ(T 6/7) regret), when an exploratory policy is available. (Section 6)
Related work. In the tabular setting, except for [27], most algorithms apply the occupancymeasure-based framework to handle adversarial losses (e.g., [25, 15, 9, 8]), which as mentioned is computationally expensive. For stochastic losses, there are many more different approaches such as model-based ones [13, 10, 5, 12, 34] and value-based ones [14, 11].
Theoretical studies for linear function approximation have gained increasing interest recently [32, 33, 16]. Most of them study stochastic/stationary losses, with the exception of [24, 7]. Our algorithm for the linear MDP setting bears some similarity to those of [2, 35] which consider stationary losses. However, our algorithm and analysis are arguably simpler than theirs. Specifically, they divide the state space into a known part and an unknown part, with different exploration principle and bonus design for different parts. In contrast, we enjoy a unified bonus design for all states. Besides, in each episode, their algorithms first execute an exploratory policy (from a policy cover), and then switch to the policy suggested by the policy optimization algorithm, which inevitably leads to linear regret when facing adversarial losses.

heading: 2 Problem Setting
text: We consider an MDP specified by a state space X (possibly infinite), a finite action space A, and a transition function P with P (·|x, a) specifying the distribution of the next state after taking action a in state x. In particular, we focus on the finite-horizon episodic setting in which X admits a layer structure and can be partitioned into X0, X1, . . . , XH for some fixed parameter H , where X0 contains only the initial state x0, XH contains only the terminal state xH , and for any x ∈ Xh, h = 0, . . . ,H − 1, P (·|x, a) is supported on Xh+1 for all a ∈ A (that is, transition is only possible from Xh to Xh+1). An episode refers to a trajectory that starts from x0 and ends at xH following some series of actions and the transition dynamic. The MDP may be assigned with a loss function ` : X ×A→ [0, 1] so that `(x, a) specifies the loss suffered when selecting action a in state x. A policy π for the MDP is a mapping X → ∆(A), where ∆(A) denotes the set of distributions over A and π(a|x) is the probability of choosing action a in state x. Given a loss function `
and a policy π, the expected total loss of π is given by V π(x0; `) = E [∑H−1 h=0 `(xh, ah) ∣∣ ah ∼
πt(·|xh), xh+1 ∼ P (·|xh, ah) ] . It can also be defined via the Bellman equation involving the state value function V π(x; `) and the state-action value function Qπ(x, a; `) (a.k.a. Q-function) defined as below: V (xH ; `) = 0,
Qπ(x, a; `) = `(x, a) + Ex′∼P (·|x,a) [V π(x′; `)] , and V π(x; `) = Ea∼π(·|x) [Qπ(x, a; `)] .
We study online learning in such a finite-horizon MDP with unknown transition, bandit feedback, and adversarial losses. The learning proceeds through T episodes. Ahead of time, an adversary arbitrarily decides T loss functions `1, . . . , `T , without revealing them to the learner. Then in each episode t, the learner decides a policy πt based on all information received prior to this episode, executes πt starting from the initial state x0, generates and observes a trajectory {(xt,h, at,h, `t(xt,h, at,h))}H−1h=0 . Importantly, the learner does not observe any other information about `t (a.k.a. bandit feedback).2 The goal of the learner is to minimize the regret, defined as
Reg = T∑ t=1 V πtt (x0)−min π T∑ t=1 V πt (x0),
where we use V πt (x) as a shorthand for V π(x; `t) (and similarly Qπt (x, a) as a shorthand for Qπ(x, a; `t)). Without further structures, the best existing regret bound is Õ(H|X| √ |A|T ) [15], with an extra √ X factor compared to the best existing lower bound [14].
Occupancy measures. For a policy π and a state x, we define qπ(x) to be the probability (or probability measure when |X| is infinite) of visiting state x within an episode when following π. When it is necessary to highlight the dependence on the transition, we write it as qP,π(x). Further define qπ(x, a) = qπ(x)π(a|x) and qt(x, a) = qπt(x, a). Finally, we use q? as a shorthand for qπ ?
where π? ∈ argminπ ∑T t=1 V π t (x0) is one of the optimal policies.
Note that by definition, we have V π(x0; `) = ∑ x,a q
π(x, a)`(x, a). In fact, we will overload the notation and let V π(x0; b) = ∑ x,a q
π(x, a)b(x, a) for any function b : X ×A→ R (even though it might not correspond to a real loss function).
Other notations. We denote by Et[·] and Vart[·] the expectation and variance conditioned on everything prior to episode t. For a matrix Σ and a vector z (of appropriate dimension), ‖z‖Σ denotes the quadratic norm √ z>Σz. The notation Õ(·) hides all logarithmic factors.

heading: 3 Dilated Exploration Bonuses
text: In this section, we start with a general discussion on designing exploration bonuses (not specific to policy optimization), and then introduce our new dilated bonuses for policy optimization. For simplicity, the exposition in this section assumes a finite state space, but the idea generalizes to an infinite state space.
When analyzing the regret of an algorithm, very often we run into the following form: Reg = T∑ t=1 V πtt (x0)− T∑ t=1 V π ? t (x0) ≤ o(T ) + T∑ t=1 ∑ x,a q?(x, a)bt(x, a) = o(T ) + T∑ t=1 V π ? (x0; bt),
(1)
for some function bt(x, a) usually related to some estimation error or variance that can be prohibitively large. For example, in policy optimization, the algorithm performs local search in each state essentially using a multi-armed bandit algorithm and treating Qπt(x, a) as the loss of action a in state x. Since Qπt(x, a) is unknown, however, the algorithm has to use some estimator of Qπt(x, a) instead, whose bias and variance both contribute to the bt function. Usually, bt(x, a) is large for a rarely-visited state-action pair (x, a) and is inversely related to qt(x, a), which is exactly why most analysis relies
2Full-information feedback, on the other hand, refers to the easier setting where the entire loss function `t is revealed to the learner at the end of episode t.
on the assumption that some distribution mismatch coefficient related to q?(x,a)/qt(x,a) is bounded (see e.g., [3, 31]).
On the other hand, an important observation is that while V π ?
(x0; bt) can be prohibitively large, its counterpart with respect to the learner’s policy V πt(x0; bt) is usually nicely bounded. For example, if bt(x, a) is inversely related to qt(x, a) as mentioned, then V πt(x0; bt) = ∑ x,a qt(x, a)bt(x, a) is small no matter how small qt(x, a) could be for some (x, a). This observation, together with the linearity property V π(x0; `t − bt) = V π(x0; `t)− V π(x0; bt), suggests that we treat `t − bt as the loss function of the problem, or in other words, add a (negative) bonus to each state-action pair, which intuitively encourages exploration due to underestimation. Indeed, assuming for a moment that Eq. (1) still roughly holds even if we treat `t − bt as the loss function:
T∑ t=1 V πt(x0; `t − bt)− T∑ t=1 V π ? (x0; `t − bt) . o(T ) + T∑ t=1 V π ? (x0; bt). (2)
Then by linearity and rearranging, we have
Reg = T∑ t=1 V πtt (x0)− T∑ t=1 V π ? t (x0) . o(T ) + T∑ t=1 V πt(x0; bt). (3)
Due to the switch from π? to πt in the last term compared to Eq. (1), this is usually enough to prove a desirable regret bound without making extra assumptions.
The caveat of this discussion is the assumption of Eq. (2). Indeed, after adding the bonuses, which itself contributes some more bias and variance, one should expect that bt on the right-hand side of Eq. (2) becomes something larger, breaking the desired cancellation effect to achieve Eq. (3). Indeed, the definition of bt essentially becomes circular in this sense.
Dilated Bonuses for Policy Optimization To address this issue, we take a closer look at the policy optimization algorithm specifically. As mentioned, policy optimization decomposes the problem into individual multi-armed bandit problems in each state and then performs local optimization. This is based on the well-known performance difference lemma [17]:
Reg = ∑ x q?(x) T∑ t=1 ∑ a ( πt(a|x)− π?(a|x) ) Qπtt (x, a),
showing that in each state x, the learner is facing a bandit problem with Qπtt (x, a) being the loss for action a. Correspondingly, incorporating the bonuses bt for policy optimization means subtracting the bonus Qπt(x, a; bt) from Qπtt (x, a) for each action a in each state x. Recall that Q
πt(x, a; bt) satisfies the Bellman equation Qπt(x, a; bt) = bt(x, a) + Ex′∼P (·|x,a)Ea′∼πt(·|x′) [Bt(x′, a′)]. To resolve the issue mentioned earlier, we propose to replace this bonus function Qπt(x, a; bt) with its dilated version Bt(s, a) satisfying the following dilated Bellman equation:
Bt(x, a) = bt(x, a) +
( 1 + 1
H
) Ex′∼P (·|x,a)Ea′∼πt(·|x′) [Bt(x ′, a′)] (4)
(with Bt(xH , a) = 0 for all a). The only difference compared to the standard Bellman equation is the extra (1 + 1H ) factor, which slightly increases the weight for deeper layers and thus intuitively induces more exploration for those layers. Due to the extra bonus compared to Qπt(x, a; bt), the regret bound also increases accordingly. In all our applications, this extra amount of regret turns out to be of the form 1H ∑T t=1 ∑ x,a q ?(x)πt(a|x)Bt(x, a), leading to
∑ x q?(x) T∑ t=1 ∑ a ( πt(a|x)− π?(a|x) )( Qπtt (x, a)−Bt(x, a) ) ≤ o(T ) +
T∑ t=1 V π ? (x0; bt) + 1 H T∑ t=1 ∑ x,a q?(x)πt(a|x)Bt(x, a). (5)
With some direct calculation, one can show that this is enough to show a regret bound that is only a constant factor larger than the desired bound in Eq. (3)! This is summarized in the following lemma.
Lemma 3.1. If Eq. (5) holds with Bt defined in Eq. (4), then Reg ≤ o(T ) + 3 ∑T t=1 V πt(x0; bt).
The high-level idea of the proof is to show that the bonuses added to a layer h is enough to cancel the large bias/variance term (including those coming from the bonus itself) from layer h+ 1. Therefore, cancellation happens in a layer-by-layer manner except for layer 0, where the total amount of bonus can be shown to be at most (1 + 1H ) H ∑T t=1 V πt(x0; bt) ≤ 3 ∑T t=1 V πt(x0; bt).
Recalling again that V πt(x0; bt) is usually nicely bounded, we thus arrive at a favorable regret guarantee without making extra assumptions. Of course, since the transition is unknown, we cannot compute Bt exactly. However, Lemma 3.1 is robust enough to handle either a good approximate version of Bt (see Lemma B.1) or a version where Eq. (4) and Eq. (5) only hold in expectation (see Lemma B.2), which is enough for us to handle unknown transition. In the next three sections, we apply this general idea to different settings, showing what bt and Bt are concretely in each case.

heading: 4 The Tabular Case
text: In this section, we study the tabular case where the number of states is finite. We propose a policy optimization algorithm with Õ( √ T ) regret, improving the Õ(T 2/3) regret of [27]. See Algorithm 1 for the complete pseudocode.
Algorithm design. First, to handle unknown transition, we follow the common practice (dating back to [13]) to maintain a confidence set of the transition, which is updated whenever the visitation count of a certain state-action pair is doubled. We call the period between two model updates an epoch, and use Pk to denote the confidence set for epoch k, formally defined in Eq. (10). In episode t, the policy πt is defined via the standard multiplicative weight algorithm (also connected to Natural Policy Gradient [18, 3, 30]), but importantly with the dilated bonuses incorporated such that πt(a|x) ∝ exp(−η ∑t−1 τ=1(Q̂τ (x, a)−Bτ (x, a))). Here, η is a step size parameter, Q̂τ (x, a) is an importance-weighted estimator for Qπττ (x, a) defined in Eq. (7), and Bτ (x, a) is the dilated bonus defined in Eq. (9).
More specifically, for a state x in layer h, Q̂t(x, a) is defined as Lt,h1t(x,a) qt(x,a)+γ , where 1t(x, a) is the indicator of whether (x, a) is visited during episode t; Lt,h is the total loss suffered by the learner starting from layer h till the end of the episode; qt(x, a) = maxP̂∈Pk q
P̂ ,πt(x, a) is the largest plausible value of qt(x, a) within the confidence set, which can be computed efficiently using the COMP-UOB procedure of [15] (see also Appendix C.1); and finally γ is a parameter used to control the maximum magnitude of Q̂t(x, a), inspired by the work of [23]. To get a sense of this estimator, consider the special case when γ = 0 and the transition is known so that we can set Pk = {P} and thus qt = qt. Then, since the expectation of Lt,h conditioned on (x, a) being visited is Q πt t (x, a) and the expectation of 1t(x, a) is qt(x, a), we know that Q̂t(x, a) is an unbiased estimator for Qπtt (x, a). The extra complication is simply due to the transition being unknown, forcing us to use qt and γ > 0 to make sure that Q̂t(x, a) is an optimistic underestimator, an idea similar to [15].
Next, we explain the design of the dilated bonus Bt. Following the discussions of Section 3, we first figure out what the corresponding bt function is in Eq. (1), by analyzing the regret bound without using any bonuses. The concrete form of bt turns out to be Eq. (8), whose value at (x, a) is independent of a and thus written as bt(x) for simplicity. Note that Eq. (8) depends on the occupancy measure lower bound q
t (s, a) = minP̂∈Pk q P̂ ,πt(x, a), the opposite of qt(s, a), which can also be computed efficiently using a procedure similar to COMP-UOB (see Appendix C.1). Once again, to get a sense of this, consider the special case with a known transition so that we can set Pk = {P} and thus qt = qt = qt. Then, one see that bt(x) is simply upper bounded by Ea∼πt(·|x) [3γH/qt(x,a)] = 3γH|A|/qt(x), which is inversely related to the probability of visiting state x, matching the intuition we provided in Section 3 (that bt(x) is large if x is rarely visited). The extra complication of Eq. (8) is again just due to the unknown transition.
With bt(x) ready, the final form of the dilated bonus Bt is defined following the dilated Bellman equation of Eq. (4), except that since P is unknown, we once again apply optimism and find the
3We use y +← z as a shorthand for the increment operation y ← y + z.
Algorithm 1 Policy Optimization with Dilated Bonuses (Tabular Case) Parameters: δ ∈ (0, 1), η = min {1/24H3, 1/√|X||A|HT}, γ = 2ηH . Initialization: Set epoch index k = 1 and confidence set P1 as the set of all transition functions. For all (x, a, x′), initialize counters N0(x, a) = N1(x, a) = 0, N0(x, a, x′) = N1(x, a, x′) = 0. for t = 1, 2, . . . , T do
Step 1: Compute and execute policy. Execute πt for one episode, where
πt(a|x) ∝ exp ( −η
t−1∑ τ=1 ( Q̂τ (x, a)−Bτ (x, a) )) , (6)
and obtain trajectory {(xt,h, at,h, `t(xt,h, at,h))}H−1h=0 .
Step 2: Construct Q-function estimators. For all h ∈ {0, . . . ,H − 1} and (x, a) ∈ Xh ×A,
Q̂t(x, a) = Lt,h
qt(x, a) + γ 1t(x, a), (7)
with Lt,h = H−1∑ i=h `t(xt,i, at,i), qt(x, a) = max P̂∈Pk qP̂ ,πt(x, a),1t(x, a) = 1{xt,h = x, at,h = a}.
Step 3: Construct bonus functions. For all (x, a) ∈ X ×A,
bt(x) = Ea∼πt(·|x)
[ 3γH +H(qt(x, a)− qt(x, a))
qt(x, a) + γ
] (8)
Bt(x, a) = bt(x) +
( 1 + 1
H ) max P̂∈Pk Ex′∼P̂ (·|x,a)Ea′∼πt(·|x′) [Bt(x ′, a′)] (9)
where q t (x, a) = minP̂∈Pk q P̂ ,πt(x, a) and Bt(xH , a) = 0 for all a.
Step 4: Update model estimation. ∀h < H , Nk(xt,h, at,h) +← 1, Nk(xt,h, at,h, xt,h+1) +← 1.3 if ∃h, Nk(xt,h, at,h) ≥ max{1, 2Nk−1(xt,h, at,h)} then
Increment epoch index k +← 1 and copy counters: Nk ← Nk−1, Nk ← Nk−1. Compute empirical transition P k(x′|x, a) = Nk(x,a,x ′) max{1,Nk(x,a)} and confidence set:
Pk = { P̂ : ∣∣∣P̂ (x′|x, a)− P k(x′|x, a)∣∣∣ ≤ confk(x′|x, a), ∀(x, a, x′) ∈ Xh ×A×Xh+1, h = 0, 1, . . . ,H − 1 } ,
(10)
where confk(x ′|x, a) = 4
√ Pk(x′|x,a) ln(T |X||A|δ )
max{1,Nk(x,a)} + 28 ln(T |X||A|δ ) 3 max{1,Nk(x,a)} .
largest possible value within the confidence set (see Eq. (9)). This can again be efficiently computed; see Appendix C.1. This concludes the complete algorithm design.
Regret analysis. The regret guarantee of Algorithm 1 is presented below: Theorem 4.1. Algorithm 1 ensures that with probability 1−O(δ), Reg = Õ ( H2|X| √ AT +H4 ) .
Again, this improves the Õ(T 2/3) regret of [27]. It almost matches the best existing upper bound for this problem, which is Õ(H|X| √ |A|T ) [15]. While it is unclear to us whether this small gap can be closed using policy optimization, we point out that our algorithm is arguably more efficient than that of [15], which performs global convex optimization over the set of all plausible occupancy measures in each episode.
The complete proof of this theorem is deferred to Appendix C. Here, we only sketch an outline of proving Eq. (5), which, according to the discussions in Section 3, is the most important part of the analysis. Specifically, we decompose the left-hand side of Eq. (5),∑ x q ?(x) ∑ t 〈πt(·|x)− π?(·|x), Qt(x, ·)−Bt(x, ·)〉, as BIAS-1 + BIAS-2 + REG-TERM, where
• BIAS-1 = ∑ x q ?(x) ∑ t〈πt(·|x), Qt(x, ·)− Q̂t(x, ·)〉 measures the amount of underestimation
of Q̂t related to πt, which can be bounded by ∑ t ∑ x,a q ?(x)πt(a|x) ( 2γH+H(qt(x,a)−qt(x,a)) qt(x,a)+γ ) +
Õ (H/η) with high probability (Lemma C.1); • BIAS-2 = ∑ x q ?(x) ∑ t〈π?(·|x), Q̂t(x, ·)−Qt(x, ·)〉 measures the amount of overestimation of
Q̂t related to π?, which can be bounded by Õ (H/η) since Q̂t is an underestimator (Lemma C.2); • REG-TERM = ∑ x q ?(x) ∑ t〈πt(·|x)− π?(·|x), Q̂t(x, ·)−Bt(x, ·)〉 is directly controlled by the
multiplicative weight update, and is bounded by ∑ t ∑ x,a q ?(x)πt(a|x) ( γH qt(x,a)+γ + Bt(x,a)H ) + Õ (H/η) with high probability (Lemma C.3).
Combining all with the definition of bt proves the key Eq. (5) (with the o(T ) term being Õ(H/η)).
5 The Linear-Q Case
In this section, we move on to the more challenging setting where the number of states might be infinite, and function approximation is used to generalize the learner’s experience to unseen states. We consider the most basic linear function approximation scheme where for any π, the Q-function Qπt (x, a) is linear in some known feature vector φ(x, a), formally stated below.
Assumption 1 (Linear-Q). Let φ(x, a) ∈ Rd be a known feature vector of the state-action pair (x, a). We assume that for any episode t, policy π, and layer h, there exists an unknown weight vector θπt,h ∈ Rd such that for all (x, a) ∈ Xh × A, Qπt (x, a) = φ(x, a)>θπt,h. Without loss of generality, we assume ‖φ(x, a)‖ ≤ 1 for all (x, a) and ‖θπt,h‖ ≤ √ dH for all t, h, π.
For justification on the last condition on norms, see [30, Lemma 8]. This linear-Q assumption has been made in several recent works with stationary losses [1, 30] and also in [24] with the same adversarial losses.4 It is weaker than the linear MDP assumption (see Section 6) as it does not pose explicit structure requirements on the loss and transition functions. Due to this generality, however, our algorithm also requires access to a simulator to obtain samples drawn from the transition, formally stated below. Assumption 2 (Simulator). The learner has access to a simulator, which takes a state-action pair (x, a) ∈ X ×A as input, and generates a random outcome of the next state x′ ∼ P (·|x, a).
Note that this assumption is also made by [24] and more earlier works with stationary losses (see e.g., [4, 28]).5 In this setting, we propose a new policy optimization algorithm with Õ(T 2/3) regret. See Algorithm 2 for the pseudocode.
Algorithm design. The algorithm still follows the multiplicative weight update Eq. (11) in each state x ∈ Xh (for some h), but now with φ(x, a)>θ̂t,h as an estimator for Qπtt (x, a) = φ(x, a)>θ πt t,h, and BONUS(t, x, a) as the dilated bonus Bt(x, a). Specifically, the construction of the weight estimator θ̂t,h follows the idea of [24] (which itself is based on the linear bandit literature) and is defined in Eq. (12) as Σ̂+t,hφ(xt,h, at,h)Lt,h. Here, Σ̂ + t,h is an -accurate estimator of (γI + Σt,h)
−1, where γ is a small parameter and Σt,h = Et[φ(xt,h, at,h)φ(xt,h, at,h)>] is the covariance matrix for layer h under policy πt; Lt,h = ∑H−1 i=h `t(xt,i, at,i) is again the loss suffered by the learner starting from layer h, whose conditional expectation is Qπtt (xt,h, at,h) = φ(xt,h, at,h) >θπtt,h. Therefore,
4The assumption in [24] is stated slightly differently (e.g., their feature vectors are independent of the action). However, it is straightforward to verify that the two versions are equivalent.
5The simulator required by [24] is in fact slightly weaker than ours and those from earlier works — it only needs to be able to generate a trajectory starting from x0 for any policy.
Algorithm 2 Policy Optimization with Dilated Bonuses (Linear-Q Case) parameters: γ, β, η, , M = ⌈
24 ln(dHT ) 2γ2
⌉ , N = ⌈ 2 γ ln 1 γ ⌉ .
for t = 1, 2, . . . , T do Step 1: Interact with the environment. Execute πt, which is defined such that for each x ∈ Xh,
πt(a|x) ∝ exp ( −η
t−1∑ τ=1 ( φ(x, a)>θ̂τ,h − BONUS(τ, x, a) )) , (11)
and obtain trajectory {(xt,h, at,h, `t(xt,h, at,h))}H−1h=0 .
Step 2: Construct covariance matrix inverse estimators.{ Σ̂+t,h }H−1 h=0 = GEOMETRICRESAMPLING (t,M,N, γ) . (see Algorithm 7)
Step 3: Construct Q-function weight estimators. For h = 0, . . . ,H − 1, compute
θ̂t,h = Σ̂ + t,hφ(xt,h, at,h)Lt,h, where Lt,h = H−1∑ i=h `t(xt,i, at,i). (12)
Algorithm 3 BONUS(t, x, a) if BONUS(t, x, a) has been called before then
return the value of BONUS(t, x, a) calculated last time. Let h be such that x ∈ Xh. if h = H then return 0. Compute πt(·|x), defined in Eq. (11) (which involves recursive calls to BONUS for smaller t). Get a sample of the next state x′ ← SIMULATOR(x, a). Compute πt(·|x′) (again, defined in Eq. (11)), and sample an action a′ ∼ πt(·|x′). return β‖φ(x, a)‖2
Σ̂+t,h + Ej∼πt(·|x)
[ β‖φ(x, j)‖2
Σ̂+t,h
] + ( 1 + 1H ) BONUS(t, x′, a′).
when γ and approach 0, one see that θ̂t,h is indeed an unbiased estimator of θπtt,h. We adopt the GEOMETRICRESAMPLING procedure (see Algorithm 7) of [24] to compute Σ̂+t,h, which involves calling the simulator multiple times.
Next, we explain the design of the dilated bonus. Again, following the general principle discussed in Section 3, we identify bt(x, a) in this case as β‖φ(x, a)‖2Σ̂+t,h + Ej∼πt(·|x) [ β‖φ(x, j)‖2 Σ̂+t,h ] for some parameter β > 0. Further following the dilated Bellman equation Eq. (4), we thus define BONUS(t, x, a) recursively as the last line of Algorithm 3, where we replace the expectation E(x′,a′)[BONUS(t, x′, a′)] with one single sample for efficient implementation. However, even more care is needed to actually implement the algorithm. First, since the state space is potentially infinite, one cannot actually calculate and store the value of BONUS(t, x, a) for all (x, a), but can only calculate them on-the-fly when needed. Moreover, unlike the estimators for Qπtt (x, a), which can be succinctly represented and stored via the weight estimator θ̂t,h, this is not possible for BONUS(t, x, a) due to the lack of any structure. Even worse, the definition of BONUS(t, x, a) itself depends on πt(·|x) and also πt(·|x′) for the afterstate x′, which, according to Eq. (11), further depends on BONUS(τ, x, a) for τ < t, resulting in a complicated recursive structure. This is also why we present it as a procedure in Algorithm 3 (instead of Bt(x, a)). In total, this leads to (TAH)O(H) number of calls to the simulator. Whether this can be improved is left as a future direction.
Regret guarantee By showing that Eq. (5) holds in expectation for our algorithm, we obtain the following regret guarantee. (See Appendix D for the proof.)
Theorem 5.1. Under Assumption 1 and Assumption 2, with appropriate choices of the parameters γ, β, η, , Algorithm 2 ensures E[Reg] = Õ ( H2(dT )2/3 ) (the dependence on |A| is only logarithmic).
This matches the Õ(T 2/3) regret of [24, Theorem 1], without the need of their assumption which essentially says that the learner is given an exploratory policy to start with.6 To our knowledge, this is the first no-regret algorithm for linear function approximation (with adversarial losses and bandit feedback) when no exploratory assumptions are made.

heading: 6 Improvements with an Exploratory Policy
text: Previous sections have demonstrated the role of dilated bonuses in providing global exploration. In this section, we further discuss what dilated bonuses can achieve when an exploratory policy π0 is given in linear function approximation settings. Formally, let Σh = E[φ(xh, ah)φ(xh, ah)>] denote the covariance matrix for features in layer h following π0 (that is, the expectation is taken over a trajectory {(xh, ah)}H−1h=0 with ah ∼ π0(·|xh)), then we assume the following. Assumption 3 (An exploratory policy). An exploratory policy π0 is given to the learner ahead of time, and guarantees that for any h, the eigenvalues of Σh are at least λmin > 0.
The same assumption is made by [24] (where they simply let π0 be the uniform exploration policy). As mentioned, under this assumption they achieve Õ(T 2/3) regret. By slightly modifying our Algorithm 2 (specifically, executing π0 with a small probability in each episode and setting the parameters differently), we achieve the following improved result.
Theorem 6.1. Under Assumptions 1, 2, and 3, Algorithm 8 ensures E[Reg] = Õ (√
H4T λmin
+ √ H5dT ) .
Removing the simulator One drawback of our algorithm is that it requires exponential in H number of calls to the simulator. To address this issue, and in fact, to also completely remove the need of a simulator, we further consider a special case where the transition function also has a low-rank structure, known as the linear MDP setting.
Assumption 4 (Linear MDP). The MDP satisfies Assumption 1 and that for any h and x′ ∈ Xh+1, there exists a weight vector νx ′
h ∈ Rd such that P (x′|x, a) = φ(x, a)>νx ′ h for all (x, a) ∈ Xh ×A.
There is a surge of works studying this setting, with [7] being the closest to us. They achieve Õ( √ T ) regret but require full-information feedback of the loss functions, and there are no existing results for the bandit feedback setting without a simulator. We propose the first algorithm with sublinear regret for this problem, shown in Algorithm 10 of Appendix F due to space limit.
The structure of Algorithm 10 is very similar to that of Algorithm 2, with the same definition of bt(x, a). However, due to the low-rank transition structure, we are now able to efficiently construct estimators of Bt(x, a) even for unseen state-action pairs using function approximation, bypassing the requirement of a simulator. Specifically, observe that according to Eq. (4), for each x ∈ Xh, under Assumption 4 Bt(x, a) can be written as bt(x, a) + φ(x, a)>Λπtt,h, where Λ πt t,h = (1 +
1 H ) ∫ x′∈Xh+1 Ea′∼πt(·|x′)[Bt(x ′, a′)]νx ′ h dx ′ is a vector independent of (x, a). Thus, by the same idea of estimating θπtt,h, we can estimate Λ πt t,h as well, thus succinctly representing Bt(x, a) for all (x, a).
Recall that estimating θπtt,h (and thus also Λ πt t,h) requires constructing the covariance matrix inverse estimate Σ̂+t,h. Due to the lack of a simulator, another important change in the algorithm is to construct Σ̂+t,h using online samples. To do so, we divide the entire horizon into epochs with equal length, and only update the policy optimization algorithm at the beginning of an epoch. Within an epoch, we keep executing the same policy and collect several trajectories, which are then used to construct Σ̂+t,h. With these changes, we successfully remove the need of a simulator, and prove the guarantee below.
Theorem 6.2. Under Assumption 3 and Assumption 4, Algorithm 10 ensures E[Reg] = Õ ( T 6/7 ) (see Appendix F for dependence on other parameters).
One potential direction to further improve our algorithm is to reuse data across different epochs, an idea adopted by several recent works [35, 19] for different problems. We also conjecture that
6Under an even strong assumption that every policy is exploratory, they also improve the regret to Õ( √ T );
see [24, Theorem 2].
Assumption 3 can be removed, but we meet some technical difficulty in proving so. We leave these for future investigation.
Acknowledgments and Disclosure of Funding
We thank Gergely Neu and Julia Olkhovskaya for discussions on the technical details of their GEOMETRICRESAMPLING procedure. This work is supported by NSF Award IIS-1943607 and a Google Faculty Research Award.

Review summaries:
This paper makes several contributions:  	 1. In the episodic tabular setting, with adversarial rewards, unknown MDP dynamics and bandit feedback, it provides the first algorithm that achieves O(\sqrt T) regret bound using the regret decomposition approach, which is more computationally cheap than the approach presented in Jin et al. Typically result obtained by using this approach scales with the inverse of the visitation probability. However, here the results don't have this drawback.   	 2. For the linear case, the paper considers the setting with an infinite set of states and the algorithm has access to the simulator of the dynamics of MDP. Then it provides the algorithm that obtains T^2/3 regret without assuming that the smallest eigenvalue of the covariance matrix \Sigma_h is at least \lambda_min and T^1/2 taken this assumption. The latter improves the previous result in the considered setting, which was T^2/3 regret, assuming that the smallest eigenvalue of \Sigma_h is bounded away from zero. The only drawback is that the algorithm is more computationally expensive since it requires O(T^H) number of calls to the simulator. 	 3. The third result presented in the paper is in the same setting as above but without access to the simulator of MDP, which is a very challenging setting. The obtained regret bound is T^6/7, and it makes use of the assumption on the smallest eigenvalue of \Sigma_h.  4. All three results from above make use of dilated bonuses, which is the main contribution of this paper.  The use of the dilated bonuses that decrease the contribution to the regret, induced by the term appearing from the mismatch of q^*(x) and q(x), shows up in the analysis. To the best of my knowledge, this idea has not been considered before, and I think this idea is beneficial for future studies.  

The paper studies the regret of policy optimization for adversarial MDPs with bandit feedback. It develops a general solution that adds dilated bonuses to the policy update for exploration and applies the algorithm to the tabular, linear-Q, and linear MDP settings.   It shows that such a solution improves and generalizes the state-of-the-art.