A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Zhen Li * 1 Gilles Stoltz * 2 3
arXiv:2604.08149v1 [cs.LG] 9 Apr 2026
Abstract
Stochastic bandits in changing environments. In finitely-armed stochastic bandits (introduced by Thompson, 1933 Robbins, 1952; see also the survey monograph by Lattimore & Szepesvári, 2020), rewards are drawn i.i.d. from fixed but unknown distributions indexed by arms, and the learner must perform some trade-off between exploration (to estimate the distributions) and exploitation (to pull more often better-performing arms). A first extension of interest is called linear contextual bandits (see Chu et al., 2011 and Abbasi-Yadkori et al., 2011, where the celebrated LinUCB strategy was introduced), where the learner observes a context (possibly chosen adversarially), selects an action, and receives a reward modeled as a linear function of (some function of) the context and action.
We revisit the finite-armed linear bandit model by Nelson et al. (2022), where contexts and rewards are governed by a finite hidden Markov chain. Nelson et al. (2022) approach this model by a reduction to linear contextual bandits; but to do so, they actually introduce a simplification in which rewards are linear functions of the posterior probabilities over the hidden states given the observed contexts, rather than functions of the hidden states themselves. Their analysis (but not their algorithm) also does not take into account the estimation of the HMM parameters, and only tackles expected, not high-probability, bounds, which suffer in addition from unnecessary complex dependencies on the model (like reward gaps). We instead study the more natural model incorporating direct dependencies in the hidden states (on top of dependencies on the observed contexts, as is natural for contextual bandits) and also obtain stronger, high-probability, regret bounds for a fully adaptive strategy that estimates HMM parameters online. These bounds do not depend on the reward functions and only depend on the model through the estimation of the HMM parameters.
A second extension of interest is when this linear contextual model depends on some latent state changing over time. Two modelings and approaches were considered: first, some change-point detection approaches, relying on infrequent changes, with regret bounds typically functions of the root number of changes (see Wu et al., 2018 or Austin & Morgan, 2025); second, a modeling of the latent state as following some partially known dynamic, typically a Markov chain. Contexts are then typically assumed to follow a hidden Markov model [HMM]: they are drawn independently at random given the latent state. Much of this literature focuses on context-free reward models, where rewards depend on the actions and latent states but not on the observed contexts (when present, the latter are used only for state inference). For example, Azizzadenesheli et al. (2016) and Zhou et al. (2021) study such a setting and combine a LinUCB-style exploration with a spectral method for reward estimation. A common limitation due to the spectral method is to have to consider finite reward spaces, with Zhou et al. (2021) focusing, in particular, on binary rewards. In terms √ of guarantees, Azizzadenesheli et al. (2016) obtained an T – high-probability regret bound against a memoryless policy benchmark, whereas Zhou et al. (2021) provided a T 2/3 regret bound against a stronger oracle that knows the true belief and the state-dependent expected rewards.
1. Introduction and Related Works We revisit the setting of Nelson et al. (2022), which consists of linear contextual bandits with finitely many arms and with contexts governed by a hidden Markov model [HMM]. Before we explain in detail the extensions made, we position the problem within the broader context of stochastic bandits, and more particularly, of stochastic bandits in changing environments. 1
BNP Paribas, Paris, France 2 Université Paris-Saclay, CNRS, Inria, Laboratoire de mathématiques d’Orsay, 91405, Orsay, France 3 HEC Paris, Jouy-en-Josas, France. Correspondence to: Zhen Li <[email protected]>, Gilles Stoltz <[email protected]>.
To the best of our knowledge, few works only study linear contextual bandits in which the latent state governs the con-
Preprint. April 10, 2026.
1
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Contribution 2: Comparison. We formally compare the belief-dependent linear reward model of Nelson et al. (2022) to the state-dependent model studied here, showing in Section 3 that the former reduces to linear contextual bandits whereas the latter does not.
text distribution and, jointly with context and action, determine the rewards. Nelson et al. (2022) do so with a HMM modeling of contexts, but further assume that rewards are linear in (some function of) the action and in what is called the belief (the posterior distribution over latent states given past and present contexts), rather than being linear in (some function of) the action and the actual latent state. This is a seemingly harmless but actually major simplification of the problem, as we explain throughout this article. Nelson et al. (2022) propose Thompson-sampling and LinUCB-style algorithms and also provide some partiel elements for a theoretical analysis (however, not discussing the estimation of HMM parameters).
We further show in Appendix A that, under the beliefdependent linear reward model, even allowing contextual rewards and estimating the belief online (instead of assuming it is known as in Nelson et al., 2022), may be handled through a LinUCB-like analysis, up to an extra belief error term. This yields a high probability regret of order T 3/4 , where the extra T 1/4 factor is shown to only come from belief estimation. The analysis proposed in Appendix A is simple (much simpler than in the original reference) and directly exploits the reduction to linear contextual bandits.
Two recent works include Hong et al. (2020) and Galozy et al. (2025): they evaluate their algorithms against a strong benchmark that knows the realized latent states and the latent-state-dependent reward-model parameters. However, their regret guarantees require a sublinear number of latent-state changes and degrade to linear when switches occur at a linear rate.
We also discuss in Section 5.1 how the obtained regret bound is sharper and more general than the one by Nelson et al. (2022): in particular, it holds with high probability, not only in expectation, and is reward-model free. Outline
Main Contributions, Comparison to Nelson et al. (2022)
Section 2 introduces the setting and the general model of HMM-generated contextual bandits with rewards being state-dependent linear functions of the contexts and actions; in particular, this section introduces the corresponding notion of regret.
The contributions are twofold: first, being able to obtain sublinear high-probability regret bounds in a complex model more challenging than existing models; second, achieving an elementary, more direct, and more efficient treatment of the simpler model by Nelson et al. (2022) as a special case of the methodological developments made to tackle the more general problem considered.
Section 3 (continued in Appendix B) can be skipped in the first reading: it discusses the technical challenges overcome, all related to the intricate dependencies on observed quantities to the hidden states. It sheds light on the reasons for building a LinUCB-like strategy that proceeds in stages. It also compares the general reward model studied to the simplified version considered by Nelson et al. (2022).
Contribution 1: General model. First, we introduce around Equation (1) a general setting of linear contextual bandits with latent-state dynamics, where expected rewards depend linearly on (functions of) the contexts and actions, as well as on unobserved states (that follow a HMM). The rewards are continuously-valued. We explain why the seemingly similar dependence of rewards in Nelson et al. (2022) on beliefs, rather than directly on states, is actually an important simplification of the model. Therefore, prior work either assumed infrequent state changes, or considered reward models depending only on states and actions but not on contexts (with contexts only used for inference), or depending on contexts and actions but not directly on states, or restricted the rewards to a finite space. None provided sublinear regret bounds in our setting where rewards depends jointly on states, contexts, and actions, where states may switch arbitrarily often, and where these rewards are continuously-valued.
This staged LinUCB-like strategy is then formally stated in Section 4; it relies on belief-estimation subroutines, for which reminders are provided in Appendix C. A special case thereof, when stages only contain a single round, is able to handle the simplified model of Nelson et al. (2022). Section 5 states and provides sketches of proofs of the regret bounds of the strategies considered: a T 3/4 regret bound in the simplified model by Nelson et al. (2022) (see full details in Appendix A) and a T 7/8 regret bound in the general model (with full details provided in Appendix E). The second regret bound relies on forgetting properties of HMMs, for which reminders are provided in Appendix D.
2. Setting and Notation We describe the finite-armed contextual bandit setting considered by Nelson et al. (2022) and then state two versions of the reward functions, the original, simplified, version by
Our solution relies on an extremely careful analysis of the beliefs and of their stochastic properties, leading to a strategy proceeding in stages to carefully balance 2
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Nelson et al. (2022) in Section 3 and our own, more complex, version in this section. We also consider the same definition of regret as Nelson et al. (2022) but target highprobability bounds, not just bounds in expectation.
Nelson et al. (2022), as we argue below in Section 3.1. It is handy to assume some boundedness. Assumption 2.1 (bounds on the reward model). There exists Cθ ⋆ ∈ (0, +∞) such that for all a ∈ A, x ∈ X , h ∈ [H],
Notation. The short-hand xs:t stands for the sequence xs , . . . , xt . We let [H] = {1, . . . , H}. The vectors (1, . . . , 1) with all elements equal to 1 are denoted, independently of the lengths, by 1. The identity matrix of size s × s is denoted by Is . We denote the tensor product of two vectors u = (uh )h∈[H] ∈ RH and v ∈ Rd by u ⊗ v = (uh v)h∈[H] ∈ RdH . The Euclidean norm is denoted by k · k2 , and the ℓ1 –norm by k · k1 . For matrices M , the norm considered is the Frobenius norm, i.e., the Euclidean norm of the coefficients all written into a column vector; this is why we use the same notation kM k2 for this matrix norm. The norm induced on Rs by a symmetric definite positive matrix G of size s × s is defined by √ ∀u ∈ Rs , kukG = uT Gu .
|ϕ(a, x)T θ ⋆h | ⩽ 1 ,
kϕ(a, x)k2 ⩽ 1 ,
kθ⋆h k2 ⩽ Cθ ⋆ .
Learning protocol and information available. At each round t ⩾ 1, the learner observes the context xt (but not the latent state ht ), picks an action at ∈ A based on xt and on the information available from past rounds, and obtains and observes the reward rt (at ), but not the rewards rt (a) for actions a 6= at . The information available when picking at consists therefore of the past and present contexts (xτ )1⩽τ ⩽t and of the past rewards rτ (aτ ) 1⩽τ ⩽t−1 . We denote the filtration generated by this information by Ftobs = σ xτ , rτ (aτ ) τ ⩽t−1 , xt
For two symmetric matrices G, G′ , we write G G′ when G − G′ is a symmetric positive semi-definite matrix.
(where “obs” stands for observed): the action at is thus Ftobs –measurable.
2.1. Latent Dynamic and Learning Protocol
Assumptions on the noise term. A classic assumption in linear bandits (e.g., Abbasi-Yadkori et al., 2011) on the noise terms ηt (a) is that these terms are conditionally subGaussian, see Assumption 2.2. It turns out that following Nelson et al. (2022), a milder assumption on conditional first and second moments may be enough, see Assumption 2.3. We will consider the second assumption for stating our main results, though the stronger Assumption 2.2 will be useful for discussions and comparison to prior results.
We consider a finite-armed contextual bandit problem, with a finite action set A and with a m–dimensional context space X ⊆ Rm , equipped with the Borel σ–algebra. At each round t ⩾ 1, the learner observes some context xt ∈ X , generated by a hidden Markov model [HMM]. HMM modeling. More formally, there exists an underlying state ht ∈ [H], where [H] denotes the finite latent state space. The first state h1 is distributed according to some initial distribution denoted by π. At each round t ⩾ 1, the context xt is drawn independently at random given ht , according to an emission distribution over X denoted by νht . The next latent state ht+1 is then drawn according to a Markov model indexed by the transition matrix M = (Mh,h′ )(h,h′ )∈[H]2 , where Mh,h′ is the probability from moving from state h to state h′ .
For both assumptions, conditionings are taken with respect to all priori random variables, whether they are observed or not: we consider the filtration all Ft = σ hτ , xτ , ητ (a) a∈A , ht , x t . τ ⩽t−1
Assumption 2.2 (conditionally sub-Gaussian noise). There exists vη such that for all a ∈ A, 2 2 E eληt (a) | Ftall ⩽ eλ vη /2 . Note that this entails that E ηt (a) | Ftall = 0.
The (homogeneous) HMM is thus parameterized by the initial distribution π, the transition matrix M , and the emission distributions ν = (νh )h∈[H] , all unknown to the learner. Reward model—most complex one. We consider the following linear model: there exist a known transfer function ϕ : A × X → Rd and some unknown parameters θ⋆h ∈ Rd , where h ∈ [H], such that the reward rt (a) obtained with action a ∈ A at round t equals (1)
Assumption 2.3 (Bounded conditional second-order moment). There exists Cη such that for all a ∈ A, E ηt (a) | Ftall = 0 and E ηt (a)2 | Ftall ⩽ Cη .
where ηt (a) is a noise term, which we discuss below. This model is more complex than the simplified model by
The literature of bandits with latent space dynamics considers benchmarks involving beliefs about the hidden states,
rt (a) = ϕ(a, xt )T θ⋆ht + ηt (a) ,
2.2. Regret as a Performance Measure
3
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
3.1. The Simplified Model by Nelson et al. (2022)
i.e., posterior probabilities over the states, bnk
bnk
bnk
bt : h ∈ [H] 7−→ bt (h) = P(ht = h | Ft )
Nelson et al. (2022) consider the same latent dynamics and learning protocol as above but rather study the following ⋆ reward model: there exist scalars (θh,a )h∈[H],a∈A such that
for filtrations σ(x1:t ) ⊆ Ftbnk ⊆ Ftobs discussed below; these beliefs rely on the knowledge of the HMM parameters. The associated benchmarks are of the form X X T ⋆ bbnk E rt (a) | Ftbnk = max max t (h) ϕ(a, xt ) θ h , a∈A
a∈A
h∈[H]
rt′ (a) =
X
⋆ bt (h) θh,a + ηt′ (a) ,
(3)
h∈[H]
h∈[H]
where the noise terms ηt′ (a) satisfy Assumption 2.3. We rather consider an immediate generalization where expected rewards can depend directly on contexts and where general transfer functions are considered as in (1): X bt (h) θ⋆h + ηt′ (a) , (4) rt′ (a) = ϕ(a, xt )T
where the equality holds by the tower rule. Zhou et al. (2021) consider a model with {0, 1}–valued rewards and (only) because of that, may take Ftbnk = Ftobs . This choice however is somewhat unnatural, as the benchmark is not intrinsic and depends on the strategy used.
h∈[H]
In this article, we rather follow the more intrinsic choice by Nelson et al. (2022), which also does not put any restriction on the range of rewards: Ftbnk = σ(x1:t ), i.e., the beliefs are based only on contexts and no additional information from the complex dependencies of rewards on the hidden states is exploited. More formally, we consider the beliefs
The original model (3) corresponds to the special case ⋆ where θ⋆h = (θh,a )a∈A and ϕ(a, xt ) ∈ {0, 1}A with the a–th component equal to 1 and all other components being null. The difference between the model (1) we study in this article and the immediate generalization (3) of the model by Nelson et al. (2022) lies in replacing ϕ(a, xt )T θ⋆ht by X bt (h) θ ⋆h . E ϕ(a, xt )T θ⋆ht | x1:t = ϕ(a, xt )T
bt : h ∈ [H] 7−→ bt (h) = P(ht = h | x1:t ) and the associated pseudo-regret RT =
T X t=1
max a∈A
X
h∈[H]
h∈[H]
bt (h) ϕ(a, xt )T θ ⋆h −
T X X
This substitution looks harmless at first sight but has important consequences: the problem can be reduced to contextual bandits, as exploited by Nelson et al. (2022). Without this substitution, and when keeping the direct dependencies on the hidden states ht , no such reduction holds and an improved analysis is required. We now detail these claims.
bt (h) ϕ(at , xt )T θ ⋆h . (2)
t=1 h∈[H]
Remark 2.4. We can actually justify, by adapting the proof of Theorem 5.2 (and in particular, the one of Lemma E.2), that for the strategy considered (which proceeds in stages), T X t=1
rt (at ) and
T X X
Reduction of model (4) to linear contextual bandits. Introduce ′ Ft obs = σ xτ , rτ′ (aτ ) τ ⩽t−1 , xt .
bt (h) ϕ(at , xt )T θ ⋆h
t=1 h∈[H]
′
The action at picked in the model (4) is Ft obs –measurable. Also, the assumptions on the noise entail, by the tower rule, that for all a ∈ A, ′ ′ E ηt (a) | Ft obs = 0 , thus E ηt (at ) | Ft obs = 0 .
are close with high probability, up to a factor of the same order of magnitude as the bound guaranteed on the pseudoregret. Put differently, we could consider some actual regret, not only a pseudo-regret.
Because of the specific form of the reward model (4), these equalities translate into: X ′ bt (h) θ⋆h ∀a ∈ A, E rt′ (a) | Ft obs = ϕ(a, xt )T
3. Challenges Overcome We now explain how our work extends to the so-far best statement and analysis of a contextual bandit problem with latent dynamics, by Nelson et al. (2022): in a nutshell, we consider a direct dependency on the hidden state in the reward model (1), through the θ⋆ht term, while Nelson et al. (2022) considered instead a conditional expectation thereof. We explain that this seemingly harmless differences introduces new challenges, and we explain how we overcame them.
h∈[H]
X ′ bt (h) θ⋆h . E rt′ (at ) | Ft obs = ϕ(at , xt )T h∈[H] The vectors ϕ(a, xt )bt (h) h∈[H] act as contexts in linear contextual bandits. Nelson et al. (2022) only provide an analysis when these contexts are known (because the HMM parameters are assumed to be known) but with the and
4
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
techniques introduced in this article, these contexts may be be estimated (see Section 3.2) and the reduction to linear bandits can be saved.
are typically computed based on Bayes’ update rules (see Appendix C), and such rules work should then take rewards into account; this is what Zhou et al. (2021) performed in the case of Bernoulli rewards, but finding a general and computationally efficient solution beyond that case seems challenging.
See Appendix A for details and a regret analysis taking care of estimation errors: under Assumption 2.2, we obtain a e 3/4 ), where the exhigh probability regret bound of O(T e 1/4 ) term is due to belief estimation (recovering tra O(T e O(T 1/2 ) if the belief were known).
Ideas. The first idea is to not use rewards to estimate beliefs, and do so only independently, based on contexts; the loss in efficiency should be acceptable given the definition (2) of the pseudo-regret, which relies on beliefs bt estimated only based on the contexts. It turns out that such belief estimation only based on contexts is standard (see Appendix C): it suffices to estimate the HMM parameters, for which standard procedures exist, and estimation errors on the beliefs can be obtained as functions of the estimation errors of the HMM parameters.
There is no such reduction in the reward model (1) primarily studied in this article, where reward depend directly on the hidden states ht . Issues with model (1) due to direct dependencies on ht . Consider any filtration Ft such that σ(x1:t ) ⊆ Ft ⊆ Ftobs . In model (1), we have, still by the assumptions on the noise terms and by the tower rule: for all a ∈ A, X P(ht = h | Ft ) θ⋆h (5) E rt (a) | Ft = ϕ(a, xt )T
The second idea is to design the filtration Ut so that bt (h) = P(ht = h | x1:t ) and bt (h) = P(ht = h | Ut )
h∈[H]
are close, while maintaining the Ut –measurability of at , i.e., including enough information on past rewards in Ut .
This equality extends to rt (at ) provided that at is Ft – measurable. A second constraint to save the reduction to linear contextual bandits is that P(ht = h | Ft ) can be easily estimated. There is a tension between the two objectives and the two extreme candidates σ(x1:t ) and Ftobs . First, the natural filtration to get measurability of at is Ftobs ; indeed, the actions picked at depend on the rewards obtained in the past, not only on the contexts. Note that
Solution. The solution is essentially based on a typical property of HMMs: that they forget exponentially fast the initial state. Put differently, after a sufficient time, HMMs not initialized with the same distributions over states are almost equal in distributions. This property suggests to work in stages: we update only periodically the Ut to include a new sufficient statistic based on the rewards of the stage just passed.
P(ht = h | x1:t , at ) and bt (h) = P(ht = h | x1:t ) are different in general. Indeed, the action at depends on past rewards, and therefore depends on ht−1 , which entails some dependency between at and ht . More generally,
These sufficient statistics consist of estimates of the parameters (θ ⋆h )h∈[H] of the reward model. The actions at are picked based on the latest such estimates available (and on the estimated beliefs), in an optimistic fashion, through the consideration of an upper confidence bound.
P(ht = h | Ft ) and bt (h) = P(ht = h | x1:t ) are different in general when at is Ft –measurable. Second, the natural filtration to estimate easily the beliefs P(ht = h | Ft ) is σ(x1:t ): we discard reward and may then open the toolbox of HMM estimation. Also, the pseudo-regret is formulation in terms of beliefs based on σ(x1:t ).
3.3. Other Technical Tool from Nelson et al. (2022) A final ingredient in our solution, discussed next, is to leverage an approach by Nelson et al. (2022) for proving deviation inequalities in cases where the LinUCB approach by Abbasi-Yadkori et al. (2011) is not applicable. Provided that they strengthen a bit their assumption on the noise terms from a second-order moment assumption (Assumption 2.3) to a well-accepted sub-Gaussian (Assumption 2.2), Nelson et al. (2022) could have resorted to the classic LinUCB tools, with absolutely no need of HMM forgetting properties (like Assumption 5.1), to get their regret bound; see details in Appendix A.
Our solution basically consists of introducing a carefully constructed filtration in the middle of these two extremes; we denote it by Ut . 3.2. Caveats Encountered when Estimating Beliefs Difficulty. As explained above, the action at needs to be Ut –measurable. Now, to make useful decisions, the filtration Ut cannot be reduced to just contexts and thus needs to include at least some (quantities based on the) rewards. However, beliefs are then difficult to compute even with the knowledge of the underlying HMM parameters, and thus are even more difficult to estimate. Indeed, beliefs
However, they relaxed the assumption on the noise and resorted instead to an L2 –Markov inequality (suited for random variables with second-order moments, that are not necessarily sub-Gaussian), as outlined stylized quantities in 5
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
δ ∈ (0, 1),
Appendix B.
4. Staged LinUCB on Estimated Beliefs
X
t∈[T ]
In this section, we both present our main strategy (Box A) addressing the most complex reward model of Equation (1), as well as a special case thereof addressing the simplified model of Equation (4) but in more generic way than in Nelson et al. (2022), as we do not fix a specific belief estimation subroutine (online expectation-maximization in their case) but consider any efficient such subroutine (see Assumption 4.1). We discuss these subroutines first (in Section 4.1) and then state the strategies (in Section 4.2).
e T 1/2 , Ubelief (t, δ) = O
such that for all δ ∈ (0, 1), with probability at least 1 − δ, the following statements hold for all t ⩾ TB,M,ν 1 + ln(1/δ) : • first, the labeling of hidden states is consistent over the rounds considered; w w bt − bt w1 ⩽ Ubelief (t, δ). • second, wb
In the HMM literature, belief estimation is more commonly referred to as the estimation of the filtering distributions. The hidden state space is typically assumed to be finite, while the context space may be finite or continuous. For the sake of exposition, and since the belief estimation is used here only as an independent subroutine, we will mostly focus on the case of a finite context set.
4.1. Belief Estimation Subroutines As justified in Sections 2.2 and 3.2 and as in Nelson et al. (2022), due to the complex dependencies between rewards and hidden states, we estimate beliefs only based on contexts. We therefore define a belief estimation subroutine B as a sequence of functions where the t–th function
Example 1: Spectral method for finite context sets X . The so-called spectral method was proposed by Hsu et al. (2012) and further developed by Anandkumar et al. (2012) and Anandkumar et al. (2014). It provides estimates of the HMM transition matrix M and of the emission distributions νh . De Castro et al. (2017) show how the performance of these estimates, combined with the Bayes’ update rule, transfers into a performance bound on estimated beliefs of the form of Assumption 4.1. This is formally stated in Lemma 4.3 below.
x1 , . . . , xt 7−→ b bt = b bt (h) h∈[H]
associates with the contexts x1 , . . . , xt a probability distribution b bt over the hidden state spaces [H].
We provide no methodological development on the estimation of beliefs and instead resort to known results, up to one addition. The estimation of HMM parameters, and thus of beliefs, requires knowing the number H of hidden states but only provides estimates that are correct up to permutations of the hidden states (as the latter have no specific ordering). This is why estimation guarantees are only formulated in norms. However, the strategy considered (see Box A) must keep track of specific states, as it will maintain estimators for each parameter θ⋆ . That the labeling of hidden states is consistent throughout time will be vital. We achieve this through an additional alignment step. See details on this issue and on the solution in Appendix C
Assume that the context set X is finite, so that each emission distribution νh on X may be seen as a column vector, and let E denote the emission matrix, indexed by X × [H], obtained by concatenating the vectors νh as h ∈ [H]. We assume below that E has full column rank: this imposes, in particular, that H is smaller than the cardinality X of X . Recall that σ is a singular value of E if σ 2 is an eigenvalue of the square matrix ET E.
To make our arguments generic, we consider the following assumption on the belief-estimation subroutine B; examples and pointers below explain why it is a reasonable assumption (and to which large classes of hidden Markov chains it applies).
Assumption 4.2. The context set X is finite, with cardinality denoted by |X | = X. The emission matrix E has full column rank with smallest singular value σmin (E) > 0, and its smallest element satisfies def eν,min = min min νh (x) > 0 .
Assumption 4.1 (belief estimation error). The belief estimation procedure B is such that for all hidden Markov chains (π, M , ν) in a wide class, there exist
The transition matrix M is invertible, with smallest eigenvalue denoted by σmin (M ) > 0, and the smallest element of M is positive: εM = min′ Mh,h′ > 0.
• a constant TB,M,ν not necessarily known to the learner, • a fully known belief error function Ubelief on {1, 2, . . .} × (0, 1), where Ubelief (t, δ) depends logarithmically on δ and, up to poly-log factors, for each
Finally, the initial distribution π is the (unique) stationary distribution of M .
h∈[H] x∈X
h,h
Appendix C reviews the literature necessary to obtain the guarantee stated in Lemma 4.3 (whose proof may be found 6
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
in Appendices C.1 and C.2), and also provides more details on the underlying belief estimation procedure (namely, the spectral method combined with a Bayes’ update rule).
Within a stage, rewards are estimated by estimates of their conditional means ϕ(a, xt )T θ⋆ht , of the form X b(s−1)ℓ,h + εt,a , b bt (h)ϕ(a, xt )T θ
Lemma 4.3. Assumption 4.1 is satisfied for all hidden Markov chains of Assumption 4.2, for the spectral method (followed by an alignment step) combined with the Bayes’ update rule, with the known belief error function Ubelief (t, δ) = √ ln(t) H X
s
h∈[H]
where the εt,a are confidence bonuses. The strategy considered is optimistic and plays arms that maximize the upper confidence estimates defined above.
! √ 2 ln 6Xt(t + 1)/δ − t−1 +e t
The resulting strategy, called staged LinUCB on estimated beliefs, is formally stated in Box A. B OX A: S TAGED L IN UCB ON ESTIMATED BELIEFS
and the unknown threshold TB,M,ν whose closed-form expression is provided in Equation (30).
Known parameters: finite action set A; context set X ; transfer function ϕ : A × X → Rd ; finite state space [H] Unknown parameters: HMM parameters, given by a transition matrix M = (Mh,h′ )(h,h′ )∈[H] and emission distributions (νh )h∈[H] over X ; reward parameters θ⋆h ∈ Rd , for h ∈ [H]
Example 2: More general context sets X . De Castro et al. (2017) extended the spectral method and its analysis to the case of continuously-valued contexts, under an assumption that contexts are continuously projectable into a finite-dimensional feature space via basis functions such as splines, trigonometric functions, or wavelets.
Inputs: risk δ ∈ (0, 1); belief estimation subroutine B; stage length ℓ ⩾ 1; regularization parameter λ > 0; closed-form expression for the confidence bonuses εt,a , possibly depending on δ, λ, and ℓ b0 = (1/λ) 1 ∈ RdH Initialization: set θ
4.2. LinUCB Strategies on Estimated Beliefs For any probability distribution b over [H], we use the short-hand notation, for all a ∈ A and x ∈ X , b ⊗ ϕ(a, x) = b(h)ϕ(a, x) h∈[H] ∈ RdH , X T b(h) ϕ(a, x)T θ ⋆h = b ⊗ ϕ(a, x) θ⋆ . so that
For stages s = 1, 2, . . . : For rounds t = (s − 1)ℓ + 1, . . . , sℓ, the learner: 1. Observes the context xt , drawn independently by the environment from νht ; 2. Obtains the belief estimate b bt by feeding x1 , . . . , xt to the subroutine B; 3. Computes estimated rewards: for all a ∈ A, X b(s−1)ℓ,h ; b bt (h)ϕ(a, xt )T θ rbt (a) = h∈[H] 4. Picks action at = argmax rbt (a) + εt,a
h∈[H]
Note that by Assumption 2.1, which considers the Euclidean norm in Rd , and the fact that b is a probability distribution, we also have, for the Euclidean norm in RdH , w w wb ⊗ ϕ(a, x)w ⩽ 1 . (6) ∀a ∈ A, ∀x ∈ X , 2
We estimate the stacked vector θ⋆ = (θ⋆h )h∈[H] ∈ RdH through a LinUCB-style (Abbasi-Yadkori et al., 2011) approach: let λ > 0 and introduce, for t ⩾ 1, the (symmetric definite positive thus invertible) Gram matrix
a∈A
5. Obtains and observes the reward
rt (at ) = ϕ(at , xt )T θ⋆ht + ηt (at ) ;
end bsℓ as in Equation (7). Computes θ end
t X T def b bτ ⊗ ϕ(aτ , xτ ) b bτ ⊗ ϕ(aτ , xτ ) + λIdH , Gt = τ =1
based on which we define the estimates t X b bt = G−1 bτ ⊗ ϕ(aτ , xτ ) rτ (aτ ) . θ t
(7)
Strategy in the simplified model (4). Our generic version of the strategy by Nelson et al. (2022) is given by the Box-A strategy run with ℓ = 1, i.e., updating the LinUCB estimates of θ ⋆ at each round, and with the rewardobtention step (numbered 5 in Box A) of course replaced by Equation (4). For the sake of clarity, we state separately this strategy in Box B of Appendix A.
τ =1
Strategy in the most complex reward model (1). As justified in Section 3.2, we consider a strategy that works in stages of lengths ℓ ⩾ 1 and only performs the estimations (7) periodically, at rounds t multiple of ℓ. This defines stages, where stage s ⩾ 1 gather rounds (s − 1)ℓ + 1 to sℓ. 7
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics (a)
5. Regret Bounds
Note that the sum in the definition of G̃t is restricted to rounds t such that a⋆t = a, where X bt (h) ϕ(a, xt )T θ⋆h . a⋆t ∈ argmax
In this section, we present regret analyses both for the main strategy of Box A addressing the most complex reward model (1), as well as its special case addressing the simplified model of Equation (4) (see the paragraph above). We start with the latter as it can be performed with no additional assumption.
a∈A
This implies that the population design matrix grows linearly in all directions. We do not impose such a coverage assumption; instead, we only use 1/λmin (Gt ) ⩽ 1/λ, which leads to a larger regret rate but avoids this additional condition.
5.1. Regret Bound for the Simplified Model (4) In Appendix A, we state (Theorem A.1) and show that under Assumption 2.2 (sub-Gaussian noise), Assumption 4.1 (on the belief estimation subroutine), and Assumption 2.1 (boundedness of rewards), with proper inputs, the strategy in the simplified model (4) described above satisfies, with probability at least 1 − δ, up to poly-log factors, e T 3/4 , RT = O
In a nutshell, we leverage the reduction to contextual linear bandits proposed by Nelson et al. (2022) a in a more direct and more efficient way. 5.2. Regret Bound for the Most Complex Model (1) We require a final, classic (see Cappé et al., 2005), assumption on the HMM: that it satisfies some fast forgetting property. Details, exemples, and further references (including the alternative forgetting condition assumed by Nelson et al., 2022) are provided in Appendix D.3. Assumption 5.1 (exponentially fast forgetting of initial condition). There exists a constant γ ∈ [0, 1) so that, for all s ⩽ t, for all pairs h, h′ ∈ [H] of hidden states, X P{hs =h} (ht = j | xs+1:t )
where a closed-form expression of the regret bound may be found in the proof, see Equation (21).
Comparison to Nelson et al. (2022, Theorem 2). First, Nelson et al. (2022, Theorem 2) do not take into account the belief estimation error into account in their regret bound, which, in addition, only holds in expectation; they √ obtain a T rate and the proof of Theorem A.1 shows that the worsened rate T 3/4 is only due to the belief estimation error.
j∈[H]
Second, Nelson et al. (2022, Theorem 2) consider a milder noise condition (Assumption 2.3 instead of Assumption 2.2) but to do so, require a forgetting condition (as Assumption 5.1 below). We instead provide a more direct analysis, close to the standard LinUCB analysis and not requiring this forgetting condition; see Appendix A.
Fourth, Nelson et al. (2022, Theorem 1) also impose a nondegeneracy assumption on its population design matrix, which can be stated as follows in our extended setting, denoting by λmin the smallest eigenvalue: for all actions a ∈ A, T →∞
(a)
(a)
G̃t
=
> 0,
− P{hs =h′ } (ht = j | xs+1:t ) ⩽ 2γ t−s .
We may now state our main result. The T 7/8 rate achieved therein must be contrasted with the T 3/4 rate discussed in Section 5.1 above: the price to pay for facing the actual latent model (and not an overly simplified version thereof) is a T 1/8 factor, mostly due to the necessity of proceeding in stages (see Section 3.2). Theorem 5.2. Assume the horizon T is known to the learner and fix δ ∈ (0, 1). Consider the strategy of Box A with a belief estimation subroutine satisfying Assumption 4.1, with parameters λ = T 3/4 and√ℓ = ⌈T 3/4 ⌉, as well as the confidence bonuses εt,a = 1+ d/λ for t ∈ [1, ℓ] and for t ⩾ ℓ + 1, w w w −1 w b w εt,a = Ubelief (t, δ/2) + ft w G b ⊗ ϕ(a, x ) t w w (st −1)ℓ t 2 s √ sT (st − 1)(1 + st γ)ℓ + where ft = λ H Cθ ⋆ + 4 δ(1 − γ) r (st −1)ℓ X 2(st − 1)γ 4sT Cη (st − 1)ℓ + + Ubelief (τ, δ/2) δ 1−γ τ =1
Third, the bound of Nelson et al. (2022, Theorem 2) is an expected bound, and not a bound in high probability; it involves constants that heavily depend on the problem, in particular, on the reward gaps, while the bound achieved in Theorem A.1 is model-free for the part not linked to the estimation of HMM parameters, see Equation (21).
lim inf λmin G̃t
h∈[H]
where
T T i 1 X h bt ⊗ϕ(a, xt ) . bt ⊗ϕ(a, xt ) b E 1{a=a⋆t } b T t=1
and where st = ⌈t/ℓ⌉ denotes the stage to which round t belongs. Then, under Assumption 2.1 (boundedness of rewards), Assumption 2.3 (sub-Gaussian noise), 8
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Assumption 4.1 (controlled belief estimation error), and Assumption 5.1 (exponentially fast forgetting), with probability at least 1 − δ, up to poly-log factors, e T 7/8 . RT = O
kbt − b bt k1 , which is manageable thanks to the estimation Assumption 4.1; and second,
5.3. Proof Sketch for Theorem 5.2
where the equality follows by substituting the very b(s −1)ℓ and where the exact defidefinition of θ t nitions of the three S terms are in Appendix E. We handle the term in the display above by a Cauchy-Schwarz inequality and the boundedness Assumption 2.1, together with the fact the Euclidean ′ ′ ′ norms kSdiff,(s k, kSbelief,(s k, kSeta,(s k t −1)ℓ t −1)ℓ t −1)ℓ behave respectively as the absolute values of
T b b(s −1)ℓ bt ⊗ ϕ(a, xt ) θ⋆ − θ t T = b bt ⊗ ϕ(a, xt ) G−1 (st −1)ℓ ×
A closed-form expression of the regret bound may be found in the proof, see Equations (47) and (48).
′ ′ ′ Sdiff,(s + Sbelief,(s + Seta,(s − λIdH θ⋆ t −1)ℓ t −1)ℓ t −1)ℓ
The full proof of Theorem 5.2 may be found in Appendix E. We introduce a filtration augmented by the algorithmic upbsℓ computed at the end dates, by considering the estimates θ of past complete stages s ⩽ st − 1 on top of contexts x1:t : bsℓ . Ut = σ x1:t , θ s⩽st −1
(s−1)ℓ
S
The key of the proof, as discussed in Section 3.2, is that this filtration is such that at is Ut –measurable (by design, thanks to staging in Box A) while bt (h) = P(ht = h | Ut ) and bt (h)
(s−1)ℓ
Sb =
(s−1)ℓ
Sη =
h∈[H]
t∈[T ]
which is seen
e T 7/8 =O
ητ (aτ ) .
(s−1)ℓ X w X w w w wb̄τ − bτ w + wbτ − b bτ w , 1
τ =1
1
τ =1
where Equation (8) and Assumption 4.1 take respective care of each sum. The term S η could be bounded by resorting to martingale arguments (like in the LinUCB analysis, though we rather mimic for it in Appendix E the proof scheme used for S ∆ and described next).
b b(s −1)ℓ,h ⩽ εt,a + 2T0 /λ , (9) bt (h)ϕ(a, xt )T θ t
εt,at
X
bτ (h′ ) , ϕ(aτ , xτ )T θ⋆h′ b̄τ (h′ ) − b
(s−1)ℓ
bt (h)ϕ(a, xt )T θ⋆h
X
X
Now, the term S b may be bounded by
The term S ∆ is the term that is difficult to control, see the discussions in Section 3.3 and Appendix B: LinUCB-type analyses are not applicable. Indeed, denoting X ⋆ ⋆ T b̄τ (h)θ h , zτ = ϕ(aτ , xτ ) θ hτ −
where T0 is essentially the unknown constant threshold of Assumption 4.1. Based on that, classic manipulations entail that the pseudo-regret RT is essentially bounded by 2
h′ ∈[H]
τ =1
h∈[H]
X
X
X ⋆ ′ ⋆ b̄τ (h )θ h′ , ϕ(aτ , xτ ) θ hτ − T
τ =1 h′ ∈[H]
(8)
Summing confidence bounds. The core of the proof is to show that the confidence bonuses εt,a in Theorem 5.2 satisfy, with high probability, uniformly over T0 ⩽ t ⩽ T and a ∈ A, that
−
=
X
τ =1
are close enough; this may be guaranteed by Assumption 5.1 (exponentially fast forgetting condition).
X
∆
h∈[H]
where |zτ | ⩽ 2 by Assumption 2.1; we have that E zτ | Uτ = 0
by substituting classic linear-algebra bounds (the socalled elliptic potential lemma, adapted to stages, see Abbasi-Yadkori et al., 2011, Section C) and by carefully picking λ and ℓ to optimize the bound.
but zτ is not Uτ –measurable (as it explicitly depends on hτ ). However, we follow instead an approach by Nelson et al. (2022), which consists of controlling S ∆ in L2 –norm and applying Markov’s inequality: thanks to Assumption 5.1 (exponentially fast forgetting condition),
Thus, the core of the proof is to show (9). Three sums, including a difficult one. The left-hand side of (9) is bounded by the sum of two terms; first, 9
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
E[zτ zτ ′ ] is exponentially small when τ and τ ′ are separated, so that E (S ∆ )2 is of order sℓ , hence, |S ∆ | is smaller than least 1 − δs .
p sℓ/δs with probability at
Collecting all elements, together with careful union bounds (taking δs = δ/sT , where sT denotes the stage of T ), concludes the proof. Again, the complete proof of Theorem 5.2 may be found in Appendix E.
6. Limitations and Future Work The main open questions are around optimality: first, showing that a T 3/4 rate on the pseudo-regret is inevitable, even in the simplified reward model, due to belief estimation; second, possibly improving the T 7/8 rate in the most complex reward model into a T 3/4 rate by finding a more efficient argument than the L2 –Markov exhibited. Indeed, the latter √ entails dependencies onpthe probabilities of failure as 1/ δs , instead of typical ln(1/δs ) dependencies under exponential-martingale arguments, and this worsened dependency comes at a polynomial cost in the final regret bound.
10
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Impact Statement
De Castro, Y., Gassiat, E., and Le Corff, S. Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden markov models. IEEE Transactions on Information Theory, 63(8):4758–4777, 2017.
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.
Ding, J. and Zhou, A. Eigenvalues of rank-one updated matrices with some applications. Applied Mathematics Letters, 20(12):1223–1226, 2007.
References Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Galozy, A., Nowaczyk, S., and Ohlsson, M. A new bandit setting balancing information from state evolution and corrupted context. Data Mining and Knowledge Discovery, 39(1):9, 2025.
Anandkumar, A., Hsu, D., and Kakade, S. M. A method of moments for mixture models and hidden markov models. In Conference on learning theory, pp. 33–1. JMLR Workshop and Conference Proceedings, 2012.
Hong, J., Kveton, B., Zaheer, M., Chow, Y., Ahmed, A., Ghavamzadeh, M., and Boutilier, C. Non-stationary latent bandits. arXiv preprint arXiv:2012.00386, 2020.
Anandkumar, A., Ge, R., Hsu, D. J., Kakade, S. M., Telgarsky, M., et al. Tensor decompositions for learning latent variable models. J. Mach. Learn. Res., 15(1):2773–2832, 2014.
Hsu, D., Kakade, S. M., and Zhang, T. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 78(5):1460–1480, 2012. Kontorovich, A. and Weiss, R. Uniform chernoff and dvoretzky-kiefer-wolfowitz-type inequalities for markov chains and related processes. Journal of Applied Probability, 51(4):1100–1113, 2014.
Austin, E. and Morgan, L. E. Detecting changes and anomalies in nonstationary contextual bandits with an application to task categorisation. Information Sciences, pp. 122270, 2025.
Krishnamurthy, V. Partially observed Markov decision processes. Cambridge university press, 2016.
Azizzadenesheli, K., Lazaric, A., and Anandkumar, A. Reinforcement learning of pomdps using spectral methods. In Conference on Learning Theory, pp. 193–256. PMLR, 2016.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020. Nelson, E., Bhattacharjya, D., Gao, T., Liu, M., Bouneffouf, D., and Poupart, P. Linearizing contextual bandits with latent state dynamics. In Uncertainty in Artificial Intelligence, pp. 1477–1487. PMLR, 2022.
Boyen, X. and Koller., D. Tractable inference for complex stochastic processes. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, UAI’98, pp. 33–42, 1998.
Robbins, H. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527–535, 1952.
Brégère, M., Gaillard, P., Goude, Y., and Stoltz, G. Target tracking for contextual bandits: Application to demand side management. In International Conference on Machine Learning, pp. 754–763, 2019.
Thompson, W. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285–294, 1933.
Cappé, O., Moulines, E., and Rydén, T. Inference in Hidden Markov Models. Springer Science & Business Media, 2005.
Wu, Q., Iyer, N., and Wang, H. Learning contextual bandits in a non-stationary environment. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 495–504, 2018.
Carpentier, A., Vernade, C., and Abbasi-Yadkori, Y. The elliptical potential lemma revisited. arXiv preprint arXiv:2010.10182, 2020.
Zhou, X., Xiong, Y., Chen, N., and GAO, X. Regime switching bandits. In Advances in Neural Information Processing Systems, volume 34, 2021.
Chu, W., Li, L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AIStats’11), volume 15, pp. 208– 214, 2011. 11
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
A. Algorithm and Analysis for the Simplified Reward Model of Nelson et al. (2022) Section 3.1 indicated that (a generalized version of) the simplified reward model by Nelson et al. (2022) may be stated as rt′ (a) =
X
bt (h) ϕ(a, xt )T θ⋆h + ηt′ (a) ,
bt (h) = P(ht = h | x1:t )
where
h∈[H]
and where here, we assume that the noise terms satisfy a sub-Gaussian assumption as in Assumption 2.2: denoting by ′
Ft all = σ
hτ , xτ , ητ′ (a) a∈A
τ ⩽t−1
, ht , xt
the filtration with respect to all random variables anterior to the ηt′ (a), there exists vη such that for all a ∈ A, ′ E ηt (a) | Ft all = 0
′ ′ 2 2 E eληt (a) | Ft all ⩽ eλ vη /2 .
and
(10)
Aim of this appendix. This appendix recalls the main claim by Nelson et al. (2022), namely, how a reduction to standard contextual linear bandits may be performed for the reward model above. Unlike Nelson et al. (2022), we also provide a straightforward analysis based on the LinUCB analysis, taking into account the belief estimation error (see Appendix C for a description of a belief estimation routine and its associated guarantees), and yielding high-probability bounds (not only bounds in expectation); no HMM forgetting properties are required to that end. Actually, the more complex analysis by Nelson et al. (2022), which, in particular, relies on HMM forgetting properties (as in Assumption 5.1, see more generally Appendix D.3), is only required because of the relaxation considered on the noise terms: Nelson et al. (2022) only assume that conditional second-order moments are bounded, as in Assumption 2.3. We see this relaxation as unimportant. Algorithm. We use the reduction to contextual linear bandits pointed out by Nelson et al. (2022), discussed in Section 3.1, and relying on the rewriting rt′ (a) =
X
h∈[H]
T bt (h) ϕ(a, xt )T θ⋆h + ηt′ (a) = bt ⊗ ϕ(a, xt ) θ⋆ + ηt′ (a) ,
where
θ ⋆ = θ⋆h h∈[H] ;
the quantities bt ⊗ ϕ(a, xt ) act as (unknown) contexts and mean rewards depend linearly on them, via the dH–dimensional parameter θ⋆ . We also consider a belief estimation subroutine B, as discussed in Section 4.1 (see also Appendix C), so as to replace the unknown contexts by known estimated contexts. Fix a regularization parameter λ > 0. At the end of each round t ⩾ 1, the algorithm computes t X def −1 b bt = θ bt,h bτ ⊗ ϕ(aτ , xτ ) rτ′ (aτ ) , = G θ t h∈[H] τ =1
where
def
Gt =
t X
τ =1
T b bτ ⊗ ϕ(aτ , xτ ) b bτ ⊗ ϕ(aτ , xτ ) + λIdH , (11)
based, in particular, on the estimated belief b bt obtained from B at the beginning of round t. Then, in the next round t + 1, mean rewards
X
bt+1 (h) ϕ(a, xt+1 )T θ⋆h
are estimated by
h∈[H]
def
rbt+1 (a) =
X
h∈[H]
b bt,h . bt+1 (h) ϕ(a, xt+1 )T θ
The action at+1 to be played at round t + 1 is picked in an optimistic way as the action maximizing rbt+1 (a) plus some confidence bonus over a ∈ A. The corresponding algorithm is formally stated in Box B. It corresponds to a LinUCB approach (Abbasi-Yadkori et al., 2011) with contexts computed based on estimated beliefs; the mere difference to the main algorithm of Box A is that it does not proceed in stages. 12
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
B OX B: L IN UCB ON ESTIMATED BELIEFS ( WITHOUT STAGES ) Known parameters: finite action set A; finite state space [H]; context space X ; transfer function ϕ : A × X → Rd Unknown parameters: HMM parameters, given by a transition matrix M = (Mh,h′ )(h,h′ )∈[H] and emission distributions (νh )h∈[H] over X ; reward parameters θ⋆h ∈ Rd , for h ∈ [H] Inputs: risk δ ∈ (0, 1); belief estimation subroutine B (see Section 4.1); regularization parameter λ > 0; closedform expression for the confidence bonuses εt,a , possibly depending on δ and λ b0 = (1/λ) 1 ∈ RdH Initialization: the learner sets θ
For rounds t ⩾ 1 the learner:
1. Observes the context xt , drawn independently by the environment from νht 2. Obtains the belief estimate b bt by feeding x1 , . . . , xt to the subroutine B; X bt−1,h b bt (h) ϕ(a, xt )T θ 3. Computes the estimated mean rewards rbt (a) = 4. Picks an action at ∈ argmax rbt (a) + εt,a ; a∈A
rt′ (at ) =
5. Obtains and observes the reward
h∈[H]
X
for all a ∈ A;
bt (h) ϕ(at , xt )T θ⋆h + ηt (at ) ;
h∈[H]
bt as in Equation (11). 6. Computes θ
Analysis. At a high level, the analysis adapts the LinUCB proof to handle the substitution of the true contexts bt ⊗ϕ(a, xt ) by estimations thereof. We follow closely classic analyses of LinUCB (the original reference by Abbasi-Yadkori et al., 2011, the monograph by Lattimore & Szepesvári, 2020, Chapters 19 and 20, as well as the extension by Brégère et al., 2019), with occasional simplifications or shortcuts—e.g., we avoid stating confidence ellipsoids on the θ⋆h and rather focus on confidence intervals on the mean payoffs, as studied in Lemma A.2 below. The bounds obtained in the sequel corresponds to the classic bound when b bt = bt , i.e., if there was no estimation error for the beliefs. The formal aim is to prove the following theorem. Theorem A.1. Assume that the horizon T is known to the learner and fix δ ∈ (0, 1). Consider the strategy of Box B with a belief estimation subroutine satisfying Assumption 4.1, with λ = T 1/2 and with the confidence bonuses (14). Then, under the boundedness stated in Assumption 2.1 and under the sub-Gaussian noise assumption (10), with probability at least 1 − δ, up to poly-log factors, e T 3/4 , RT = O where a closed-form expression of the regret bound may be found in the proof, see Equation (21).
The total regret bound is basically given by 2 times the sum of the upper confidence bounds of Lemma A.2 below, which we prove first. Lemma A.2. Under Assumption 2.1 and for sub-Gaussian noise terms as in Equation (10), with probability at least 1 − δ, for all t ⩾ 2, ∀a ∈ A,
X
h∈[H]
bt (h) ϕ(a, xt )T θ⋆h −
w w w w w w ⩽ wbt − b bt w1 + wb bt ⊗ ϕ(a, xt )w −1
Gt−1
X
h∈[H]
t−1
bt−1,h b bt (h) ϕ(a, xt )T θ
√ 1 X √ kbτ − b bτ k1 + λH Cθ ⋆ + vη λ τ =1
! q 2 ln(1/δ) + dH ln 1 + t/(λdH) .
b1 are probability vectors, and a In the case t = 1, by several triangle inequalities, Assumption 2.1, the fact that b1 and b Cauchy-Schwarz inequality, we have, with probability 1: for all a ∈ A, √ ⩽ d/λ
√ }| { z z }| { X X d Tb T ⋆ T ⋆ Tb b b1 (h) ϕ(a, xt ) θ0,h ⩽ max ϕ(a, xt ) θh + max ϕ(a, xt ) θ0,h ⩽ 1 + b1 (h) ϕ(a, x1 ) θh − , h∈[H] h∈[H] λ ⩽1
h∈[H]
h∈[H]
13
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
w √ w w b0,h = 1 ∈ Rd . θ 0,h w2 ⩽ 1 × d/λ, since θ where we resorted to the Cauchy-Schwarz inequality kϕ(a, x1 )w2 wb Proof. By a triangle inequality and by the boundedness stated in Assumption 2.1, X
h∈[H]
bt (h) ϕ(a, xt )T θ⋆h −
X
h∈[H]
bt−1,h b bt (h) ϕ(a, xt )T θ
⩽
X
h∈[H]
|
| · |⩽1
}| { X z b bt−1,h . (12) bt (h) − b bt (h) ϕ(a, xt )T θ⋆h + bt (h)ϕ(a, xt )T θ ⋆h − θ {z
}
⩽kbt −b bt k1
h∈[H]
|
{z
}
bt−1 ) =(b bt ⊗ϕ(a,xt ))T (θ⋆ −θ
The rest of the proof bounds the second term in the upper bound of Equation (12). To that end, we rewrite rτ′ (aτ ) as T T rτ′ (aτ ) = (bτ − b bτ ) ⊗ ϕ(aτ , xτ ) θ⋆ + b bτ ⊗ ϕ(aτ , xτ ) θ⋆ + ητ (aτ )
and also note that by the definition of Gt−1 in Equation (11), θ
⋆
bt−1 = G−1 −θ t−1
= G−1 t−1
⋆
Gt−1 θ − ⋆
λθ −
t−1 X
τ =1
t−1 X
τ =1
! ′ b bτ ⊗ ϕ(aτ , xτ ) rτ (aτ )
! T ⋆ ′ b b . bτ ⊗ ϕ(aτ , xτ ) rτ (aτ ) − bτ ⊗ ϕ(aτ , xτ ) θ
Thanks to these two equalities, we may decompose the second term in the upper bound of Equation (12) as T T ⋆ b bt−1 ) = b bt ⊗ ϕ(a, xt ) (θ⋆ − θ bt ⊗ ϕ(a, xt ) G−1 t−1 λθ − Sdiff,t−1 − Seta,t−1
where
Sdiff,t−1 =
t−1 X
τ =1
T b bτ ⊗ϕ(aτ , xτ ) (bτ −b bτ )⊗ϕ(aτ , xτ ) θ⋆
and Seta,t−1 =
t−1 X
τ =1
b bτ ⊗ϕ(aτ , xτ ) ητ (aτ ) .
−1 A Cauchy-Schwarz inequality for the inner product induced by Gt−1 , together with a triangle inequality, entails
w w T w b bt−1 ) ⩽ w bt ⊗ ϕ(a, xt ) (θ⋆ − θ bt ⊗ ϕ(a, xt )w −1 λkθ⋆ kG−1 + kSdiff,t−1 kG−1 + kSeta,t−1 kG−1 . wb t−1
Gt−1
Since Gt−1 λIdH ,
λkθ⋆ kG−1 ⩽ t−1
t−1
kuk2 kukG−1 ⩽ √ . t−1 λ
∀u ∈ RdH , Therefore, using Assumption 2.1,
t−1
√
λ kθ⋆ k2 , ⩽
(13)
√ λH Cθ ⋆
and, again by Assumption 2.1, by Equation (6), and by a triangular inequality, k · k2 ⩽1 w t−1 | · |⩽1 z }| {w t−1 w z }| { w 1 Xw 1 w wX X w T ⋆ b b wbτ − b ϕ(aτ , xτ ) θh bτ (h) − bτ (h) bτ ⊗ ϕ(aτ , xτ )w ⩽ √ bτ w1 . kSdiff,t−1 kG−1 ⩽ √ w t−1 w w λ τ =1 h∈[H] λ τ =1 2
As for the final term kSeta,t−1 kG−1 , it is exactly of the form discussed in Abbasi-Yadkori et al. (2011, Theorem 1 and t−1 Lemma 10, recalled below as Lemma A.3), with d′ = dH ,
G = λIdH ,
Xτ = b bτ ⊗ ϕ(aτ , xτ ) , 14
ητ (aτ ) ,
′
Fτ = Fτall +1 ;
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics ′
′
indeed, aτ and Xτ are Fτall –measurable while the ηt (a), and thus also ηt (at ), are Fτall +1 –measurable and vη –sub-Gaussian ′ conditionally to Fτall , as stated in Equation (10). In addition, Equation (6) guarantees that kXτ k2 ⩽ 1. We get that probability at least 1 − δ, for all t ⩾ 1, w w t−1 q wX w w w ητ (aτ ) b bτ ⊗ ϕ(aτ , xτ )w ⩽ vη 2 ln(1/δ) + dH ln 1 + t/(λdH) . w w w −1 τ =1
Gt−1
The proof is concluded by collecting all the bounds above.
For the convenience of the reader, we restate the key classic deviation inequality used above. We recall that sub-Gaussian random variables are necessarily centered. Lemma 10 by Abbasi-Yadkori et al. (2011) is exactly Lemma A.5 stated at the end of this appendix. Lemma A.3 (Abbasi-Yadkori et al., 2011, Theorem 1 and Lemma 10). Consider a filtration (Ft )t⩾0 and two stochastic processes, a scalar-valued process (ηt )t⩾1 such that ηt is Ft –measurable and vη –sub-Gaussian conditionally to Ft−1 , and a d′ –vector-valued process (Xt )t⩾1 such that Xt is Ft−1 –measurable and kXt k2 ⩽ 1 a.s. For λ > 0, let St =
t X
ητ Xτ
Gt = λI +
and
d′
t X
Xτ XTτ .
τ =1
τ =1
Then, with probability at least 1 − δ, for all t ⩾ 1, kSt kG−1 ⩽ vη t
q 2 ln(1/δ) + d′ ln 1 + t/(λd′ ) .
We consider the Box B strategy with a belief estimation subroutine satisfying Assumption 4.1 (for which we recall that the belief error function Ubelief is known) and the confidence bonuses, for t ⩾ 2 and a ∈ A, εt,a = Ubelief (t, δ/2) w w w w + wb bt ⊗ ϕ(a, xt )w −1
Gt−1
t−1 X
1 √ λ τ =1
q √ Ubelief (τ, δ/2) + λH Cθ ⋆ + vη 2 ln(2/δ) + dH ln 1 + t/(λdH)
(14) !
√ and ε1,a = 1 + d/λ. The confidence bonuses εt,a correspond to the upper bounds of Lemma A.2, denoted by ε′t,a in the proof below, up to the replacements of δ by δ/2 and of the unknown kbτ − b bτ k1 by their high-probability bounds Ubelief (τ, δ/2). Recall the statement of our theorem, which we may now prove below. Theorem A.1. Assume that the horizon T is known to the learner and fix δ ∈ (0, 1). Consider the strategy of Box B with a belief estimation subroutine satisfying Assumption 4.1, with λ = T 1/2 and with the confidence bonuses (14). Then, under the boundedness stated in Assumption 2.1 and under the sub-Gaussian noise assumption (10), with probability at least 1 − δ, up to poly-log factors, e T 3/4 , RT = O where a closed-form expression of the regret bound may be found in the proof, see Equation (21).
Proof. We denote by w w ε′t,a = wbt − b bt w1 w w w w + wb bt ⊗ ϕ(a, xt )w −1
! t−1 q √ w 1 Xw wbτ − b √ bτ w1 + λH Cθ ⋆ + vη 2 ln(2/δ) + dH ln 1 + t/(λdH) Gt−1 λ τ =1 √ the upper bound read in Lemma A.2 for the risk δ/2, and let ε′1,a = 1 + d/λ. With this piece of notation, Lemma A.2 guarantees, in particular, that with probability at least 1 − δ/2, for all t ⩾ 1, X X bt−1,h b bt (h) ϕ(a, xt )T θ (15) bt (h) ϕ(a, xt )T θ ⋆h ⩽ max ε′t,a + max a∈A a∈A h∈[H] h∈[H] X X bt−1,h ⩽ ε′ + b bt (h) ϕ(at , xt )T θ ⋆h . (16) bt (h) ϕ(at , xt )T θ and t,at h∈[H]
h∈[H]
15
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
On the other hand, Assumption 4.1 ensures that with probability at least 1 − δ/2, w w wbt − b bt w1 ⩽ Ubelief (t, δ/2) ,
∀t ∈ [T0 , T ],
n o def T0 = max 2, ⌈TB,M ,ν 1 + ln(2/δ) ⌉ ;
where
therefore, with probability at least 1 − δ/2,
(17)
t−1 t−1 w X X w w 2(T0 − 1) w wb w wbτ −b bτ w1 ⩽ 2(T0 −1)+ Ubelief (t, δ/2) and ε′t,a ⩽ εt,a + √ wbt ⊗ϕ(a, xt )w −1 . Gt−1 λ τ =1 τ =1 (18) Equations (6) and (13) ensure that
∀t ∈ [T0 , T ],
∀t ∈ [T0 , T ],
w w wb w w w bt ⊗ ϕ(a, xt )w w 1 wb w 2 √ ⩽ √ wbt ⊗ ϕ(a, xt )w −1 ⩽ Gt−1 λ λ
ε′t,a ⩽ εt,a + 2(T0 − 1)/λ .
thus, finally,
(19) By a union bound, substituting these bounds in Equations (15) and (16) and using the definition of at as the argument of some maximum, we get that with probability at least 1 − δ, for all t ∈ [T0 , T ], X
max a∈A
bt (h) ϕ(a, xt )T θ⋆h ⩽
h∈[H]
=
2(T0 − 1) + max εt,a + a∈A λ
X
h∈[H]
b bt−1,h bt (h) ϕ(a, xt )T θ
X 2(T0 − 1) bt−1,h b bt (h) ϕ(at , xt )T θ + εt,at + λ
h∈[H]
X
and
h∈[H]
max
thus
a∈A
X b bt−1,h ⩽ 2(T0 − 1) + εt,a + bt (h) ϕ(at , xt )T θ⋆h , bt (h) ϕ(at , xt )T θ t λ h∈[H]
X
h∈[H]
bt (h) ϕ(a, xt )T θ⋆h −
X
bt (h) ϕ(at , xt )T θ⋆h ⩽
h∈[H]
4(T0 − 1) + 2εt,at . λ
For t ⩽ T0 −1, the difference above, called the instantaneous pseudo-regret, is always bounded by 2 due to the boundedness stated in Assumption 2.1. Therefore, the regret (2) is bounded, with probability at least 1 − δ, by RT =
T X t=1
max a∈A
X
h∈[H]
⩽ 2(T0 − 1) +
bt (h) ϕ(a, xt )T θ⋆h −
X
h∈[H]
bt (h) ϕ(at , xt )T θ⋆h ⩽ 2(T0 − 1) +
T T w w X X 4T (T0 − 1) wb w +2 Ubelief (t, δ/2) + 2 wbt ⊗ ϕ(a, xt )w −1 λ Gt−1 t=1 t=1 t−1
×
√ 1 X √ Ubelief (τ, δ/2) + λH Cθ ⋆ + vη λ τ =1
T X
t=T0
2εt,at + 4(T0 − 1)/λ (20)
! q 2 ln(2/δ) + dH ln 1 + t/(λdH) ,
where we obtained the second inequality by substituting the expression of εt,at and by replacing T0 by 1 in the summation indices. We further bound the expression above by upper bounding each t by T in the sum of three terms in parentheses and by using r T w w X wb w ⩽ 2 dHT ln 1 + T /(dHλ) , wbt ⊗ ϕ(a, xt )w t=1
G−1 t−1
which follows from Lemma A.4 applied to the vectors y τ = b bτ ⊗ ϕ(aτ , xτ ), of dimension dH and with Euclidean norm 16
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
smaller than 1 as indicated in Equation (6). We get the following final bound: with probability at least 1 − δ, r T X 4T (T0 − 1) +2 Ubelief (t, δ/2) + 2 2 dHT ln 1 + T /(dHλ) RT ⩽ 2(T0 − 1) + λ t=1 T
×
√ 1 X √ Ubelief (τ, δ/2) + λH Cθ ⋆ + vη λ τ =1
(21)
! q 2 ln(2/δ) + dH ln 1 + T /(λdH) .
√ This upper bound is of order T up to logarithmic factors when no belief estimation is required (i.e., when Ubelief is null and T0 = 1, and for λ given by a constant). Keeping in mind that T0 is of order ln T as far as its dependency on T is concerned, the second part of Assumption 4.1 ensures that the upper bound of Equation (21) is of order, up to poly-logarithmic factors, √ p √ √ e T 3/4 , e T /λ + T + T T /λ + λ = O O
where we exploited the choice λ = T 1/2 , which is the optimal choice of the form T a as far as orders of magnitude in T up to poly-logarithmic factors are concerned.
For the sake of self-completeness, we state the so-called elliptic potential lemma, which is extracted from Abbasi-Yadkori et al. (2011, Section C); we actually even re-prove it here because we extend it later to staged updates in Appendix E.2 and base our extension on the classic proof below. Lemma A.4. Consider vectors y t ∈ Rd with ky t k2 ⩽ 1, a parameter λ ⩾ 1, and the Gram matrices V0 = λId and Vt = λId +
t X
y τ yTτ
for t ⩾ 1 .
τ =1
For all integers T ⩾ 1, we have:
T q X w −1/2 w wV w 2dT ln 1 + T /(dλ) . t−1 y t 2 ⩽ t=1
Proof. The classic proof is extracted from Abbasi-Yadkori et al. (2011, Section C). By the Cauchy-Schwarz inequality, v v u T u T T u Xw −1/2 w2 u X X w −1/2 w −1 t tT wV w wV w T yTt Vt−1 yt . (22) t−1 y t 2 ⩽ t−1 y t 2 = t=1
t=1
t=1
Now, for t ⩾ 1, given that Vt−1 λId , where λ ⩾ 1, and given that ky t k2 ⩽ 1 by assumption, we have −1 0 ⩽ yTt Vt−1 yt ⩽
1 ky k2 ⩽ 1 . λ t 2
We resort to the inequality u ⩽ 2 ln(1 + u) for u ∈ [0, 1], and then to Lemma A.5, to get T X t=1
−1 yTt Vt−1 yt ⩽ 2
T X det(VT ) det(Vt ) −1 = 2 ln , ln ln 1 + yTt Vt−1 yt = 2 det(Vt−1 ) det(V0 ) t=1 t=1
T X
(23)
where det(V0 ) = λd and an upper bound on det(VT ) is given by Lemma A.6. Collecting all inequalities concludes the proof. Lemma A.5 (Matrix determinant lemma, see, e.g., Ding & Zhou, 2007, Lemma 1.1). For a d × d invertible matrix A and vectors y, y ′ ∈ Rd , det A + y ′ yT = 1 + yT A−1 y ′ det(A) .
Lemma A.6 (Determinant–trace inequality, see, e.g., Abbasi-Yadkori et al., 2011, Lemma 10). With the notation and assumptions of Lemma A.4, det(Vt ) ⩽ (λ + t/d)d . 17
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
B. Challenges Overcome: Details on a Final Ingredient We detail the final ingredient in our solution, alluded at in Section 3.3 and borrowed from the analysis by Nelson et al. (2022), where it could however have been replaced by simpler arguments up to slightly strengthening the noise assumptions from Assumption 2.3 to a well-accepted sub-Gaussian (Assumption 2.2). We do so on stylized quantities. Stylized quantities considered. The proofs—see, in particular, Appendix E.1.1 for the most complex reward model (1) and Lemma A.2 for the simplified version (4) by Nelson et al. (2022)—indicate that they key quantities to be controlled are of the stylized form T X X rt (at ) − ϕ(a, xt )T bt (h) θ ⋆h . ∆T = t=1
h∈[H]
The exact quantities appearing in the proofs of the regret bounds are slightly more complicated (in particular, they are vector-valued) but we capture here the essence of the arguments. Simplified reward model.
By definition of the reward model (4), ∆T =
T X
ηt′ (at ) ,
t=1
′
′
obs obs where the ηt′ (at ) are martingale increments, e.g., with respect to Ft+1 . Indeed, on the one hand, ηt′ (at ) is Ft+1 –measurable ′ ′ obs as the difference between rt (at ), which is one of the variables generating Ft+1 , and some quantity measurable with respect ′ to σ(x1:t ) and at , where at itself is Ft obs –measurable. On the other hand, the assumption that the noise term′ is independent ′ from the present and the past entails that E ηt′ (a) | Ft obs = 0 for all a ∈ A, so that, using again that at is Ft obs –measurable, we also have ′ E ηt′ (at ) | Ft obs = 0 .
Because the ηt′ (at ) form bounded martingale increments, with probability at least 1 − δ, the martingale ∆T is smaller than p something of the order of T ln(1/δ), e.g., by the Hoeffding-Azuma inequality.
Most complex reward model: issue. The main issue is that we do not deal with martingale increments, due, in particular, to the direct dependencies of rewards on hidden states. More precisely, we have, by the definition (1), that T T X X X bt (h) θ⋆h + ηt (at ) . ∆T = ϕ(at , xt )T θ⋆ht − t=1
t=1
h∈[H]
all An argument similar to above shows that the ηt (at ) are martingale increments with respect to Ft+1 , thus their sum is controlled.
The remaining question is thus to control T X t=1
dt ,
where
dt = ϕ(at , xt )T θ ⋆ht −
X
h∈[H]
bt (h) θ ⋆h .
However, the dt do not form martingale increments, nor are sufficiently close to martingale increments. The issue mostly lies in guaranteeing that dt is Ft+1 –measurable; it is straightforward to find filtrations such that E dt | Ft is close to 0, e.g., Ft = Ut : X ⋆ T bt (h) − bt (h) θh , E dt | Ut = ϕ(at , xt ) h∈[H]
which is small as all terms bt (h) − bt (h) are small, see Section 3.2. 18
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Any natural filtration Ft we would consider (and Ut in particular) includes contexts x1:t and is such that at is Ft – measurable. For such filtration, the requirement of Ft+1 –measurability of dt entails that θ ⋆ht should be Ft+1 –measurable. Say, for simplicity, that ht is Ft+1 –measurable. With the same arguments as above, the constraint E dt | Ft close to 0 would then impose that bt (h) = P(ht = h | x1:t ) and P(ht = h | Ft )
should be close, but P(ht = h | Ft ) corresponds to a quantity of the form P(ht = h | ht−1 , xt ) and is likely to differ much from bt (h), as the former is mostly a function of ht−1 , while the latter depends weakly on the underlying states due to the HMM forgetting properties. Most complex reward model: solution. It turns out that we do not need that the dt are sufficiently close to martingale increments to control their sum: via Markov’s inequality, it suffices that their sum is small in L2 –norm, e.g., of the order of T a for a < 1. Then, with high probability, the sum itself is small: with probability at least 1 − δ v h i u r u E d2 + . . . + d2 T X t 1 T O(T a ) ⩽ . dt ⩽ δ δ t=1 Nelson et al. (2022) illustrate this for the sum of noise terms ηt′ (a) in their simplified model, when relaxing the subGaussian noise Assumption 2.2 to Assumption 2.3 on bounded conditional second-order moments. This relaxation seems unimportant and we provide a simple and straightforward-to-prove regret bound under Assumption 2.2 (see Appendix A). Yet, the analysis that Nelson et al. (2022) developed, while not fully useful for them, is powerful and may be mimicked (and extended) to handle the sum of dt . Indeed, we write
"
E
T X t=1
d2t
!#
=
T X E d2t +2 t=1
|
{z
}
of order T
X
1⩽t⩽t′ ⩽T
E dt dt′ ,
where we used Assumption 2.1, i.e., the boundedness of dt , to see that the sum of expected square terms is of order T . We get, by the tower rule and by the fact that bt (h) and bt′ (h) are Ut′ –measurable: h X i E dt dt′ = E E dt dt′ | Ut′ = Eϕ(at , xt )T θ⋆ht ϕ(at′ , xt′ )T θ⋆ht′ − bt′ (h) θ⋆h + ψ bt − bt′ , h∈[H]
where ψ bt −bt′ is a term bounded by something of the order of kbt −bt′ k1 and is therefore small, by the HMM forgetting property. The other term in the rewriting above involves differences between and bt , P hτ = h and hτ ′ = h′ | Uτ ′ which, again, are small when t and t′ are sufficiently separated due to the HMM forgetting property.
19
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
C. Belief Estimation The aim of this section is to detail why the following assumption made on the belief estimation subroutine is reasonable. Assumption 4.1 (belief estimation error). The belief estimation procedure B is such that for all hidden Markov chains (π, M , ν) in a wide class, there exist • a constant TB,M ,ν not necessarily known to the learner, • a fully known belief error function Ubelief on {1, 2, . . .} × (0, 1), where Ubelief (t, δ) depends logarithmically on δ and, up to poly-log factors, for each δ ∈ (0, 1), X e T 1/2 , Ubelief (t, δ) = O t∈[T ]
such that for all δ ∈ (0, 1), with probability at least 1 − δ, the following statements hold for all t ⩾ TB,M ,ν 1 + ln(1/δ) : • first, thew labeling of w hidden states is consistent over the rounds considered; bt − bt w1 ⩽ Ubelief (t, δ). • second, wb
More precisely, we show that this assumption holds at least for the large class of HMMs satisfying Assumption 4.2 below. To state the latter, we let E denote the emission matrix, indexed by X × [H] and obtained by concatenating the emission distributions νh seen as X–dimensional column vectors as h ∈ [H]. We will assume, among others, that E has full column rank: this imposes, in particular, that H is smaller than the cardinality of X . Recall the notion of singular value: σ is a singular value of E if σ 2 is an eigenvalue of the square matrix ET E. Assumption 4.2. The context set X is finite, with cardinality denoted by |X | = X. The emission matrix E has full column rank with smallest singular value σmin (E) > 0, and its smallest element satisfies def
eν,min = min min νh (x) > 0 . h∈[H] x∈X
The transition matrix M is invertible, with smallest eigenvalue denoted by σmin (M ) > 0, and the smallest element of M is positive: εM = min′ Mh,h′ > 0. h,h
Finally, the initial distribution π is the (unique) stationary distribution of M . To that end, we consider a combination of a so-called spectral method (see its algorithmic statement in Appendix C.4 and see references after the statement of Lemma 4.3) to estimate the HMM parameters M and E, i.e., the νh for h ∈ [H], together with a Bayes’ update rule to deduce estimated belief from these estimated parameters. We also add an alignment step (see Appendix C.2) to keep track of the hidden states. c t and νbt,h the estimates of M and of the νh obtained The Bayes’ update rule. More precisely, for t ⩾ 1, we denote by M b of the distribution of h1 , for instance, the uniform based on the contexts x1 , . . . , xt ; we also consider some estimation π distribution over [H]. The Bayes’ update rule then works as follows. For τ = 1, we compute, for all h ∈ [H]: b bt,1 (h) =
b (h) νbt,h (x1 ) π X . b (h′′ ) νbt,h′′ (x1 ) π
h′′ ∈[H]
We then compute successively, for all 2 ⩽ τ ⩽ t, for all h ∈ [H], X b ct,h′ ,h bt,τ −1 (h′ ) M νbt,h (xτ ) b bt,τ (h) =
We finally issue
X
h′′ ∈[H]
(24)
h′ ∈[H]
νbt,h′′ (xτ )
X
h′ ∈[H]
b bt = b bt,t .
b ct,h′ ,h′′ bt,τ −1 (h′ ) M
.
(25)
(26)
We call the successive updates above the Bayes’ update rule. When M , π, and the νh are used instead of their estimates in the formulas above, we obtain the true beliefs bt . We detail in the rest of this appendix how to obtain the following result, which shows that Assumption 4.1 is reasonable. 20
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Lemma 4.3. Assumption 4.1 is satisfied for all hidden Markov chains of Assumption 4.2, for the spectral method (followed by an alignment step) combined with the Bayes’ update rule, with the known belief error function s ! √ √ 2 ln 6Xt(t + 1)/δ − t−1 +e Ubelief (t, δ) = ln(t) H X t and the unknown threshold TB,M ,ν whose closed-form expression is provided in Equation (30). References for the spectral method. The HMM parameter estimation via spectral method is a standard procedure commonly used for bandits with latent states or for partially observable Markov decision processes [POMDP] where underlying states follow an HMM. It was proposed by Hsu et al. (2012) and further developed by Anandkumar et al. (2012) and Anandkumar et al. (2014). For instance, Zhou et al. (2021) and Azizzadenesheli et al. (2016) apply this the method proposed by Anandkumar et al. (2012, Section 4.2), in combination with the power iteration method from Anandkumar et al., 2014. We restate the algorithm of Anandkumar et al. (2012, Section 4.2) in Appendix C.4. C.1. Proof of Lemma 4.3: Belief-Estimation Error We explain how the belief-estimation error bound from Lemma 4.3 follows from the application of two known results on HMM parameter estimation (one for the estimation of the parameters themselves, one for the guarantees induced on the estimation of the beliefs), together with two simple additions: an alignment step to ensure coherence of the labeling of hidden states and a twist to get a fully known belief error function. First, as detailed in Appendix C.3, Azizzadenesheli et al. (2016, Theorem 3) and Zhou et al. (2021, Proposition 1, Appendix B) offer some estimator error guarantees, which can be instantiated under Assumption 4.2 as follows (keeping the notation of the second reference), with constants 12 16 4 √ 256 21 21H H+ 2 C3 , where C3 = 3/2 1 + 2 3 + 2 2 . C1 = 2 C3 and C2 = σ σ σ εM σ εM σ εM Based on Anandkumar et al. (2014, Equation 28), we also define C0 = min (56 · 9 · 102)−1 , (100 · 168)−1 , ∆′ ,
where ∆′ > 0 is a numerical constant defined in Anandkumar et al. (2014, Lemma B.5 with ∆ = 1/50), though not in closed-form. Compared to the mentioned references, we rather consider the Frobenius norm instead of the spectral norm, √ which introduces an additional H factor in the estimation bound for M . Proposition C.1 (Instantiation of Zhou et al., 2021, Proposition 1, itself based on Azizzadenesheli et al., 2016, Theorem 3). Under Assumption 4.2, the threshold ( ) 2 1/3 12 16H 3H TeB,M,ν = 2 2 2 ln 2X + 1 max , 1 (27) , 2 2 2/3 1/3 εM σ C0 εM C0 εM σ is such that for all t ⩾ TeB,M ,ν 1 + ln(1/δ) , with probability 1 − δ, the estimates M̃ t and ν̃t from the spectral method can be well computed and satisfy, up to some permutation ρ of [H], r r w (ρ) w 2H ln(6X/δ) 2 ln(6X/δ) wM̃ − M w ⩽ C2 and ∀h ∈ [H], kν̃t,ρ(h) − νh k2 ⩽ C1 , t 2 t t (ρ)
where M̃ t
= M̃t,ρ(h),ρ(h′ ) h,h′ ∈[H] .
The result above is “up to some permutation ρ of [H]”: this underlines that the spectral method does absolutely not guarantee that what was called “state h” in round t will correspond to the same ‘state h” in round t + 1. In terms of beliefs, this means that the belief function obtained from the estimates of Proposition C.1 are good up to the labeling of the hidden states. Since the end result is about the ℓ1 –error between the estimated beliefs and the true beliefs, the ordering of hidden 21
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
labels does not matter as long as that ordering is constant over time. This is what the alignment procedure described in Appendix C.2 will guarantee. For now, we move to controlling the ℓ1 –error between the estimated beliefs and the true beliefs, which corresponds to the second statement of Lemma 4.3 and is independent of the ordering of hidden labels, as it corresponds to some global evaluation. De Castro et al. (2017) developed the following bound linking the estimation errors of the HMM parameters to the estimation error on the beliefs (again, the result holds up to permutations). Proposition C.2 (De Castro et al., 2017, Proposition 2.1, see also Zhou et al., 2021, Proposition 3). Under Assumption 4.2, letting 2 1 − εM (1 − εM )2 1 1 − εM , L2 = 4 , L = 4 , L0 = 4 1 2 εM εM eν,min ε3M the beliefs b̃t obtained from (a suitable permutation of) the estimates π̃, and M̃ t and ν̃t,h through the Bayes’ rule (24)–(26) satisfy t−1 Xw w w w w w w w wν̃t,h − νh w + L2 wM̃ t − M w . wπ̃ − π w + L1 wb̃t − bt w ⩽ L0 1 − εM 2 1 2 1 1 − εM h∈[H]
We now combine Propositions C.1 and C.2 and perform some simple upper boundings, where the second follows from the Cauchy-Schwarz inequality: sX √ w √ w w w w w w 2 qw wν̃t,h − νh w ⩽ X wν̃t,h − νh w . wπ − π̃ w = and π(h) − π̃(h) ⩽ wπ − π̃w1 ⩽ 2 1 2 2 | {z } h∈[H]
∈[−1,1]
We also perform union bounds and use
δ t(t + 1)
instead of
δ
(28)
at each round t ⩾ 1: this is to ensure that the result of Proposition C.1 holds simultaneously for all t ⩾ TeB,M,ν with probability at least 1 − δ.
We get, from Propositions C.1 and C.2 that with probability 1 − δ, up to identifying a correct permutation, ∀t ⩾ TeB,M,ν 1 + ln t(t + 1)/δ , √ w w wb̃t − bt w ⩽ 2L0 1 − 1
εM 1 − εM
t−1
s √ 2 ln 6Xt(t + 1)/δ √ . (29) + L1 C1 H X + L2 C2 H t
The right-hand side cannot be our Ubelief function, as it depends on unknown quantities εM , C1 , C2 , L0 , L1 , L2 (the latter depend on the unknown HMM parameters). We do not follow the mitigations alluded at in Zhou et al. (2021, Section 3.3) or Azizzadenesheli et al. (2016, Remark 3), consisting of estimating these quantities (this looks as difficult as estimating the HMM parameters) or replacing them by some hyperparameters tuned by hand; we rather bound them as functions of t and increase the threshold TeB,M ,ν to compensate for that.
We note that t−1 √ εM 1− ⩽ e− t−1 1 − εM
as soon as i.e.,
√ ε′M (t − 1) ⩽ − t − 1 , t ⩾ 1 + 1/ ε′M
Thus, we let
2
,
where
√ TB,M,ν = max 6 TeB,M,ν 1 + ln TeB,M,ν , exp(L1 C1 + L2 C2 ) , exp 2L0 ,
ε′M = ln 1 −
εM 1 − εM
2 ′ 1 + 1/ εM , 6 T∆ 1 + ln(T∆ ) ,
22
.
(30)
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
where we recall that TeB,M ,ν is defined in Equation (27) and where T∆ is defined in Equation (34) below. Then, for t ⩾ TB,M,ν 1 + ln(1/δ) , we have L1 C1 + L2 C2 ⩽ ln TB,M ,ν
⩽ ln t/ 1 + ln(1/δ) ⩽ ln(t),
√ 2L0 ⩽ ln(t) ,
1−
εM 1 − εM
t−1
√
⩽ e− t−1 ,
so that the right-hand side of Equation (29) is indeed smaller than the quantity Ubelief (t, δ) defined in Lemma 4.3 for these t ⩾ TB,M,ν 1 + ln(1/δ) . We also need to make sure that these t satisfy the condition of Equation (29): this is the case as (see proof right below) t ⩾ TB,M ,ν 1 + ln(1/δ) entails t ⩾ TeB,M ,ν 1 + ln t(t + 1)/δ . (31) This concludes the proof of the belief-estimation error part of the lemma up to identifying the suitable permutations, a topic which we discuss below in Appendix C.2, and up to proving (31), which do next. Proof of Equation (31). From the assumption t ⩾ TB,M ,ν 1 + ln(1/δ) and from the definition of TB,M ,ν , which guarantees that TB,M ,ν ⩾ 6 TeB,M,ν 1 + ln(TeB,M ,ν ) , we get t
TeB,M ,ν
1 + ln(1/δ) ⩾ 6 1 + ln(1/δ) . ⩾ 6 1 + ln TeB,M,ν
(32)
From the intermediate inequality above, we also show later that
t ⩾ 3 ln(t) ⩾ 2 ln(t + 1) , e TB,M,ν
(33)
where the second inequality holds because ln(t + 1) ⩽ 1.5 ln(t) for t ⩾ 6, a condition that is satisfied in particular here. The conclusion then follows from combining the three bounds established above: t 1 1 1 t t(t + 1) = . = 1 + ln(1/δ) + ln(t) + ln(t + 1) ⩽ 1 + ln + + δ 6 3 2 TeB,M,ν TeB,M,ν It only remain to prove the intermediate inequality of Equation (33).
For the first inequality below, we use that u 7→ u/3 − ln(u) is increasing for u ⩾ 3 and apply this property to the left inequality of Equation (32), and for the second inequality below, we use that 6 < exp(2) and 1 + ln(x) ⩽ x for x > 0: 6 1 + ln Te B,M,ν t t e ⩾ ln TeB,M ,ν , ⩾ − ln − ln 6 1 + ln TB,M,ν e e 3 TB,M ,ν 3TB,M,ν {z } | ⩽e2 TeB,M ,ν
which rewrites as
ln(t) = ln TeB,M ,ν + ln
which is exactly the intermediate inequality of Equation (33).
t TeB,M ,ν
⩽
t , e 3TB,M,ν
C.2. Proof of Lemma 4.3: Coherence Statement In this section, we introduce an alignment step to ensure that, after a sufficiently large number of rounds, the latent-state labels of the estimated HMM parameters are consistent over time and thus can be mapped with some constant ordering of states. This also implies that the corresponding estimated belief vectors are expressed in one common latent state coordinate system, so that the words “a suitable permutation of” are not required anymore in Proposition C.2. What follows was already alluded at, but not described in detail, by Azizzadenesheli et al. (2016, Proof of Lemma 8, Step 3). 23
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Algorithmic statement. More formally, let S denote the set of all permutations ρ of [H]. At step t + 1, when obtaining c t+1 and νbt+1,h by the estimates M̃ t+1 and ν̃t+1,h considered in Proposition C.1, we transform them into the estimates M picking a permutation ρt+1 and considering ∀h ∈ [H],
νbt+1,h = ν̃t+1,ρ(h)
and
c t+1 = M̃t+1,ρ(h),ρ(h′ ) , M h,h′ ∈[H]
w w where the permutation is picked as ρt+1 ∈ argmin max wνbt,h − ν̃t+1,π(h) w2 . π∈S
h∈[H]
At step t = 1, we leave estimators unchanged, i.e., pick ρ1 given by the identity. Analysis.
We consider the same union bound as the one performed in Equation (28), so that, in particular, P ∀t ⩾ TeB,M,ν 1 + ln t(t + 1)/δ , ∀h ∈ [H],
∃ρ′t ∈ S
s.t. s
kν̃t,ρ′t (h) − νh k2 ⩽ C1
2 ln 6Xt(t + 1)/δ t
!
⩾ 1−δ.
Denote by ∆ = min′ kνh − νh′ k2 ; h6=h
this quantity is positive as, by Assumption 4.2, E is full rank and thus, the emission distributions νh are, in particular, all different. Now, consider a time T∆ such that s 2 ln 6Xt(t + 1)/δ ∆ < ; ∀t ⩾ T∆ 1 + ln t(t + 1)/δ , C1 t 4 for instance,
32 C12 ln(6X) T∆ = 1 + ∆2 is a suitable value, as for t ⩾ T∆ 1 + ln t(t + 1)/δ , and using that ln(6X) ⩾ 1,
C1
s
(34)
v u s u ln(6X) 1 + ln t(t + 1)/δ 2 ln 6Xt(t + 1)/δ ∆ 2 ln(6X) u < ⩽ C1 t2 . = C1 t T 4 ∆ T∆ 1 + ln t(t + 1)/δ
We consider the same threshold TB,M,ν as in Equation (30); in particular, given the definition of TB,M,ν , the proof of Equation (31) with T∆ instead of TeB,M,ν guarantees that entails t ⩾ T∆ 1 + ln t(t + 1)/δ . t ⩾ TB,M ,ν 1 + ln(1/δ) Together with Equation (31), we thus have proved so far that P ∀t ⩾ TB,M,ν 1 + ln(1/δ) , ∃ρ′t ∈ S s.t. ∀h ∈ [H],
The claimed coherence can now be formally stated as follows.
kν̃t,ρ′t (h) − νh k2 < ∆/4 ⩾ 1 − δ .
(35)
Lemma C.3. Under the same 1 − δ probability event considered in the end of Appendix C.1, which includes the event of Equation (35), we have that for all t ⩾ TB,M,ν 1 + ln(1/δ) , the permutation ρ′t of Equation (35) is unique, and so is the permutation ρt+1 defined in the algorithmic statement above. In addition, there exists a permutation ρ̄ such that w w w w wνbt,h − νh′ w > 3∆/4 ; while ∀h ∈ [H], ∀h′ 6= ρ̄(h), ∆/4 > max wνbt,h − νρ̄(h) w2 → 0 2 h∈[H]
thus, the algorithm keeps track of the latent states and uses a consistent hidden-state labeling after TB,M ,ν 1 + ln(1/δ) . 24
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Proof. Denote t0 = TB,M ,ν 1 + ln(1/δ) and fix t ⩾ t0 . Consider a suitable permutation ρ′t . We note that under the event of interest, by a triangle inequality, ∀m′ 6= ρ′t (h),
kν̃t,m′ − νh k2 ⩾ kνm − νh k2 − kν̃t,m′ − νm k2 > 3∆/4 ,
where we introduced m such that ρ′t (m) = m′ , so that kν̃t,m′ −νm k2 < ∆/4; in particular, m 6= h, so that kνm −νh k2 ⩾ ∆. This shows that ρ′t is unique. Now define ρ̄ = (ρ′t0 )−1 ◦ ρt0 . We prove by induction on t ⩾ t0 that w w max wνbt,h − νρ̄(h) w2 < ∆/4 , h∈[H]
together with the uniqueness of ρt+1 . For t = t0 , by definition, νbt0 ,h = ν̃t0 ,ρt0 (h) , so that w w w w max wνbt0 ,h − νρ̄(h) w2 = max wν̃t0 ,ρt0 (h) − ν(ρ′t )−1 (ρt0 (h)) w2 0 h∈[H] h∈[H] w w w w wν̃t ,ρ′ (h′ ) − νh′ w < ∆/4 , w ν̃t0 ,h′ − ν(ρ′t )−1 (h′ ) w2 = max = max 0 t 2 ′ ′ 0
h ∈[H]
0
h ∈[H]
where we performed various re-indexations of [H] based on permutations and where we used the definition of ρ′t0 to get the final inequality. Assume that the induction property holds at some t ⩾ t0 , and define πt+1 = ρ′t+1 ◦ ρ̄. Then, by the triangle inequality, w w w w w w max wνbt,h − ν̃t+1,π (h) w ⩽ max wνbt,h − νρ̄(h) w + max wν̃t+1,ρ′ (ρ̄(h)) − νρ̄(h) w h∈[H]
t+1
2
2
h∈[H]
h∈[H]
t+1
2
w w w w ⩽ max wνbt,h − νρ̄(h) w2 + max wν̃t+1,ρ′t+1 (h) − νh w2 < ∆/2 , h∈[H]
h∈[H]
where we used that the first maximum is smaller than ∆/4 by the induction hypothesis, and that the second maximum is also smaller than ∆/4 by the definition of ρ′t+1 . On the other hand, if π 6= πt+1 , then there exists h ∈ [H] such that π(h) 6= ρ′t+1 ρ̄(h) , thus (ρ′t+1 )−1 π(h) 6= ρ̄(h); using a triangle inequality, we have w w w w w w wν̃t+1,π(h) − νρ̄(h) w ⩾ wν(ρ′ )−1 (π(h)) − νρ̄(h) w − wν̃t+1,π(h) − ν(ρ′ )−1 (π(h)) w 2 2 2 t+1 t+1 w w w w w w w w ′ ′ ′ = ν(ρt+1 )−1 (π(h)) − νρ̄(h) 2 − ν̃t+1,ρt+1 (h′ ) − νh 2 > 3∆/4 , | {z } | {z } >∆
<∆/4
where the < ∆/4 part comes from the definition and uniqueness of ρ′t+1 used with h′ = (ρ′t+1 )−1 (π(h)), and the > ∆ part from the very definition of ∆. Therefore, by another triangle inequality and another use of the induction hypothesis, w w w w w w wνbt,h − ν̃t+1,π(h) w ⩾ wν̃t+1,π(h) − νρ̄(h) w − wνbt,h − νρ̄(h) w > 3∆/4 − ∆/4 = ∆/2 . 2 2 2 This shows the uniqueness of ρt+1 and its closed-form expression ρt+1 = πt+1 = ρ′t+1 ◦ ρ̄. Finally, substituting this expression and using the definition of ρ′t+1 , w w w w w w wνbt+1,h − νρ̄(h) w = wν̃t+1,ρ (h) − νρ̄(h) w = wν̃t+1,ρ′ (ρ̄(h)) − νρ̄(h) w < ∆/4 , ∀h ∈ [H], t+1 2 2 2 t+1
which closes the induction and completes the proof.
C.3. Details on How Proposition C.1 Follows from Existing Results Proposition C.1 follows from various results scattered throughout Hsu et al. (2012), which introduced the spectral method, Anandkumar et al. (2012) and Anandkumar et al. (2014). Azizzadenesheli et al. (2016) and Zhou et al. (2021) extended the method to more complex settings involving Markov decision processes (of which HMMs are special cases) and they offered a synthetical view of the constants involved in the estimation bound (though some of these constants are larger or depend on more complex quantities due to the consideration of Markov decision processes, which involve actions for the learner). More precisely, we follow below the exposition by Azizzadenesheli et al. (2016, Lemma 5, Lemma 8, Theorem 3, Theorem 16) and most importantly, Zhou et al. (2021, Proposition 1), with the needed modifications: the constants C1 , C2 , C3 and the threshold TeB,M,ν of Appendix C.1 are as in Zhou et al. (2021, Appendix B) except for removing an unnecessary term |A| from C1 (it only arises due to their more complex setting) and up to substituting upper or lower bounds on some quantities, as detailed below. 25
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
First series of quantities. Assumption 4.2 entails that the hidden states form an ergodic Markov chain, which thus admits a unique stationary distribution π, is geometrically mixing in the following sense and with the following parameters (see Kontorovich & Weiss, 2014, Krishnamurthy, 2016, Theorems 2.7.2 and 2.7.4, Zhou et al., 2021, Appendix B): X P(ht = h | h1 = h′ ) − π(h) ⩽ 4(1 − εM )t−1 . ∀t ⩾ 2, max ′ h ∈[H]
h∈[H]
Further, due to the boundedness of M and the fact that h1 follows π, for all h ∈ [H] and all t ⩾ 1, X π(h′ ) M h′ ,h ⩾ εM . P(ht = h) = π(h) = | {z } ′ h ∈[H]
Second series of quantities.
⩾εM
We define the following multi-view matrices A1 , A2 , A3 ∈ [0, 1]X×H for t ⩾ 2,
∀x ∈ X , ∀h ∈ [H],
A1 (x, h) = P(xt−1 = x | ht = h) ,
A2 (x, h) = P(xt = x | ht = h) , A3 (x, h) = P(xt+1 = x | ht = h) ,
and we are interested in min σmin (A1 ), σmin (A2 ), σmin (A3 ) , where σmin (Ai ) is the smallest singular value of the matrix Ai , for i ∈ {1, 2, 3}. We have A2 = E and A3 = EMT . The closed-form expression for A1 is slightly more complex as we have to go backwards in the HMM: no dep. on h and =E x,h′
}| { X z A1 (x, h) = P(xt−1 = x | ht = h) = P(xt−1 = x | ht−1 = h′ , ht = h) P(ht−1 = h′ | ht = h) , h′ ∈[H]
where
P(ht−1 = h′ | ht = h) =
π(h′ ) M h′ ,h P(ht = h | ht−1 = h′ ) P(ht−1 = h′ ) = P(ht = h) π(h)
(we recall that the Marhov chain of hidden states is initialized with the stationary distribution π), so that A1 = E diag(π)M diag(π)−1 , where diag transforms a vector into a square diagonal matrix with diagonal coefficients given by the vector. We now use that for two matrices E, E ′ of compatible sizes, we have σmin (E E ′ ) ⩾ σmin (E) σmin (E ′ ). Also, given that all components of π are in the interval [εM , 1], and σmin diag(pt )−1 ⩾ 1 . σmin diag(π) ⩾ εM
We obtain σmin (A2 ) = σmin (E), as well as
σmin (A1 ) ⩾ σmin (E) σmin (M ) εM
and
σmin (A3 ) ⩾ σmin (E) σmin (M ) .
Given that M is a stochastic matrix, we have εM < 1 and σmin (M ) ⩽ 1, and thus def min σmin (A1 ), σmin (A2 ), σmin (A3 ) ⩾ σ = σmin (E) σmin (M ) εM .
Finally, we also introduce the co-occurrence matrix A4 ∈ [0, 1]X×X : ∀(i, j) ∈ X × X , A4 (i, j) = E 1{xt+1 =i} 1{xt−1 =j} = P(xt+1 = i, xt−1 = j)
Third series of quantities.
and are interested in σmin (A4 ). In a HMM, xt+1 and xt−1 are conditionally independent given ht , as both are drawn independently conditional on ht+1 and ht−1 ; therefore, for any i, j ∈ X , X P(ht = h) P(xt+1 = i | ht = h) P(xt−1 = j | ht = h) , P(xt+1 = i, xt−1 = j) = h∈[H]
and thus, A4 = A3 diag(π)AT1 . Similarly as above, this rewriting entails 2 σmin (A4 ) ⩾ σmin (A3 ) σmin diag(π) σmin AT1 ⩾ σmin (E) σmin (M ) εM = σ 2 . 26
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
C.4. Reminder on the Spectral Method for MHH Parameter Estimation Finally, for the sake of self-completedness, we recall the spectral method for HMM parameter estimation, which is the method considered in Proposition C.1. The exposition follows closely Anandkumar et al. (2012, Section 4.2). Remember that we assume that the context X space is finite, with cardinality X. With no loss of generality, we may therefore identify it with the canonical vectors in RX , i.e., up to numbering the elements in X and substituting the i–th element, where i ∈ [X], by the column vector ei = (0, . . . , 0, 1, 0 . . . , 0)T ∈ RX , where the unique element 1 is in i–th position. We extend the tensor product notation to products of three elements: for all vectors u, v, w ∈ RX , the two-dimensional matrix u ⊗ v and the three-dimensional matrix u ⊗ v ⊗ w are defined component wise by ∀(i, j, k) ∈ [X]3 ,
(u ⊗ v)i,j = ui v j
and (u ⊗ v ⊗ w)i,j,k = ui v j w k .
We may now restate the special case of the estimation of HMM parameters as1 detailed in Anandkumar et al. (2012, Section 4.2). Remark on the practical implementation. In our numerical experiments, we will post-process M̃t and Ẽt by clipping small negative entries and performing the needed normalizations so that they define valid emission and transition matrices.
1
The indexing conventions are slightly different here and in their article, so that extra transpositions appear here.
27
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
B OX C: S PECTRAL ESTIMATION OF HMM PARAMETERS FROM OBSERVATIONS x1:t Inputs: known number H of hidden states; observations x1 , x2 , . . . , xt , where t ⩾ 3, in the form of canonical vectors Parameter: invertible matrix Γ ∈ RH×H , e.g., a random rotation matrix; denote by Γh, · ∈ RH its h–th row transposed into a column-vector Output: estimates Ẽ t and M̃ t of the emission and transition matrices E and M 1. Compute the empirical moments (t) P̃3,1 =
t−1 1 X xs+1 ⊗ xs−1 , t − 2 s=2
(t) P̃3,2 =
t−1 1 X xs+1 ⊗ xs , t − 2 s=2
(t) P̃3,1,2 =
t−1 1 X xs+1 ⊗ xs−1 ⊗ xs . t − 2 s=2
2. Compute Ũ3 , Ũ1 ∈ RX×H , the matrices whose columns are, respectively, the left and right singular vectors (t) of P̃3,1 associated with its largest H singular values. (t)
Compute Ũ2 ∈ RX×H , the matrix whose columns are the right singular vectors of P̃3,2 associated with its largest H singular values. (t)
3. Define the contraction of the third-order tensor P̃3,1,2 (z) along its third mode for each vector z ∈ RX by and let
X X (t) (t) P̃3,1,2 (z) i,j := P̃3,1,2 i,j,k z k , k=1
−1 (t) (t) (t) ; B̃3,1,2 (z) = Ũ3T P̃3,1,2 (z)Ũ1 Ũ3T P̃3,1 Ũ1
then, compute a matrix R̃ ∈ RH×H , with columns of unit Euclidean norm, such that (t) R̃−1 B̃3,1,2 (Ũ2 Γ1, · ) R̃ = diag λ̃1,1 , λ̃1,2 , . . . , λ̃1,H ;
if this is not possible, redraw Γ and repeat this step.
4. For each h ∈ [H], using the matrix R̃ computed in Step 3, define λ̃h,1 , λ̃h,2 , . . . , λ̃h,H as the diagonal entries of (t) R̃−1 B̃3,1,2 (Ũ2 Γh, · ) R̃ and form the matrix L̃ ∈ RH×H with entries L̃h,j := λ̃h,j for all h, j ∈ [H]. 5. Define Õt = Ũ2 Γ−1 L̃ and output Ẽ t = ÕTt
M̃ t =
and
28
Ũ3T Õt
−1 T R̃ .
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
D. HMM Forgetting Properties and Related Reminders This appendix justifies the exponentially fast forgetting of the initial distribution of the HMM stated in Assumption 5.1. Assumption 5.1 (exponentially fast forgetting of initial condition). There exists a constant γ ∈ [0, 1) so that, for all s ⩽ t, for all pairs h, h′ ∈ [H] of hidden states, X P{hs =h} (ht = j | xs+1:t ) − P{hs =h′ } (ht = j | xs+1:t ) ⩽ 2γ t−s . j∈[H]
This assumption involves quantities of the form PE (E ′ | G), where E and E ′ are events and G is a σ–algebra, all defined on the same underlying probability space (Ω, F ): we provide some reminders on such quantities—including their definitions— in Appendix D.1 below. See also Appendix D.2 for reminders on why we only condition by xs+1:t in the probability distributions above. For now, we compare the assumption above to the alternative forgetting property used by Nelson et al. (2022, see Corollary C.4.1 therein), which is of the form: there exists γ ∈ [0, 1) and a constant C, both depending on the HMM, such that X (36) E P{hs =h} (ht = j | xs+1:t ) − P(ht = j | xs+1:t ) ⩽ C exp −γ(t − s) . j∈[H]
′
This constant γ is given by e−γ /2 , where γ ′ is the minimal mixing rate of the transition matrix M : X min{Mh,h′ , Mh,h′′ } . γ ′ = ′ min ′′ h ,h ∈[H]
h∈[H]
Nelson et al. (2022) apply some inequalities for Markov processes established by Boyen & Koller., 1998, see, in particular, Theorem 3 to show the property stated in Equation (36). The forgetting property used by Nelson et al. (2022) is (by far) less demanding as the condition is to be satisfied in expectation compared to the one of Assumption 5.1. However, this is perfectly consistent with the fact that Nelson et al. (2022) only provide bounds in expectation while the present article instead aims for high-probability bounds (see the discussion in Section 1). D.1. Bayes’ Formula for Probabilities Conditional to σ–Algebras We assume that P (E) > 0 and let PE = P( · | E) denote the conditional probability with respect to event E. This is a probability distribution over (Ω, F ) and its conditional probability PE ( · | G) with respect to the σ–algebra G ⊆ F is thus well defined. We recall in the lemma below how to apply rigourously Bayes’ theorem in this context. Lemma D.1. With the notation above and under the condition P (E) > 0, we have P(E ∩ E ′ | G) = P(E | G) × PE (E ′ | G) . Proof. A characterization of the conditional expectation E[Z | G] of a nonnegative random variable Z ⩾ 0 is that it is a G–measurable random variable satisfying ∀A ∈ G, E[Z 1A ] = E E[Z | G] 1A ] . (37)
We thus should prove that for all events A ∈ G, E 1A P(E ∩ E ′ | G) = E 1A P(E | G) × PE (E ′ | G) .
By Equation (37) for the second equality, the left-hand side of Equation (38) can be rewritten as E 1A P(E ∩ E ′ | G) = E 1A E[1E 1E ′ | G] = E[1A 1E 1E ′ ] . 29
(38)
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
By G–measurability of PE (E ′ | G) for the second equality and by Equation (37) for the third equality, the right-hand side of Equation (38) can first be rewritten as E 1A P(E | G) × PE (E ′ | G) = E 1A E[1E | G] × PE (E ′ | G) = E 1A E[1E PE (E ′ | G) | G] = E 1A 1E PE (E ′ | G) .
We continue the calculation by noting, for the first and last equalities below, that, by definition, E[ · 1E ] = P(E) × EE [ · 1E ], where EE denotes the conditional expectation with respect to the event E, and, for the third equality, by resorting again to Equation (37) with EE : E 1A 1E PE (E ′ | G) = EE 1A PE (E ′ | G) = EE 1A EE [1E ′ | G] = EE [1A 1E ′ ] = E[1A 1E 1E ′ ] . The proof is concluded by collecting all equalities.
D.2. Consequences of the Hidden Markov Model Formulation Before we discuss (and prove) that Assumption 5.1 is natural, it is useful to state a reminder on how some conditionings may be simplified. Recall the definition of Ftall from Section 2: Ftall = σ this is the richer filtration we consider.
hτ , xτ , ητ (a) a∈A
τ ⩽t−1
, ht , x t ;
The HMM model implies that, for τ < τ ′ , conditionally on hτ , the distribution of hτ ′ is independent of past and present information, that is, Fτall and ητ (a), but of course, not from future information corresponding to rounds τ + 1 till τ ′ , like the contexts xτ +1:τ ′ . More formally and for example, we have, for τ < τ ′ , P(hτ ′ = h′ | Fτall , ητ (aτ ), xτ +1:τ ′ ) = P(hτ ′ = h′ | hτ , xτ +1:τ ′ ) . Via the same tools as in Appendix D.1, this entails, in particular, that for all h ∈ [H], P{hτ =h} (hτ ′ = h′ | Fτall , ητ (aτ ), xτ +1:τ ′ ) = P{hτ =h} (hτ ′ = h′ | xτ +1:τ ′ ) .
(39)
D.3. Some Classic Condition Leading to Assumption 5.1 In this appendix, we show how Assumption 5.1 follows from the assumption below, considered by Cappé et al. (2005, Chapter 3) and rewritten in our context. Remember that we consider an homogeneous HMM (the distributions of transitions and emissions do not depend on the round), which is why the assumption is only stated with hidden states h1 and h2 . Assumption D.2 (Cappé et al., 2005, Assumption 59, “strong mixing condition”). There exists a transition kernel K : X × [H] → (0, 1) and measurable functions ζ − , ζ + : X → (0, +∞), with ζ − ⩽ ζ + , such that for all Borel sets E of X , and all h, h′ ∈ [H], Z Z ζ − (x) K(x, h′ ) dx ⩽ P(h2 = h′ , x2 ∈ E | h1 = h) ⩽ ζ + (x) K(x, h′ ) dx . E
E
Cappé et al. (2005, Proposition 61) almost immediately entails the following lemma. Lemma D.3. Assumption D.2 entails Assumption 5.1, whenever ζ − (x) < 1. sup 1 − + ζ (x) x∈X This is the case at least when X is finite. 30
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Proof. By homogeneity, it suffices to prove Assumption 5.1 for s = 1 and t ⩾ 2. Cappé et al. (2005, Proposition 61, based on Assumption D.2 above) guarantees that for all t ⩾ 2, for all pairs h, h′ ∈ [H] of hidden states, X
j∈[H]
P{h1 =h} (ht = j | x1:t ) − P{h1
=h′ }
t Y ζ − (xτ ) . 1− + (ht = j | x1:t ) ⩽ 2 ζ (xτ ) τ =2
(40)
Under the HMM property, ht is independent of x1 given h1 ; thus x1 can be removed from the conditionings in the left-hand sides of the above inequality (see Appendix D.2). Each of the terms 1 − ζ − (xτ )/ζ + (xτ ) is non-negative, since ζ − ⩽ ζ + by assumption. We further bound the right-hand side of Equation (40) by 2γ t−1 (which is the upper bound claimed by Assumption 5.1), where ζ − (x) . γ = sup 1 − + ζ (x) x∈X When X is finite, Assumption D.2 imposed that ζ − (x) > 0 for all x ∈ X , thus each of the finitely many terms in the defining maximum of γ are strictly smaller than 1, therefore, so is γ.
31
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
E. Proof of Theorem 5.2 The aim of this section is to prove the main result, which we restate below. Theorem 5.2. Assume the horizon T is known to the learner and fix δ ∈ (0, 1). Consider the strategy of Box A with a belief 3/4 estimation subroutine and ℓ = ⌈T 3/4 ⌉, as well as the confidence √ satisfying Assumption 4.1, with parameters λ = T bonuses εt,a = 1 + d/λ for t ∈ [1, ℓ] and for t ⩾ ℓ + 1, =ft }| { z s r w w w √ w −1 sT (st − 1)(1 + st γ)ℓ 4sT b w + Cη (st − 1)ℓ εt,a = Ubelief (t, δ/2) + w wG(st −1)ℓ bt ⊗ ϕ(a, xt ) w λ H Cθ⋆ + 4 δ(1 − γ) δ 2 ! (st −1)ℓ X 2(st − 1)γ + Ubelief (τ, δ/2) , + 1−γ τ =1 where st = ⌈t/ℓ⌉ denotes the stage to which round t belongs. Then, under Assumption 2.1 (boundedness of rewards), Assumption 2.3 (sub-Gaussian noise), Assumption 4.1 (controlled belief estimation error), and Assumption 5.1 (exponentially fast forgetting), with probability at least 1 − δ, up to poly-log factors, e T 7/8 . RT = O A closed-form expression of the regret bound may be found in the proof, see Equations (47) and (48).
The analysis follows the same structure as the one in Appendix A for the simplified model. Therein, the main piece in establishing the regret bound of Theorem A.1 consisted of building confidence intervals in Lemma A.2: the total regret bound was basically given by 2 times the sum of the errors margins of these confidence intervals. The counterpart to Lemma A.2 is the following. The only difference is that union bounds must be performed with greater care, hence the consideration of stage-varying confidence levels 1 − δs . Lemma E.1. Fix errors levels δs ∈ (0, 1) for each s ⩾ 1. Under Assumptions 2.1–2.3–5.1, for all s ⩾ 1, for all t ∈ [(s − 1)ℓ + 1, sℓ], with probability at least 1 − 2δs , ∀a ∈ A, where ε′t,1,λ,δ1 ,a = 1 + w
X
h∈[H]
bt (h)ϕ(a, xt )T θ⋆h −
X
h∈[H]
√ d/λ for s = 1, and for s ⩾ 2, w
w w
−1 ε′t,s,λ,δs ,a = wbt − b bt w1 + w wG(s−1)ℓ
w w b bt ⊗ ϕ(a, xt ) w w
b(s−1)ℓ,h ⩽ ε′ b bt (h)ϕ(a, xt )T θ t,s,λ,δs ,a ,
√ λ H Cθ ⋆ + 2
s
4(s − 1)(1 + sγ)ℓ + δs (1 − γ)
(41)
r
1 Cη (s − 1)ℓ δs ! (s−1)ℓ X 2(s − 1)γ + + kbτ − b bτ k1 . 1−γ τ =1
Appendix E.1 provides the proof of Lemma E.1, while Appendix E.2 proves Theorem 5.2 based on Lemma E.1. E.1. Proof of Lemma E.1 b(s−1)ℓ,h instead of θ bt−1,h , but The proof adapts the one of Lemma A.2: the very beginning is similar, up to considering θ the core of the proof is significantly different, as the LinUCB approach by Abbasi-Yadkori et al. (2011) cannot be followed anymore; see details on the reasons for this non-applicability in Section 3 and in Appendix B. The proof below actually details the claims and proof structure presented in Appendix B, partly based on some L2 –Markovbased deviation inequality by Nelson et al. (2022). √ Proof. The deterministic bound 1+ d/λ actually holds for all s and t, see the comments after the statement of Lemma A.2. The rest of the proof thus only covers the case s ⩾ 2. By a triangle inequality and by leveraging again Assumption 2.1, the 32
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
target quantity can be bounded by X
h∈[H]
bt (h)ϕ(a, xt )T θ⋆h −
h∈[H]
⩽
X
h∈[H]
|
h∈[H]
b(s−1)ℓ,h b bt (h)ϕ(a, xt )T θ
| · |⩽1
X
⩽
X
}| { X z b b(s−1)ℓ,h bt (h) − b bt (h) ϕ(a, xt )T θ⋆h + bt (h)ϕ(a, xt )T θ⋆h − θ h∈[H]
(bt (h) − b bt (h) + {z
}
=kbt −b bt k1
X
h∈[H]
|
b b(s−1)ℓ,h . bt (h)ϕ(a, xt )T θ⋆h − θ {z
b(s−1)ℓ −θ⋆ ) =(b bt ⊗ϕ(a,xt ))T (θ
(42)
}
b(s−1)ℓ in The rest of the proof bounds the second term of the upper bound above. We first rewrite the differences θ ⋆ − θ terms of the payoffs, using the definitions around Equation (7):
(s−1)ℓ
b(s−1)ℓ = G−1 G(s−1)ℓ θ ⋆ − θ⋆ − θ (s−1)ℓ
X
τ =1
b bτ ⊗ ϕ(aτ , xτ ) rτ (aτ ) (s−1)ℓ
λIdH θ⋆ − = G−1 (s−1)ℓ
X
τ =1
T ⋆ b bτ ⊗ ϕ(aτ , xτ ) θ . bτ ⊗ ϕ(aτ , xτ ) rτ (aτ ) − b
We substitute rτ (aτ ) in the expression above, but first rewrite it : def
rτ (aτ ) = ϕ(aτ , xτ )T θ ⋆hτ + ητ (aτ ) X X T ϕ(aτ , xτ )T θ⋆h′ b̄τ (h′ ) − b bτ (h′ ) + b bτ ⊗ ϕ(aτ , xτ ) θ⋆ + ητ (aτ ) . b̄τ (h′ )θ ⋆h′ + = ϕ(aτ , xτ )T θ⋆hτ − h′ ∈[H]
h′ ∈[H]
The second term in Equation (42) may therefore be rewritten as X
h∈[H]
T b(s−1)ℓ − θ⋆ b b(s−1)ℓ,h = b θ bt ⊗ ϕ(a, xt ) bt (h)ϕ(a, xt )T θ ⋆h − θ
T ⋆ ′ ′ ′ = b bt ⊗ ϕ(a, xt ) G−1 , (s−1)ℓ Sdiff,(s−1)ℓ + Sbelief,(s−1)ℓ + Seta,(s−1)ℓ − λIdH θ
where
(s−1)ℓ ′ = Sdiff,(s−1)ℓ
X
τ =1 (s−1)ℓ ′ = Sbelief,(s−1)ℓ
X
X ⋆ ′ ⋆ ϕ(aτ , xτ ) θhτ − b̄τ (h )θ h′ b bτ ⊗ ϕ(aτ , xτ ) , T
h′ ∈[H]
X
τ =1 h′ ∈[H] (s−1)ℓ ′ Seta,(s−1)ℓ =
X
τ =1
ϕ(aτ , xτ )T θ⋆h′ b̄τ (h′ ) − b bτ (h′ ) b bτ ⊗ ϕ(aτ , xτ ) ,
ητ (aτ ) b bτ ⊗ ϕ(aτ , xτ ) .
′ The Euclidean norm of each of these three term is bounded in a series of lemmas below: Sdiff,(s−1)ℓ in Lemma E.2, ′ ′ Seta,(s−1)ℓ in Lemma E.3, and Sbelief,(s−1)ℓ in Lemma E.4.
33
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
More precisely, we bound the second term in Equation (42) by a Cauchy-Schwarz inequality and a triangle inequality: X
h∈[H]
=
b b(s−1)ℓ,h bt (h)ϕ(a, xt )T θ ⋆h − θ
T ⋆ ′ ′ ′ b bt ⊗ ϕ(a, xt ) G−1 (s−1)ℓ Sdiff,(s−1)ℓ + Sbelief,(s−1)ℓ + Seta,(s−1)ℓ − λIdH θ
w w w w w ′ w w ′ w −1 w w ′ ⋆ b w w w w w w wS ⩽w G b ⊗ ϕ(a, x ) t w diff,(s−1)ℓ 2 + Seta,(s−1)ℓ 2 + Sbelief,(s−1)ℓ 2 + kλθ k2 , w (s−1)ℓ t 2
√ where kλθ⋆ k2 ⩽ λ H Cθ ⋆ by Assumption 2.1. Lemma E.2 ensures that with probability at least 1 − δs ,
s w w(s−1)ℓ w w X X w 4(s − 1)(1 + sγ)ℓ w w ⋆ ⋆ ′ T w b̄τ (h )θ h′ b bτ ⊗ ϕ(aτ , xτ )w ⩽ ϕ(aτ , xτ ) θhτ − , diff,(s−1)ℓ 2 = w w w δs (1 − γ) ′
w ′ wS
τ =1
h ∈[H]
2
where we performed some bounding to get a more compact bound. Lemma E.3 ensures that with probability at least 1 − δs , w(s−1)ℓ w r w X w w 1 w w w ητ (aτ ) b bτ ⊗ ϕ(aτ , xτ )w ⩽ Cη (s − 1)ℓ . eta,(s−1)ℓ 2 = w w w δs
w ′ wS
τ =1
2
Finally, Lemma E.4 guarantees that with probability 1,
w w(s−1)ℓ (s−1)ℓ w w X X X w w w 2(s − 1)γ w w ⋆ T ′ ′ b b w =w wbτ − b b ⊗ϕ(a , x ) ϕ(a , x ) θ b̄ (h )− b (h ) ⩽ + bτ w1 . ′ w τ τ τ τ τ τ τ h belief,(s−1)ℓ 2 w w 1−γ ′
w ′ wS
τ =1 h ∈[H]
τ =1
2
The proof is concluded by collecting all the bounds above and by applying a union bound. w w ′ w E.1.1. B OUND ON wSdiff,sℓ 2
This is the most difficult term to bound and we follow the approach described at a high level in Appendix B: this approach L2 –norm; constitutes the key technical contribution by Nelson et al. (2022). In particular, we apply Markov’s p inequality in p this has the drawback that the associated high-probability bound depends on the risk δ through 1/δ instead of ln(1/δ) in the LinUCB approach (see Appendix A). Lemma E.2. Under Assumptions 2.1 and 5.1, for all s ⩾ 1, w w2 sℓ w wX hw i X w 2s(s + 1)ℓγ 2 w w ⋆ b ⋆ T ′ w = Ew b̄ (h)θ b ⊗ ϕ(a , x ) − θ E wSdiff,sℓ ϕ(a , x ) . w ⩽ 4sℓ + τ τ τ τ τ τ h h τ 2 w w 1−γ τ =1
h∈[H]
2
Thus, for all δ ∈ (0, 1), for each s ⩾ 1, with probability at least 1 − δ,
s w w sℓ w wX X w ′ w 2s(s + 1)ℓγ 1 w w ⋆ b ⋆ T wSdiff,sℓ w = w 4sℓ + . b̄τ (h)θ h bτ ⊗ ϕ(aτ , xτ )w ⩽ ϕ(aτ , xτ ) θhτ − 2 w w δ 1−γ τ =1
h∈[H]
2
Proof. The second inequality follows from the first one via Markov’s inequality. We thus only prove the first inequality below. Step 1: Preparation. Introduce the scalar-valued random variables X ⋆ ⋆ T b̄τ (h)θ h , zτ = ϕ(aτ , xτ ) θ hτ − h∈[H]
34
where |zτ | ⩽ 2
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
by Assumption 2.1 and the fact that b̄τ is a probability distribution. Therefore, by developing the squared norm and by applying the inequalities above, as well as the bound of Equation (6), to the diagonal terms only, the target quantity may be rewritten as and bounded by "w sℓ w2 # wX w E w bτ ⊗ ϕ(aτ , xτ )w zτ b w w 2 τ =1 " T # sℓ sℓ XX bτ ⊗ ϕ(aτ , xτ ) b bτ ′ ⊗ ϕ(aτ ′ , xτ ′ ) E zτ zτ ′ b = τ =1 τ ′ =1
sℓ X ⩽ E zτ2 +2 τ =1
|
{z
⩽4sℓ
}
T # b b bτ ′ ⊗ ϕ(aτ ′ , xτ ′ ) . E zτ zτ ′ bτ ⊗ ϕ(aτ , xτ ) 1⩽τ <τ ′⩽sℓ {z } | X
"
(43)
to be dealt with
bsℓ for t ⩾ 1. Now, we note that the inner product in the cross terms We recall that we introduced Ut = σ x1:t , θ s⩽st −1 ′ above (marked as “to be dealt with”) is σ(Uτ )–measurable, as, in particular, actions aτ and aτ ′ (since the algorithm proceeds in stages) and estimated beliefs b bτ ′ and b bτ ′ are so. By the Cauchy-Schwarz inequality and the bound of Equation (6), it is also seen to be smaller than 1. Therefore, by the tower rule, we further bound the τ < τ ′ cross term above by is σ(U ′ )–measurable
τ z T}| {# b E zτ zτ ′ b bτ ⊗ ϕ(aτ , xτ ) bτ ′ ⊗ ϕ(aτ ′ , xτ ′ )
"
"
= E E z τ z τ ′ | Uτ ′
T # b b ⩽ E E z τ z τ ′ | Uτ ′ . bτ ⊗ ϕ(aτ , xτ ) bτ ′ ⊗ ϕ(aτ ′ , xτ ′ ) {z } | ⩽1
′
To get the claimed bound, we prove that for each 1 ⩽ τ < τ ⩽ sℓ, τ ′ −τ 2γ if τ ⩾ (sτ ′ − 1)ℓ + 1, i.e., if τ belongs to the same stage as τ ′ , E z τ z τ ′ | Uτ ′ ⩽ ′ 2 γ τ −(sτ ′ −1)ℓ if τ ⩽ (sτ ′ − 1)ℓ, i.e., if τ and τ ′ belong to different stages,
(44)
which we do next in the subsequent steps of the proof. Then, based on Equation (44), we obtain X E z τ z τ ′ | Uτ ′ ′ ′ =(s′ −1)ℓ γ τ −(s −1)ℓ ⩽γ/(1−γ) 1⩽τ <τ ′ ⩽sℓ z }| { z }| { ! ′ ′ (sτ ′ −1)ℓ s sℓ τX −1 X X X ′ ′ τ −τ τ −(sτ ′ −1)ℓ γ ⩽2 γ + s′ =1 τ ′ =(s′ −1)ℓ+1
⩽2
s X
′
sℓ X
τ =1
′ ′ (s′ − 1)ℓ γ τ −(s −1)ℓ +
s′ =1 τ ′ =(s′ −1)ℓ+1
τ =(sτ ′ −1)ℓ+1
γ 1−γ
s
⩽
2γ X ′ s(s + 1)ℓγ , sℓ= 1−γ ′ 1−γ s =1
from which the first inequality of the lemma follows by Equation (43). It only remains to show Equation (44). Step 2: Proof of Equation (44), part 1. In this step, we show that X X P{hτ =h} (hτ ′ = h′ | Uτ ′ ) − P hτ ′ = h′ | Uτ ′ . P(hτ = h | Uτ ′ ) E z τ z τ ′ | Uτ ′ ⩽ h∈[H]
(45)
h′ ∈[H]
In the closed-form expression for zτ zτ ′ , the only quantities that are not Uτ ′ –measurable are θ⋆hτ and θ⋆hτ ′ ; the other terms are Uτ ′ –measurable: ϕ(aτ , xτ ) and ϕ(aτ ′ , xτ ′ ), as well as b̄τ (h) and b̄τ ′ (h). Also, by definition of b̄τ ′ , X b̄τ ′ (h) θ ⋆h . E θ⋆hτ ′ | Uτ ′ = h∈[H]
35
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Therefore,
E z τ z τ ′ | Uτ ′
X X b̄τ ′ (h)θ ⋆h Uτ ′ b̄τ (h)θ⋆h ϕ(aτ ′ , xτ ′ )T θ⋆hτ ′ − = Eϕ(aτ , xτ )T θ⋆hτ − h∈[H]
h∈[H]
X b̄τ ′ (h)θ ⋆h Uτ ′ . = Eϕ(aτ , xτ )T θ⋆hτ ϕ(aτ ′ , xτ ′ )T θ⋆hτ ′ −
h∈[H]
We continue the calculation by applying formulas of the form: for all Uτ ′ –measurable functions F , h i X P hτ = h and hτ ′ = h′ | Uτ ′ F θ⋆h , θ ⋆h′ . E F θ⋆hτ , θ⋆hτ ′ Uτ ′ = h,h′ ∈[H]
To do so, we consider the functions
G : θ⋆h , θ⋆h′ − 7 → ϕ(aτ , xτ )T θ⋆h ϕ(aτ ′ , xτ ′ )T θ ⋆h′ X b̄τ ′ (j)θ ⋆j , θ ⋆h 7−→ −ϕ(aτ , xτ )T θ⋆h ϕ(aτ ′ , xτ ′ )T
and
j∈[H]
and get the rewriting E z τ z τ ′ | Uτ ′ =
X
P hτ = h and hτ ′ = h′ | Uτ ′ G θ⋆h , θ⋆h′ h,h′ ∈[H] X X b̄τ ′ (j) G θ⋆h , θ⋆j . P h τ = h | Uτ ′ − h∈[H]
G θ⋆h , θ⋆h′
The inequality claimed in Equation (45) follows by noting that Lemma D.1 (Bayes’ formula with expectations conditional to σ–algebras).
j∈[H]
⩽ 1 (by Assumption 2.1) and by applying
Step 3: Proof of Equation (44), part 2. Given the bound of Equation (45), it suffices to show that for all h ∈ [H], X
h′ ∈[H]
P{hτ =h} (hτ ′ = h′ | Uτ ′ ) − P hτ ′ = h′ | Uτ ′ ⩽
(
′
2 γ τ −τ ′ 2 γ τ −(sτ ′ −1)ℓ
if τ ⩾ (sτ ′ − 1)ℓ + 1, i.e., if τ belongs to the same stage as τ ′ , if τ ⩽ (sτ ′ − 1)ℓ, i.e., if τ and τ ′ belong to different stages.
(46)
In the case when τ ⩾ (sτ ′ − 1)ℓ + 1, i.e., when sτ = sτ ′ , we combine a law of total probability with Lemma D.1 to get the decomposition X P hτ = j | Uτ ′ P{hτ =j} hτ ′ = h′ | Uτ ′ . P h τ ′ = h ′ | Uτ ′ = j∈[H]
bsℓ with Also, by the HMM conditional independence discussed around Equation (39), since Uτ ′ is generated by estimates θ s ⩽ sτ ′ − 1 = sτ −1 , which are therefore more in the past than hτ , and by the contexts x1:τ ′ , we have P{hτ =h} (hτ ′ = h′ | Uτ ′ ) = P{hτ =h} (hτ ′ = h′ | xτ +1:τ ′ ) .
Using successively these equalities (together with a triangle inequality), the quantity of interest may be upper bounded by X P{hτ =h} (hτ ′ = h′ | Uτ ′ ) − P hτ ′ = h′ | Uτ ′ h′ ∈[H]
⩽
X
j∈[H]
=
X
j∈[H]
P h τ = j | Uτ ′ P h τ = j | Uτ ′
X
h′ ∈[H]
X
h′ ∈[H]
P{hτ =h} (hτ ′ = h′ | Uτ ′ ) − P{hτ =j} hτ ′ = h′ | Uτ ′
P{hτ =h} (hτ ′ = h′ | xτ +1:τ ′ ) − P{hτ =j} hτ ′ = h′ | xτ +1:τ ′
|
{z
⩽2γ τ ′ −τ
36
}
,
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics ′
where the ⩽ 2γ τ −τ bound follows from Assumption 5.1. This proves Equation (46) in the first case, when τ belongs to the same stage as τ ′ . For the second case, when τ ⩽ (sτ ′ − 1)ℓ, i.e., τ belongs to an stage earlier than the one of τ ′ , we adapt the argument above by also introducing h(sτ ′ −1)ℓ . Two combinations of a law of total probability together with Lemma D.1 and a triangle inequality entail the following bound on the quantity of interest: X
h′ ∈[H]
⩽
P{hτ =h} (hτ ′ = h′ | Uτ ′ ) − P hτ ′ = h′ | Uτ ′
X X X
h′ ∈[H] i∈[H] j∈[H]
P h(sτ ′ −1)ℓ = i | Uτ ′ P h(sτ ′ −1)ℓ = j | Uτ ′
× P{hτ =h and h(s ′ −1)ℓ =i} (hτ ′ = h′ | Uτ ′ ) − P{h(s ′ −1)ℓ =j} hτ ′ = h′ | Uτ ′ τ
τ
.
bsℓ with s ⩽ sτ ′ − 1 which only depend on information till round (sτ ′ − 1)ℓ, Given that Uτ ′ is generated by estimates θ and by the contexts x1:τ ′ , we have, by the HMM conditional independence discussed around Equation (39), that for all j, h′ ∈ [H], P{h(s ′ −1)ℓ =j} (hτ ′ = h′ | Uτ ′ ) = P{h(s ′ −1)ℓ =j} (hτ ′ = h′ | x(sτ ′ −1)ℓ+1:τ ′ ) . τ
τ
Actually, since τ ⩽ (sτ ′ − 1)ℓ, we even have, with the same arguments, for all j, h, h′ ∈ [H], P{hτ =h and h(s ′ −1)ℓ =j} (hτ ′ = h′ | Uτ ′ ) = P{h(s ′ −1)ℓ =j} (hτ ′ = h′ | x(sτ ′ −1)ℓ+1:τ ′ ) . τ
τ
Substituting these equalities in the bound established above, and resorting to Assumption 5.1 entails X
h′ ∈[H]
⩽
P{hτ =h} (hτ ′ = h′ | Uτ ′ ) − P hτ ′ = h′ | Uτ ′
X X
P h(sτ ′ −1)ℓ = i | Uτ ′ P h(sτ ′ −1)ℓ = j | Uτ ′
×
P{h(s ′ −1)ℓ =i} (hτ ′ = h′ | x(sτ ′ −1)ℓ+1:τ ′ ) − P{h(s ′ −1)ℓ =j} hτ ′ = h′ | x(sτ ′ −1)ℓ+1:τ ′
j∈[H] i∈[H]
X
h′ ∈[H]
|
τ
τ
′
{z
⩽2γ τ −(sτ ′ −1)ℓ
This proves Equation (46) in the second case, and concludes the proof of the lemma.
.
}
w ′ w w E.1.2. B OUND ON wSeta,sℓ 2 w w ′ w w To bound the term Seta,sℓ 2 , we mimic, and simplify, the proof conducted right before for Lemma E.2: we adapt its Step 1 (and do not need Steps 2 and 3). Actually, under the stronger noise Assumption 2.2, a LinUCB-type approach as in Appendix A could have been followed (i.e., Lemma A.3 could have been applied). We however prefer to mimic and simplify the proof of Lemma E.2. Lemma E.3. Under the Assumptions 2.1 and 2.3, for all s ⩾ 1, w w2 sℓ w wX hw i w w ′ b w2 = Ew η (a ) b ⊗ ϕ(a , x ) E wSeta,sℓ w τ τ τ τ τ w ⩽ Cη sℓ . 2 w w τ =1
2
Thus, for all δ ∈ (0, 1), for each s ⩾ 1, with probability at least 1 − δ,
w w r sℓ wX w w ′ w 1 w w wSeta,sℓ w = w Cη sℓ . ητ (aτ ) b bτ ⊗ ϕ(aτ , xτ )w ⩽ 2 w w δ τ =1
2
37
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Proof. The second inequality follows from the first one via Markov’s inequality. For the first inequality, we develop the squared norm and apply the bound of Equation (6): "w sℓ w2 # w wX E w ητ (aτ ) b bτ ⊗ ϕ(aτ , xτ )w w w 2
τ =1
⩽
sℓ X
τ =1
E ητ (aτ )2 + 2
X
1⩽τ <τ ′⩽sℓ
T E ητ (aτ )ητ ′ (a′τ ) b bτ ⊗ ϕ(aτ , xτ ) b bτ ′ ⊗ ϕ(aτ ′ , xτ ′ ) .
For the first component of above inequality, by Assumption 2.3 and using that the selected action at is Ftall –measurable, we have, for all τ ⩾ 1, i i X h h 1{at =a} E ητ (a)2 Fτall ⩽ Cη , E ητ (aτ )2 Fτall = a∈A
so that, by the tower rule,
h sℓ sℓ i i X h X 2 all 2 ⩽ sℓCη . E E ητ (aτ ) Fτ E ητ (aτ ) = τ =1
τ =1
For the second sum, fix a pair 1 ⩽ τ < τ ′ ⩽ sℓ. We use that aτ is measurable w.r.t. Fτall , and that Fτall′ is generated by xτ , the ητ (a), and other variables, to show that the random variables ητ (aτ ) and ϕ(aτ , xτ ) are all Fτall′ –measurable. We also have that b bτ and b bτ ′ are measurable w.r.t. x1 , . . . , xτ ′ , thus w.r.t. Fτall′ , and by similar arguments, aτ ′ and ϕ(aτ ′ , xτ ′ ) are all also Fτ ′ –measurable. Therefore, by the tower rule and by Assumption 2.3, T ′ b b E ητ (aτ )ητ ′ (aτ ) bτ ⊗ ϕ(aτ , xτ ) bτ ′ ⊗ ϕ(aτ ′ , xτ ′ ) " # T X = E ητ (aτ ) b bτ ⊗ ϕ(aτ , xτ ) b bτ ′ ⊗ ϕ(aτ ′ , xτ ′ ) 1{a′ =a} E ητ ′ (a) | F all′ = 0 . τ
τ
a∈A
The proof is concluded by collecting all (in)equalities.
{z
|
=0
}
w w ′ w E.1.3. B OUND ON wSbelief,sℓ 2 w w ′ w w To bound the term Sbelief,sℓ 2 , we also mimic, and simplify, the proof of Lemma E.2 conducted in Appendix E.1.1: we do not need its Steps 1 and 2 and we adapt its Step 3. Lemma E.4. Under Assumptions 2.1 and 5.1, for all s ⩾ 1, with probability 1, w w sℓ sℓ w wX X X w w w ′ w 2sγ w w T ⋆ b b wbτ − b wSbelief,sℓ w = w bτ w1 . ϕ(a , x ) θ b̄ (h) − b (h) ⩽ + b ⊗ ϕ(a , x ) w τ τ τ τ τ τ τ h 2 w w 1 − γ τ =1 τ =1 h∈[H]
2
Proof. By the triangle inequality and the bounds indicated by Assumption 2.1 and Equation (6),
k · k2 ⩽1 w sℓ | · |⩽1 }| {w sℓ sℓ X w wX X z }| { z X X w w w w T ⋆ b b b wb̄τ − b bτ w1 . b̄ (h) − b (h) = ϕ(a , x ) θ ⩽ b̄ (h) − b (h) b ⊗ ϕ(a , x ) w τ τ τ τ τ τ τ τ τ w h w w τ =1 h∈[H]
2
τ =1 h∈[H]
τ =1
The claimed bound is obtained by another triangle inequality and by Lemma E.5 below: for all s ⩾ 1,
sℓ sℓ sℓ X X X w w w w w w w w ⩽ 2sγ + wb̄τ − bτ w + wbτ − b wb̄τ − b kbτ − b bτ w1 . b bτ w1 ⩽ τ 1 1 1 − γ τ =1 τ =1 τ =1
Lemma E.5. Under Assumption 5.1 (exponentially fast forgetting of initial condition), for each s ⩾ 1, with probability 1, sℓ X
w w wbτ − b̄τ w ⩽ 1
τ =(s−1)ℓ+1
38
2γ . 1−γ
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Proof. The proof is a mere adaptation of Step 3 of the proof of Lemma E.2 located in Appendix E.1.1. By two applications of the law of total probability and Lemma D.1 for the second equality, by the conditional independence discussed around Equation (39) for the third equality, and by a triangle inequality together with Assumption 5.1 for the final inequality, sℓ X
w w wbτ − b̄τ w 1
τ =(s−1)ℓ+1
=
sℓ X
P(hτ = h | x1:τ ) − P(hτ = h | Uτ )
sℓ X
X
X
X
sℓ X
X
sℓ X
X X
τ =(s−1)ℓ+1 h∈[H]
=
τ =(s−1)ℓ+1 h∈[H]
=
i∈[H]
X
τ =(s−1)ℓ+1 h∈[H] i∈[H]
⩽
τ =(s−1)ℓ+1 i∈[H] j∈[H]
×
X
h∈[H]
P h(s−1)ℓ = i | x1:τ P{h(s−1)ℓ =i} (hτ = h | x1:τ ) −
X
P h(s−1)ℓ = j | Uτ P{h(s−1)ℓ =j} (hτ = h | Uτ )
X
P h(s−1)ℓ = j | Uτ P{h(s−1)ℓ =j} hτ = h | x(s−1)ℓ+1:τ
j∈[H]
P h(s−1)ℓ = i | x1:τ P{h(s−1)ℓ =i} hτ = h | x(s−1)ℓ+1:τ −
j∈[H]
P h(s−1)ℓ = i | x1:τ P h(s−1)ℓ = j | Uτ
P{h(s−1)ℓ =i} (hτ = h | x(s−1)ℓ+1:τ ) − P{h(s−1)ℓ =j} hτ = h | x(s−1)ℓ+1:τ
|
{z
,
}
⩽2γ τ −(s−1)ℓ
from which the stated bound follows, by the formula for geometric sums. E.2. Proof of Theorem 5.2
This section now proves Theorem 5.2 based on Lemma E.1: as in Appendix A—namely, the proof of Theorem A.1 based on Lemma A.2—, the final regret bound is basically given by 2 times the sum of the upper confidence bounds stated in Lemma E.1. We adapt proof of Theorem A.1 first, to take into account the staged nature of the strategy of Box A, and second, to carefully takepcare of unions bounds. Indeed, Lemma A.2 offered a deviation bound uniform over time rounds t ⩾ 1 and with a low ln(1/δ) dependency on √ the risk level δ ∈ (0, 1). On the contrary, Lemma E.1 only provides deviation bounds for each stage s ⩾ 1 with a 1/ δs dependency on the risk level δs used for that stage. The confidence bonuses εt,a considered in Theorem 5.2 correspond to the upper bounds of Lemma E.1 up to the replacements of δs by δ/(4sT ) and of the unknown kbτ − b bτ k1 by their high-probability bounds Ubelief (τ, δ/2). Proof. We do not substitute yet the specific values of λ and ℓ considered and recall that T is assumed to be known. We denote by ε†t,a the upper bound read in Lemma E.1 for the risk δ/(4sT ) and by substituting the stage st to which a round √ t ⩾ 1 belongs, i.e., ε†t,a = 1 + d/λ for 1 ⩽ t ⩽ ℓ, and for ℓ + 1 ⩽ t ⩽ T , w
w
w w
−1 ε†t,a = wbt − b bt w1 + w wG(st −1)ℓ
w w b bt ⊗ ϕ(a, xt ) w w
√ λ H Cθ ⋆ + 4
2
s
sT (st − 1)(1 + st γ)ℓ + δ(1 − γ)
r
4sT Cη (st − 1)ℓ δ ! (st −1)ℓ X 2(st − 1)γ b + + kbτ − bτ k1 . 1−γ τ =1
By Lemma E.1 and a union bound, we have the following high-probability uniform deviation bound: with probability at 39
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
least 1 − δ/2, ∀1 ⩽ t ⩽ T,
∀a ∈ A,
X
h∈[H]
bt (h)ϕ(a, xt )T θ ⋆h −
X
h∈[H]
b(s −1)ℓ,h ⩽ ε† . b bt (h)ϕ(a, xt )T θ t,a t
From the guarantee above, we get similar guarantees as in Equations (15)–(16): with probability at least 1 − δ/2, X X b(s −1)ℓ,h b bt (h) ϕ(a, xt )T θ bt (h) ϕ(a, xt )T θ ⋆h ⩽ max ε†t,a + max t a∈A a∈A h∈[H] h∈[H] X X b(s −1)ℓ,h ⩽ ε† + b bt (h) ϕ(at , xt )T θ ⋆h . bt (h) ϕ(at , xt )T θ and t,at t h∈[H]
h∈[H]
We now want to replace the terms kbτ − b bτ k1 by Ubelief (τ, δ/2) and to do so, we adapt the results developed in Equations (17) to (19), which only depend on the belief estimation subroutine and only require Assumption 4.1. More precisely, Equation (17) remains valid: with probability at least 1 − δ/2, n w w o def wbt − b ∀t ∈ [T0 , T ], bt w1 ⩽ Ubelief (t, δ/2) , where T0 = max 2, ⌈TB,M ,ν 1 + ln(2/δ) ⌉ .
Thus, given that G(st −1)ℓ λIdH for t ⩾ ℓ + 1 and by Equation (6), we also have, t ⩾ ℓ + 1, w w w w w −1 1w 1 wb w b w wG ⩽ b ⊗ ϕ(a, x ) b ⊗ ϕ(a, x ) . w t t w ⩽ t w w (st −1)ℓ t λ λ 2 2 √ Finally, taking into account that ε†t,a = 1 + d/λ = εt,a for 1 ⩽ t ⩽ ℓ, we have (whether T0 is larger or smaller than ℓ) that with probability at least 1 − δ/2, ε†t,a ⩽ εt,a + 2(T0 − 1)/λ ,
∀t ∈ [T0 , T ],
where the εt,a are the confidence bonuses considered in the statement of Theorem 5.2. The bounds above, together with the same arguments as in Equations (19) and (20) and the definition of the Box B algorithm as picking arms at maximizing some empirical upper confidence bounds, entail that with probability at least 1 − δ, T T X X X X max bt (h) ϕ(at , xt )T θ ⋆h ⩽ 2(T0 − 1) + 2εt,at + 4(T0 − 1)/λ . bt (h) ϕ(a, xt )T θ⋆h − RT = t=1
a∈A
h∈[H]
t=T0
h∈[H]
We now substitute bounds on the εt,at , by replacing ft in its definition by the upper bound fT and by bounding (sT − 1)ℓ < T therein, and also substitute the closed-form expression for T0 : with probability at least 1 − δ, T X Ubelief (t, δ/2) RT ⩽ (2 + 4T /λ) TB,M,ν 1 + ln(2/δ) + 2 t=1
+ 2Gsum where
√ λ H Cθ ⋆ + 4
s
T sT (1 + sT γ) + δ(1 − γ)
r
! T 2sT γ X 4sT T Cη + + Ubelief (τ, δ/2) , (47) δ 1 − γ τ =1
sT min{sℓ,T w X } w X w −1 w b w w Gsum = wG(s−1)ℓ bt ⊗ ϕ(at , xt ) w . 2
s=1 t=(s−1)ℓ+1
We bound Gsum by applying Lemma E.6 below to vectors y τ = b bτ ⊗ ϕ(aτ , xτ ), of dimension dH and with Euclidean norm smaller than 1 as indicated in Equation (6), till stage S = sT : we get the deterministic upper bound r 1 Gsum ⩽ √ 2 dHsT ℓ (1 + ℓ/λ) ln 1 + sT ℓ/(dHλ) . (48) λ 40
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
Equations (47) and (48) provide the closed-form regret bound claimed in the statement of Theorem 5.2. It now suffices to show that it is of order T 7/8 up to logarithmic factors for the choices ℓ = ⌈T 3/4 ⌉ and λ = T 3/4 . Actually, taking ℓ = ⌈T a ⌉ (thus sT = T /ℓ is of order T 1−a ) and λ = T b , recalling that TB,M,ν is a constant, we have that the regret bound of Equation (47) is of order, up to logarithmic terms, p √ √ √ T /λ + T + T /λ (1 + ℓ/λ) λ + T 3/2 /ℓ + T / ℓ + T /ℓ + T , | {z } ⩽T 3/2 /ℓ
i.e., of order T c where ( · )+ denotes the non-negative part and c = max 1 − b, 1/2, (1 − b)/2 + (a − b)+ /2 + max{b, 3/2 − a, 1/2} ;
an optimization over a ∈ [0, 1] and b ∈ [0, 1] leads to a = b = 3/4 and c = 7/8, which concludes the proof. Elliptic potential with staged updates. It only remains to prove the following extension of the classic elliptic potential lemma (see Lemma A.4 in Appendix A) to updates in stages. Lemma E.6. Consider vectors y t ∈ Rd with kyt k2 ⩽ 1, a parameter λ ⩾ 1, and the Gram matrices V0 = λId and Vt = λId +
t X
y τ yTτ
for t ⩾ 1 .
τ =1
For all integers S ⩾ 1 and ℓ ⩾ 1, we have: S X
sℓ X
S sℓ X w w −1/2 w 1 X w wV w √ y ⩽ (s−1)ℓ y τ 2 (s−1)ℓ τ 2 λ s=1 τ =(s−1)ℓ+1 q 1 ⩽√ 2 dSℓ (1 + ℓ/λ) log 1 + Sℓ/(dλ) . λ
w −1 wV
s=1 τ =(s−1)ℓ+1
The sum in Lemma E.6 differs from the sum bounded in Lemma A.4 in two ways: first, it involves terms of the form w −1 w w w wV w instead of wV −1/2 y t w , t−1 y t 2 t−1 2 √ which leads to an additional 1/ λ multiplicative term in our bound,pand second, the matrices V are actually “frozen” within stages, which entails the other additional multiplicative factor 1 + ℓ/λ. The proof below focuses on these two modifications. Remark E.7. Carpentier et al. (2020) provide some general study of the sums T X w −p/2 w wV w t−1 y t 2 , t=1
p for p ∈ (0, +∞). For p = 2, as in Lemma E.6 up p to staging, they obtain an upper bound of order T d/λ. This corresponds, up to logarithmic factors and up to the 1 + ℓ/λ term due to staging, to the right-most term of Lemma E.6. Therefore, the first inequality of Lemma E.6, while relying on the simple lower bound Vt−1 λId (see the proof above), looks sharp enough. Proof. We use Vt−1 λId for all t ⩾ 1 to get, for all s ⩾ 1 and all τ ⩾ 1, w −1 wV
(s−1)ℓ y τ
w w w w w w = wV −1/2 V −1/2 y τ w ⩽ √1 wV −1/2 y τ w , (s−1)ℓ (s−1)ℓ (s−1)ℓ 2 2 2 λ
which yields the first inequality stated in the lemma. We prove below that for all s ⩾ 1, s sℓ X w −1/2 w det(Vsℓ ) wV w . 2ℓ (1 + ℓ/λ) ln (s−1)ℓ y τ 2 ⩽ det V(s−1)ℓ τ =(s−1)ℓ+1
41
(49)
(50)
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
The second inequality then follows from Equation (50) and the application of a Cauchy-Schwarz inequality: s S S sℓ X X X w −1/2 w det(Vsℓ ) wV w 2ℓ (1 + ℓ/λ) ln (s−1)ℓ y τ 2 ⩽ det V (s−1)ℓ s=1 s=1 τ =(s−1)ℓ+1 v s u S u X det(VSℓ ) det(Vsℓ ) t , = 2Sℓ (1 + ℓ/λ) ln ⩽ 2Sℓ (1 + ℓ/λ) ln det V(s−1)ℓ det V0 s=1
together with the fact that det(V0 ) = λd and that the upper bound d log(λ+Sℓ/d) on ln det(VSℓ ) is given by Lemma A.6. We are thus only left to prove Equation (50). To do so, we show below that −1 −1 ∀j ∈ [ℓ − 1], V(s−1)ℓ (1 + ℓ/λ) V(s−1)ℓ+j , √ which, keeping in mind that kV −1/2 yk2 = yT V y, directly entails that sℓ X
p w −1/2 w wV w 1 + ℓ/λ (s−1)ℓ y τ 2 ⩽
τ =(s−1)ℓ+1
sℓ X
(51)
w −1/2 w wV yτ w .
τ =(s−1)ℓ+1
τ −1
2
The bound of Equation (50) is then obtained via the arguments between Equations (22) to (23) in the proof of Lemma A.4, applied within a stage, i.e., within the ℓ rounds from (s − 1)ℓ + 1 to sℓ. To prove Equation (51), we recall that (s−1)ℓ+j
V(s−1)ℓ+j − V(s−1)ℓ =
X
y τ yTτ ,
τ =(s−1)ℓ+1
where y τ yTτ Id since kyτ k2 ⩽ 1. We also recall that by definition, V(s−1)ℓ λId . Therefore, V(s−1)ℓ+j − V(s−1)ℓ j Id (j/λ) V(s−1)ℓ , which implies Equation (51) after inverting both sides.
42
thus V(s−1)ℓ+j (1 + ℓ/λ) V(s−1)ℓ ,
A Direct Approach for Handling Contextual Bandits with Latent State Dynamics
F. Numerical Simulations Numerical simulations will be provided in a version 2 of this article.
43