Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
Authors: Wooseong Cho
Taehyun Hwang
Joongkyu Lee
Min-hwan Oh
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement learning
Function approximation
Multinomial logistic regression
Regret analysis
Primary area: reinforcement_learning
TL;DR: We propose randomized exploration model-based RL algorithms with multinomial logistic function approximation.

Abstract: We study reinforcement learning with _multinomial logistic_ (MNL) function approximation where the underlying transition probability kernel of the _Markov decision processes_ (MDPs) is parametrized by an unknown transition core with features of state and action. For the finite horizon episodic setting with inhomogeneous state transitions, we propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. For our first algorithm, $\texttt{RRL-MNL}$, we adapt optimistic sampling to ensure the optimism of the estimated value function with sufficient frequency and establish that $\texttt{RRL-MNL}$ is both _statistically_ and _computationally_ efficient, achieving a $\tilde{\mathcal{O}}(\kappa^{-1} d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T})$ frequentist regret bound with constant-time computational cost per episode. Here, $d$ is the dimension of the transition core, $H$ is the horizon length, $T$ is the total number of steps, and $\kappa$ is a problem-dependent constant. Despite the simplicity and practicality of $\texttt{RRL-MNL}$, its regret bound scales with $\kappa^{-1}$, which is potentially large in the worst case. To improve the dependence on $\kappa^{-1}$, we propose $\texttt{ORRL-MNL}$, which estimates the value function using local gradient information of the MNL transition model. We show that its frequentist regret bound is $\tilde{\mathcal{O}}(d^{\frac{3}{2}} H^{\frac{3}{2}} \sqrt{T} + \kappa^{-1} d^2 H^2)$. To the best of our knowledge, these are the first randomized RL algorithms for the MNL transition model that achieve both computational and statistical efficiency. Numerical experiments demonstrate the superior performance of the proposed algorithms.

Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
Wooseong Cho" Seoul National University Seoul, South Korea wooseong_choõsnu. ac kr
Taehyun Hwang" Seoul National University Scoul, South Korea th hwwng@snu....mmm..m..m.....u.uu. ac kr
Joongkyu Lee Scoul National University Scoul, South Korea
Min-hwan Oh Scoul National University Scoul, South Korea minoh@snu. ac. kr
jkleee7770snu ac.
Abstract
We study reinforcement learning with multinomial logistic (MNL) function approx- imation where the underlying transition probability kernel of the Markov decision processes (MDPs) parametrized by an unknown transition core with features state and action. For the finite horizon episodic setting with inhomogeneous state transitions, we propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. For our first algorithm, RRL-MNL, we adapt optimistic sampling to ensure the optimism of the estimated value function with sufficient frequency. We establish that RRL-MNL achieves ( Ed H /T) fre- quentist regret bound with constant-time computational cost per episode. Here, is the dimension of the transition core, H is the horizon length, 7 is the total number steps, and x a problem-depender cality of RRL-MNL. its regret bound scales with ~ which is potentially large in the worst case. To improve the dependence on x we propose ORRL- MNLL, which estimates the value function using the local gradient information of the MNL transi- tion model. We show that its frequentist regret bound is ((d H - 112). To the best of our knowledge, these are the first randomized RL algorithms for the MNL transition model that achieve statistical guarantees with constant-time computational cost per episode. Numerical experiments demonstrate the superior performance the proposed algorithms.
constant. Despite the simplicity and practi-
1 Introduction
Reinforcement learning (RL) is sequential decision makkin problem in which an agent tries to maximize its expected cumulative reward by interacting with an unknown environment over time.
Despite significant empirical progress in RI. algorithms for various applications 47 52
65
66 25
the theoretical understanding of RI algorithms had long been limited tabular methods 40
10 77 77), which explicitly enumerate the entire state and action spaces and learn the value (or the policy) for each state and action. Recently, there has been an increasing body of research in RL with function approximation to extend beyond the tabular problem setting. In particular, linear function approximation has served as a foundational model [43 22
On the other hand,
Equual contribution
Cooresponning author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the linear transition model assumption poses significant constraints: 1) the output of the function must be within [0, 1]. and 2) the sum of the probabilities for all possible next states must be exactly 1. These constraints make it challenging to apply RI. with linear function approximation to weal-world applications [35]. To overcome such challenges, there has been literature on RI with general function approximation 21 28 37 44 18]. Despite the guarantee of sample efficiency achieved by their algorithms, this accomplishment might be impeded by computational intractability or the necessity to rely on stronger assumptions. As result, the resulting methods may not be as general practical.
On the other hand, Hwang and Oh [35 introduce specific non- non-linear parametric MDPs called MNL- MDPs (Assumption] I where the transition probability of MDPs is given by an MNL model. They consider an upper confidence bound (UCB) approach to balance exploration and exploitation. Since it is costly or even intractable to compute UCB explicitly, randomized exploration methods such as Thompson Sampling (TS) are widely studied in RI. with linear function approximation as well as tabular MDPs. This is because, in various decision-making problems ranging from multi-armed bandits to RI., randomized exploration algorithms have been shown to perform better than UCB methods in empirical evaluations [16 57 64 49]. Furthermore, randomized exploration can be easily integrated with linear function approximation. This is because the value function in linear MDPs can be linearly parameterized, allowing perturbations of the estimator to directly control the perturbations of the value function. However, although there has been some literature aiming to propose randomized algorithms for general function classes [37 4 5 75), these methods do not discuss how to define the posterior distribution supported by the given function class and how to draw the optimistic sample from the posterior [4] 5 75,, they require stronger assumptions stochastic optimism (37. which is one of the most challenging elements in frequentist regret analysis. Thus, the design of a tractable randomized exploration RL algorithm and the feasibility of frequentist regret analysis for randomized exploration remain open challenges. Hence, the following question arises:
Can design provably efficient and tractable randomized algorithm for RL with MNL.funttinn approximation?
We answer the above question by proposing the first randomized algorithm, RRL-MNL, achieving O H vT) frequentist regret with constant-time computational cost per episode. RRL-MNL is not only the first algorithm with randomized exploration for MNL-MDPs, but also, to the best of our knowledge, it provides the first frequentist regret analysis for non-linear model-based algorithm with randomized exploration without assuming stochastic optimism 337
While RRL-MNL is statistically efficient, the current method used to analyze the regret of MNL function approximation introduces a problem-dependent constant x (Assumption 4 which reflects the level of non-linearity of the MNL transition model. This constant x originates from the use of generalized linear models (GIMS) for contextual bandit settings 26 51 45) and MNL. bandit settings [54] 17 555 The magnitude of the constant и can be exponentially small with respect to the size of the decision set, hence the regret bound scaling with x -1 could be prohibitively large in the worst case [23). Worse yet, the situation is even more challenging in RL, as in the worst case, x=1 can be much larger than in the case of bandits. To overcome the prohibitive dependence on k. algorithms based on new Bernstein-like inequalities and the self-concordant-lik property of the log-loss have been proposed for logistic bandits 23 3 24 and for MNL bandits [61 6,166,50 As an
extension of these works, the following fundamental question remains open:
Is possible for RL algorithms with funftintionn approximation to have a sharper dependence on the -depend- constant k??
For the above question, propose the second randomized algorithm referred to ORRL-MNL, which establishes a regret bound of ( H /T - dl H²) with constant-time computational cost per episode. We summarize our main contributions as follows:
We propose computationally tractable randomized algorithms for RL with MNL function approximation: RRL-MNL and ORRL-MNL. To the best of our knowledge, these are the first randomized model-based RL algorithms with MNL function approximation that achieve the frequentist regret bounds with constant- computational cost per episode.
We establish that RRL-MNL enjoys -d H VT) frequentist regret bound with constant- time computational cost per episode, where d is the dimension of the transition core, H is horizon length, T is the total number of rounds, and is a problem-dependent constant. We

---

derive the stochastic optimism of RRL-MNL, and to our knowledge, this is the first frequentist regret analysis for non non-linear model-basee algorithm with randomized exploration without assuming stochastic optimism.
To achieve a regret bound with improved dependence on K, we introduce ORRL-MNL, which constructs the optimistic randomized value functions by taking into account the effects the local gradient information for the MNI. transition model at each reachable state. We prove that ORRL-MN MNL enjoys an O H VT + n- dd H regret with constant-time computational cost per episode, significantly improving the regret of RRL-MNL without requiring prior knowledge of K.
We evaluate our algorithms on tabular MDPs and demonstrate the superior performance of our proposed algorithms compared to the existing state-of-the-art MNL-MDP algorithm (35). The experiments provide evidence that our proposed algorithms are both computationally and statistically efficient.
Related works on RL with function approximation and MNL contextual bandits are provided in Appendix A
Problem Setting
(he1 where S is the state space, AA is the action space, H is the horizon length of each episode, {P) the collection of probability distributions, and is the reward function. Every episodes start from the initial state 81 and for every step h E [H] := {1, H. in an episode, the learning agent interacts with the environment represented as M. The agent observes the state 8p. E S, chooses
We consider the episodic Markov decision processes (MDPs) denoted by M(S, H,,
an action E A. receives reward r(sa, ax) E [0, 1] and the next state 8h+1 is given by the transition probability distribution (- a,). Then this process is repeated throughout the episode. A policy S [H] + A is function that determines the action of the agent at state Sh, ie..
an (5),, h) == Th. (3)).
We define the value function of the policy æ. denoted by Vž (s), as the expected sum of re- wards under the policy ı until the end of the episode starting from 8h =, i.e., V (s)
H
Em
r(sw's Th (BW)) 8n = Similarly, we define the action-value function (s,a) =
r(s, a) + Es [VT (s')] We define an optimal policy ' to be a policy that achieves the highest possible value at every hs E S x [H]. We denote the optimal value function by (s) V (8) and the optimal action-value function by (5, = Q% (s, a). To simplify, we introduce the notation P3 are,
1 = (lleaa (8').. Recall that the Bellman equations
(s) = r(s (s, Qhss a) = r(s, (s.)., where (8) = (s) = and V/ (s) = max (s. for all s S. S.
The goal of the agent is to maximize the of rewards for K episodes. In other words, the goal is to minimize the cumulative regret of the policy π over K episodes where π = {m* 1K of policies R at k-th episode. The regret is defined as
=k=1 a collection
Regret, v. (K) = Σ V (sF)
where of is the initial state at the k-th episode.
2.1 Multinomial Logistic Markov Decision Processes (MNL-MDPs)
Even though a lot of provable RL algorithms for linear MDPs are proposed, there is a simple but fundamental problem with the linear transition model assumption on the linear MDPs. In other words, the output of a linear function approximating the transition model must be in [0, 1] and the probability of all possible following states must sum to exactly. Such restrictive assumption can affect the regret performances of algorithm suggested under the lincarity assumption. To resolve
3

---

these challenges, Hwang and Oh [55 propose setting of a multinomial logistic Markov decision processes (MNL-MDPs), where the state transition model is given by multinomial logistic model. We introduce the formal definition for MNL-MDPP follows:
Assumption 1 (MNL-MDPs [35). An MDP M,S, H. (P.)E=: is an MNL-MDP with a feature map 4p: S x A + IR for each E [M], there exists 0r E IR, such that for any (s, a) E S A and s' E Ss,a == {s' S : |,, # 0}, the state transition kernel of s' when an action a is taken at a state & is given by.
exp(yo(s, a, 8') TT))
Ps s, Eies,, explyp(s, 3) 0,,
(1)
We call each unknown vector 0% transition core. Furthermore, we denote the maximum cardinality of the set of reachable states as U, i.e., U. == I
Remark 1. While Hwang and Oh (35) assume a homogeneous transition kernel, we assume an inhomogeneous transition kernel, in which the probability varies depending the current time step even for the same state transition, which is a more general setting, Also, for notational simplicity, we denote the true transition kernel Ph. as p and the estimated transition kernel by O as Pa.
2.2 Assumptions
We introduce some standard regularity assumptions.
Assumption 2 (Boundedness). We assume ||,p(s, s')ll2 S Lp all (s,a,s) S x Ax S..a- and |10% ll2 S Lg for all h E [H]
Assumption (Known reward). We assume that the fearrff r known to the agent.
Assumption 4 Prroblem-depentee constant). Let (L) {0 R dd ||0|| S Lo). There exists R > such that for any as E x A and s', V,S Sa,a with + s,
inf Pols' Po OEBa(Lo)
Discussion of issumptions Assumption 2 common in the literature on RL with function approxi- mation [43 72 [33 37 (35] to make the regret bounds scale-free. Assumption is used to focus
the main challenge of model-based RL that learning about of the environment more difficult
than learning r. In the model-based RI. literature 77 9
72
81 35
the known reward assumption
is widely used. Assumption is typical in generalized linear contextual bandit [26] [1 23 3 24
and MNL contextual bandit Titerature [54 55
61
6
76 50
guarantee non-singular Fisher
information matrix.
Randomized Algorithm for MNL-MDPs having constant-time
computational cost
Previous work for MNL-MDPs 35 proposed a UCB-based exploration algorithm. Constructing UCB-based optimistic value function not only computationally intractable but also tends to overly optimistically estimate the true optimal value function. Additionally, their algorithm incurs increasing computation costs as episodes progress, as it requires all samples from the previous episode to estimate the transition core. In this section, we present novel model RL algorithm that incorporates randomized exploration and online parameter estimation for MNL-MDPs.
3.1 Algorithm: RRL-MNL
Online transition core estimation While Hwang and Oh 35 estimate the transition core using maximum likelihood estimation over all samples from previous episodes, we employ an efficient online parameter estimation method by exploiting the particular structure of the MNL transition model. The key insight that negative log-likelihood function for the MNL. model in each episode is strongly convex over bounded domain. This property allows us to utilize a variation of the online Newton step 30 3I, which inspired online algorithms for logistic bandits [74 and MNI. contextual bandits [55] Specifically, for (k, fi) E [K] x [H). we define the response variable y

---

Algorithm RRL-MNL (Randomized RL for MNL-MDPS)
1: Inputs: Episodic MDP M, Feature map yp S x A x 8 Rd, Number of episodes K,
K Regularization parameter X, Exploration variance (ox k=1 Sample size M, Problem-dependent constant
2: Initialize: 0 = 0g. iLA λIy for h E [H]
3: for episode 1,
do
4: Observe ot and sample i..dd noise vector Sk ~ W0a, for m E [M] and & E [H]
5: Set {-%(-) .) ne(m as described in
6: for horizon 1, 2..
7: Select a argmax (5h a) and observe s/+1
8: Update A AR, + Ex at, sf ( a S') and 0 as in
9: end for
end for
(h &' such that (s' 1 s') for s' E Sk.h := S Saa Then, y is sampled from the following multinomial distribution: yl multinomial(1, [Po; (s' s represents that yh is a single-triat trial sample. We define the per-episode loss Cx,A (0) as follows:
). where
Σ
(s') (
log (o |sh sh.a
S'E
Then, the estimated transition core for 0% is given by
0* argmin OE
1 ]
0
0 - + (0 - -0- V
12,,,
(2)
where f) can be initialized as any point in Ba(Lo) and Ag, the Gram matrix defined by
ARA = AL Σ Σ
plsh ans s (phhsh
3
I= e'ES.A
Stochastically optimistic value function First of all, we introduce the key challenges of regret analysis for randomized algorithms, explain how previous works have overcome these challenges, and then describe why the techniques from previous works cannot be applied MNL-MDPs. Ensuring that the estimated value function is optimistic with sufficient frequency is crucial challenge in analyzing the frequentist regret of randomized algorithms. A common way to promote sufficient exploration in randomized algorithms is by perturbing the estimated value function or by performing posterior sampling in the transition model class. Frequentist regret analysis randomized exploration in an RL setting has been conducted for tabular [59] 62 60 67], linear MDPs [73 37 and general function classes 37
75). In the case of linear MDPs
B 37. since the property that the
action-value function is linear in the feature map allows perturbing the estimated parameter directly to control the perturbation of the estimated value function. Also, even though Ishfaq al. (37] presented randomized algorithm for the general function class using eluder dimension, they assume stochastic optimism cuniicconcettaation) which in fact one of the most challenging aspects of frequentist analysis. Other posterior sampling algorithms in RI for the general function class such as 4 7,7 except for very limited examples, do not discuss how to define the posterior distribution supported by the given function class and how to draw the optimistic sample from the posterior. That is why even after there exists a so-called general function f
class-based result, often the case that results in specific parametric models are still needed.
Note that in episodic RL, the perturbed estimated value functions are propagated back through horizontal steps, requiring careful adjustment of the perturbation scheme to maintain sufficient probability of optimism without decaying too quickly with the horizon. For example, the probability of the estimated value function being optimistic at horizon h is denoted as p. this would result in the probability that the estimated value function in the initial state optimistic being on the order of p² implying that the regret increase exponentially with the length of the horizon H.
5

---

Additionally, the non- non-linearity and substitution effect of the next state transition in the MNL-MDPs make applying the existing TS techniques infeasible to guarantee optimism in MNL-MDPs with sufficient frequency. Instead, we design the stochastically optimistic value function by exploiting the structure of the MNL. transition model. In other words, the prediction error of MNL. transition model (Definition 1 can be bounded by the weighted norm of the dominant feature & (Lemma D Based on such dominant feature, we perturb the estimated value function by injecting Gaussian noise whose variance is proportional to the inverse of the Gram matrix to encourage the perturbation with higher variance in less explored directions. To guarantee the optimism with fixed probability, we adapt optimistic sampling technique 7 [54 37 36). For each E [M], sample i.i.d. Gaussian noise vector < ~ (Oaa,, A where σ% is an exploration parameter, and add the most optimistic inner product value maxme[M] P. a) elm) to the estimated value function. To summarize for any (s, a) E S x A, set Q+++ (s, a) = 0 and for h [H].
()(s,)) = min (((s.0)
+
Σ
Por (5' I
max (s, a) Ek,h H H mE[M]
(4)
s'ES,,a
(088 a, 8) for 8 Based on these stochastically optimistic value function, the agent plays a greedy action at = argmax, (h a'). We layout the procedure in Algorithm Note that RRL-MNL only requires constant- time computational cost and storage cost per episode, as it does not require storing all samples from previous episodes, and the Gram matrix Ak.h can be updated incrementally.
where (s) = max (', and (s,))
argmax E.., [|yp(s, a, s')ll
Remark 2.
3.2 Regret bound of RRL-MNLL
We present the regret upper bound of RRL- The complete proof is deferred to Appendix
C
Theorem 1 (Regret Bound of RRL-MNL). Suppose that Assumption
hold. For any 0 < 8 < +
2
we set the input parameters in Algorithm as X = Lig, Tk O(Hvd) and M [1 log (1)
log /
where & is the normal CDF, then with probability at least 1 - 5, the cumulative regret of the RNL
policy π. is upper- bounded as follows:
Regret, , (K) = 5 (n-
where T KH is the total number of steps.
Discussion of Theorem 1 To our best knowledge, this is the first result to provide a frequentist regret bound for the MNL-MDPs. Among the previous RL algorithms using function approxima- tion, the most comparable techniques to our method are model-free algorithms with randomized exploration 73 37.. To guarantee stochastic optimism, Zanette et al. [3 established a lower bound on the difference between the estimated value and the optimal value by the summation of linear terms with respect to the average feature (Lemma F.1 in 73)). This property is achievable due the linear expression of the value function in linear MDPs Instead, we established a lower bound on the difference between value functions by the summation of the Bellman errors (Definition [1] along the sample path obtained through the optimal policy (Lemma Z Hence, our analysis significantly differs from that of Zanette et al. 73 since the value function in MNL-MDPs no longer linearly parametrized, and there is no closed-form expression for it.
Compared to 37,. they also used an optimistic sampling technique; however, our theoretical sampling size M- = Olog H) is much tighter than that of [37], i.c., ((d) for the linear function class, (log(T)(S]]AA) for the general function class. While Ishfaq et al. (37] extend the results of the linear function class to general function class under the assumption of stochastic optimism (Assumption C in (77), we provide the frequentist regret analysis for a non-linear model-based algorithm with randomized exploration without assuming stochastic optimism.
Compared to the optimistic exploration algorithm for MNL-MDPs 35 our randomized exploration requires a more involved proof technique to ensure that the perturbation of the estimated value function has enough variance to maintain optimism with sufficient frequency (Lemma 6). As result,

---

the established regret of RRL-MNL differs by a factor of vd. which aligns with the difference in the
existing bounds of linear bandits between TS-based algorithm [2] and a UCB-based algorithm M. Additionally, we achieve statistical efficiency for the inhomogeneous fransition model, which is more general setting than that of Hwang and Oh [35]. Our computation cost per episode is (1))
while the computation cost per episode of Hwang and Oh 335 is ((K).
Proof Sketch of Theorem |
We provide the proof sketch of Theorem | into the estimation part and the pessimism part, we have
By decomposing the regret
E (++)
V (s4).
Pessimism
Estimation
We bound these two parts separately. For the estimation part, for each & E [K], E [H], we first
show that the online estimated transition core e 2 concentrates around the unknown transition core parameter 0% with high probability (Lemma 1 Then, we show that the prediction error induced by the estimated transition core can be bounded by the weighted norm of the dominant feature f multiplied by the confidence radius of the estimated transition core (Lemma 4 The bounded prediction error, together with the concentration of Gaussian noise, implies the desired bound on the estimation part (Lemma [O]. For the pessimism part, we first show that the stochastically optimistic value function V is optimistic than the true optimal value function V with sufficient frequency (Lemma 6. In the next step, show that the pessimism part is upper bounded by bound of the estimation part times the inverse probability of being optimistic (Lemma IT]. Combining all the results, we can conclude the proof. Refer Appendix [for detailed proofs.
Statistically Improved Algorithm for MNL-MDPs
Although RRL-MNL is provably efficient and achieves constant-time computational cost per episode, the current analysis makes its regret bound scale with x x- Recall that the problem-dependent indicaats the curvature of the MNL function, i.c., how difficult is required to ensure the non-singular Fisher
constant introduced in it is to learn the true transition core parameter. information matrix, hence is typically used in GLM or MNL bandit algorithms that use the maximum likelihood estimator. As introduced in Faury et al. (23 K- can be exponentially large in the worst case. The appearance of in existing bounds originates in the connection between the difference of estimators and the difference gradients of negative ligllikel,hoo, usually denoted as G in Filippi al. (26). Without considering local information all, using loose lower bound for G incurs x-1 in regret bound (see Section 4. I in Agrawal et al. (6). Recently, improved dependence on k has been achieved in bandit literature 23 61 76 50] through the use of generalization of the Bernstein-lik tail inequality (23 and the self relf--ooccrdaattllic property of the log loss [II]. However, direct adaptation of the MNL bandit technique would result in sub-optimal dependence on the assortment size in MNL bandit, which corresponds to the size of the set of reachable states, such as 4. In this section, we introduce a new randomized algorithm for MNL-MDPs, equipped with a tight online parameter estimation and feature centralization technique that achieves regret bound with improved dependence on and U.
4.1 Algorithms: ORRL-MNL
Tight online transition core estimation Zhang and Sugiyama (76) presented jointly efficient UCB-based MNL contextual bandit algorithm using online mirror descent algorithm. Adapting the update rule from (76,, the estimated transition core run by the online mirror descent is given by
1 argmin - 0 0% (EBa(T.o)
B
2 B
+ O TVV (0))
(5)
h
21
where 0) can be initialized any point in Ba(Lo), rj is step size, and B is defined as
BA, := Be, + 1 =V B := Ala
Σ v (
(6)
7

---

Algorithm 2 ORRL MNL (Optimistic Randomized RL for MNL-MDPs)
Inputs: Episodic MDP M, Feature map 40 S A + Fd, Number of episodes K, K
Regularization parameter X, Exploration variance {Øk k= [0 Confidence radius {5x k= Sample
size M, Step size 7
2: Initialize: 0, - 0g, B AIa for all E [M]
3: for episode k 1,
K do
4: Observe st and sample i..dd noise vector <(m)) Ni(O, B for m E [M] and h e [H]
5: Set {+) hE[H] as described in (
6: for horizon h 1,2 H do
7: Select / argmax (s h a) and observe s/+1
8: Update B = BEN + 2 (0) and t% as in (5)
9: Update B Ba, + (0,
10: end for
11:
end for
Note that the MNL model in Zhang and Sugiyama (76 operates in a multiple-paramene setting, where there are multiple unknown choice parameters and one given context feature. In contrast, our MNL. model operates in a single-parumeter setting, where there is one unknown transition core and features for up to L reachable states. This difference results in variations in applying the self-concordant-like property of the log-loss for the MNL model. For instance, Zhang and Sugiyama
(76 utilized the fact that the log-loss for the multiple parameter MNL model is /6-self-coom concoo--onnrd like (Lemma 2 in Zhang and Sugiyama (76). On the other hand, Lee and Oh [50] revisit the self-comcordant-lik property and demonstrate that the log-loss of the single-parameter MNL model is 3v 3-2--elffcoon lessseff-cocordant--iee (Proposition B.1 in Lee and Oh [50). This results in a concentration
bound that is independent of и and U1 introduced in Lemma 12
Remark 3. Note that the online estimated parameters 0 ② and 0 (5) do not aim to minimize
the sum of negative log-likelihoods, E ( (0). Instead, we show that the online estimated parameter concentrates around the unknown transition core 0% with high probability (Lemmal & T2). This online update approach allows estimate the transition core with constant-time computational cost per episode, as the agent does not need to store all samples from previous episodes.
Optimistic randomized value function To achieve improved dependence on K, a crucial point is to utilize the local gradient information of MNL transition probabilities for cach reachable state when constructing the Gram matrix. In MNL bandit problems [61 this can be accomplished by substituting the Hessian of the negative log-likeldhood with the Gram matrix using global gradient information к. However, there are fundamental differences between the settings in Perivier and
Goyal 611. Zhang and Sugiyama 766 and ours. Perivier and Goyal [6 address the case where the reward for each product is uniform (i.e., all products have a reward of 1), and the reward for not selecting product from the given assortment (also known the outside option) is 0. On the other hand, Zhang and Sugiyama [76] deal with non-uniform rewards where the reward for each product may vary; however, the rewards for individual products known priori to the agent. In contrast, in MNL-MDPs, the value for each reachable state may vary (non-uniform) and is not known beforehand. Due to these differences, the analysis techniques in MNL bandits [6] 76 cannot be directly applied to our setting. Instead, we adapt the feature centralization technique [50]. Then, the Hessian of the per-round loss fu (0) is expressed in terms of the centralized feature as follows:
(0)
Σ Pols' sts pps o s': d(:0) ((;))) ST;
s'ESu.
where ass.a,s';00 = (pss, a, s') Po (o 3)] is the centralized feature by 0. For more details, please refer to Appendix D.2
Now we introduce the optimistic randomized value function (+.)) for ORRL-MNL. The key point that when perturbing the estimated value function, we use the centralized feature by the estimated
8

---

transition parameter 0% For any (s.a) ESSX A, set (H41(s,a) a) 0 and for each h [H],
: (s) = min { r(s,a)+ Σ
rand Pa a) ( + k,h (s, a) H
s'ES.
where (s)= max.EA (h, and (i,n((s, is the randomized bonus term defined by
(s,a) == k,h
rand
Σ s'ES.,a
(s (s' 8, a, T Eh + +3H max s'ES,,
11yp(s, a, s')l B,
Here we sample i.i.d. Gaussian noise {m)) ~ (N(,,, B for each m E [M] and set C em(s')
Sk. where m(s')= : argmaxmE|Mi (0,s, a, s T Sk.b is the most optimistic sampling index for a reachable state s'. Based these optimistic randomized value function, each episode the agent plays greedy action with respect to Ø as summarized in Algorithm
Remark 4. Note that the second term in the randomized bonus always has a positive value, but it rapidly decreases episode proceeds. While due the randomness of &. the randomized bonus grand itself cannot be guaranteed to always have a positive value. Consequently, the constructed kih
value function 0 ()) can be optimistic or pessimistic. However, as shown Lemma 18 optimistic
sampling technique ensures that the optimistic randomized value function Q has at least a constant probubility of being optimistic than the true optimal value function.
Remark 5. As with RRL-MNL, since the transition core is estimated in an online manner and the Gram matrices with local gradient information BR, and B updated incrementally, ORRL-MNL also requires constant- -time computational cost and storage cost per-episode. Although ORRL-MNL requires an additional O(U) compulation cost for feature centralization, the computation complexity order is the same as that of RRL-MNL because it also needs to go over reachable states to calculate the dominant feature &p. which also incurs a (lL) computation cost. On the other hand, ORRL-MNL does not require prior knowledge of k and achieves regret with better dependence on
4.2 Regret Bound of ORRL-MNL
We present the regret upper bound of ORRL MML. The complete proof is deferred to Appendix D
Theorem 2 (Regret Bound of ORRL-MNL). Suppose that Assumption ! hold. For any 0
6
+ (1-1) if we the impul parameters in Algorithm 2 as X HBk, M [11 least 8, the cumulative regret of the ORRL-MNL policy is upper- upper-bounded bounded as follows:
Br.
log(H())
log 4(1 1, and n (log()), then with probability
Regret, , (K) = 5 ( (17
where T KH is the total number of time steps.
Dicussion of Theorem 2 Theorem eestablshes that the leading term in the regret bound does not suffer from the problem-dependdet constant x= and the second term of the regret bound is independent of the size of set of reachable states. To the extent of our knowledge, this is the first algorithm that provides a frequentist regret guarantee with improved dependence on = in MNL.- MDPs. Compared RRLM the technical challenge lies ensuring the stochastic optimism of the estimated value for ORRL-MNL. Note that the prediction error (Definition I] for ORRL-MNL is characterized by two components: one related to the gradient information of the MNL transition model at each reachable state, and the other related to the dominant feature with respect to the Gram matrix B (Lemma 16p. Hence, the probability of the Bellman error at each horizon, when following the optimal policy, being negative can depend on the size of the reachable states. This implies that the probability stochastic optimism can be exponentially small, not only in the horizon H but also in the size of the reachable states U. However, as shown in Lemma [8] this challenge has been overcome by using a sample size M that logarithmically increases with U, effectively addressing the issue.

---

Epicodi: Returnss
The Number Episedes
The Number of Episodes
Algerthmm
(a) S
H 12
(b) 8, 24
(c) Runtime for 1,000 episodes
Figure 1: Riverswim experiment results
Proof Sketch of Theorem The overall proof pipeline for Theorem is similar to that of Theorem The main differences lie in the concentration of the estimated transition core (Lemma D.2). the bound the prediction eтror (Lemma D.2 and the stochastic optimism (Lemma 18 Please refer to Appendix D for detailed proofs.
Optimistic exploration extension In general, since TS IS-based randomized exploration requires a more rigorous proof technique than UCB-based algorithms, our technical ingredients enable the use of optimistic exploration in straightforward manner. We introduce UCRL-MNL+ (Algorithm 3 in the Appendix [ an optimism-based algorithm for MNL-MDPs. It is both computationally and statistically efficient compared UCRL-MNL [3), achieving the rightest regret bound for MNL- MDPs.
Corollary UCRL-MNL+ (Algorithm has 0(dH3/2 xoxxxxooo ( regret with high probability.
Numerical Experiments
We perform numerical evaluation on variant of RiverSwim [88] to demonstrate practicality of our proposed algorithms. We compare our algorithms (RRL-MNL, ORRL-MNU UCRL-MNL+) with the sfate-of-the-art UCRL-MNL [35] for MNL-MDPs. For each configuration, we report the averaged results over 10 independent runs. Figure Ia and lb show the episodic return of each algorithm, which the sum of all the rewards obtained in one episode. First, our proposed algorithms (RRL-MNL, MNL, UCRL-MNL+) outperform UCRL-MNI [35] for both cases of [S] 4, 8. Second, ORRL-MNL and MMRL-MNL+ reach the optimal values quickly compared to the other algorithms, demonstrating improved statistical efficiency. Figure Ic illustrates the comparison in running time of the algorithms for the first 1,000 episodes. Our proposed algorithms are at least 50 times faster than UCRL-MNL. These differences become more pronounced as the episodes progress because our algorithms have constant computation cost, whereas the computation cost of UCRL-MNI -NNL increases over time.
Conclusions
We propose randomized algorithms with provable efficiency and constant-time computational cost for MNL-MDPs. For the first algorithm, RRL-MNL, we use an optimistic sampling technique to ensure the stochastic optimism of the estimated value functions and provide the frequentist regret analysis. This is the first frequentist regret analysis for a non-linear model-based algorithm with randomized exploration without assuming stochastic optimism. To achieve statistically improved regret bound, we propose ORRL-MNL by constructing the optimistic randomized value function using the effects of the local gradient of the MNL transition model equipped with the centralized feature, As result, we achieve frequentist regret guarantee with improved dependence on & in RL with the MNL transition model, which significant contribution. The effectiveness and practicality of our methods are supported by numerical experiments.
10

---

Acknowledgements
We sincerely thank the anonymous reviewers for their constructive feedback. This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government (No. CICCIIII,,,,,,9, 2022R 11221A444 I4A 1030579, and RS-2023-00222633 and by Al-Bio Research Grant through Seoul National University.
References
[1] Yasin abbasi-Yadkorf Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312-233 2320, 2011.
[2] Mare Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Reseurch, pages 176-184. PMLR, PMLR, 20-22 Apr 2017.
[3] Marc Abeille, Louis Faury, and Clément Calauzènes. Instance-wise minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699. PMLR, 2021.
[4] Alekh Agarwal and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. Advances in Neural Information Processing Systems, 35: 35284-35297, 2022.
[5] Alekh Agarwal and Tong Zhang. Non-linear reinforcement learning large action spaces: Structural conditions and sample-efficiency of posterior sampling. In Conference on Learning Theory, pages 2716-2814. PMLR, 2022.
[6] Priyank Agrawal, Theja Tulabandhula, and Vashist Avadhanula. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Research, 2023.
[7] Shipra Agrawal and Randy Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pages 11841 194, 2017.
[8] Sanae Amani and Christos Thrampoulidis. Ueb-based algorithms for multinomial logistic regression bandits. Advances in Neural Information Processing Systems, 34:2913-299 1-22444, 2021.
[9] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- foreement learning with value-targeted regression. International Conference on Machine Learning, pages 463-47 4744. PMLR, 2020.
[10] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[11] Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4(2):384 414, 2010.
[12] Peter L. Bartleu, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexitees The Annals of Statistics, 2005.
[13] Steven Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1):33-57, 1996.
[14] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 2283-1294, PMLR, 2020.
[15] Nicolo Campolongo and Francesco Orabona. Temporal variability implicit online learning. Advances in neural information processing systems, 33:12377-123877 2020.

---

[16] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling, Advances in neural information processing systems. 24, 2011.
[17] Xi Chen, Yining Wang, and Yuan Zhou. Dynamic assortment optimization with changing contextual information. Journal of machine learning research, 2020.
[18] Zixiang Chen, Chris Junchi Li, Huizhuo Yuan, Quanquan Gu, and Michael Jordan. A general framework for sample-efficient function approximation in reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
[19] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient pac rl with rich observations. In Advances in Neural Information Processing Systems, volume 31, 2018.
[20] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. International Conference Machine Learning, pages 1665-1674. PMLR, 2019.
[21] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-2836. PMLR, 2021.
[22] Simon S. Du, Sham M. Kakade, Ruosong Wang, and Lin F. Yang. Is good representation sufficient for sample efficient reinforcement learning? In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[23] Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference Machine Learning, pages 0052-3060. PMLR, 2020.
[24] Louis Faury, Mare Abeille, Swang-Sung Jun, and Clément Calauzènes. Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 546-580. PMLR, 2022.
[25] Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszez, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-53 2022.
[26] Sarah Filippi, Olivier Cappé. Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Proceedings of the 23rd International Conference on Neural Information Processing Systems Volume 1, NIPS' 10, page 386-594, Red Hook, NY, USA, 2010. Curran Associates Inc
[27] Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Logistic regression: The importance of being improper. In Conference On Learning Theory, pages 167-208. PMLR, 2018.
[28] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:21 13487, 2021.
[29] David Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100-118, 1975.
[30] Flad Hazan, Amit Agarwal, and Satyen Kale, Logarithmic regret algorithms for online convex optimization. Machine Learning, 19(2):169-192 2007.
[31] Elad Hazan, Tomer Koren, and Kfr Y Levy. Logistic regression: Tight bounds for stochastic and online optimization. In Conference Learning Theory, pages 197-209. PMLR, 2014.
[32] Elad Hazan et Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):17-3355, 2016.
12

---

[33] Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171-4180. PMLR, 2021.
[34] Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforce- ment learning for linear markov decision processes. In International Conference on Machine Learning, pages 12790-12822. PMLR, 2023.
[35] Taehyun Hwang and Min-hwan Oh. Model-based reinforcement learning with multinomial logistic function approximation. In Proceedings of the AAAI conference artificial intelligence, pages 7971-7979, 2023.
[36] Taehyun Hwang, Kyuwook Chai, and Min-Hwan Oh. Combinatorial neural bandits. In Proceedings of the 40th International Conference Machine Learning. PMLR, 2023.
[37] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning, volume 139, pages 4607-4616. PMLR, PMLR, 2021.
[38] Haque Ishfaq, Qingfeng Lan, Pan Xu, A. Rupam Mahmood, Doina Precup, Anima Anandkumar, and Kamyar Azizzadenesheli. Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo. In The Twelfth International Conference on Learning Representations, 2024. URL https::/openrreiieee httpss//ppaareeeeeeeeerrrrrrrrra /om
net/forum
[39] Haque Ishfaq, Yixin Tan, Yu Yang, Qingfeng Lan, Jianfeng Lu, A Rupam Mahmood, Doina Precup, and Pan Xu. More efficient randomized exploration for reinforcement learning via approximate sampling. Reinforcement Learning Journal, 3(1), 2024.
[40] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[41] Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pages 666-686. PMLR, 2020.
[42] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning, pages 1703-1713. PMLR, 2017.
[43] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[44] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 1113344661113 2021.
[45] Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable gen- eralized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
[46] Yeoneung Kim, Insoon Yang, and Kwang- Jun. Improved regret analysis for variance- adaptive linear bandits and horizon-fin free linear mixture mdps. Advances in Neural Information Processing Systems, 1060-1111 2022.
[47] Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(1 1)) 1238-1244, 2013.
[48] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29:1840-1888 2016.
[49] Branislay Kveton, Csaba Szepesvári, Mohammad Ghavanzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. In Uncertainty in Artificial Intelligence, pages 530-540. PMLR, 2020.
13

---

[50] Joongkyu Lee and Min-hwan Oh. Nearly minimax optimal regret for multinomial logistic bandit. arXiv preprint arXiv:2405.09831, 2024.
[51] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-20110 2071-2080. PMLR, 2017.
[52] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland. Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533, 2015,
[53] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of rein- forcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010-2020. PMLR, 2020.
[54] Min-hwan Oh and Garud Iyengar. Thompson sampling for multinomial logit contextual bandits. Advances in Neural Information Processing Systems, 52:3151-3161, 2019.
[55] Min-hwan Oh and Garud lyengar. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9205-99099 2213-9213, 2021.
[56] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, pages 1466-1474, 2014.
[57] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pages 2701-2710. PMLR, 2017.
[58] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
[59] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR, 2016.
[60] Aldo Pacchiano, Philip Ball, Jack Parker-Holder, Krzysztof Choromanski, and Stephen Roberts. Towards tractable optimism in model- -oseel reinforcement learning. In Uncertainty in Artificial Intelligence, pages 1413-1423, PMLR, 2021.
[61] Noemie Perivier and Vineet Goyal. Dynamic pricing and assortment under contextual mnl demand. Advances in Neural Information Processing Systems, 35:3461-3474, 2022.
[62] Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019.
[63] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pages 2256-2264, 2013.
[64] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[65] David Silver, Julian Schritwiiserr, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 55007676):3544-35) 2017.
[66] David Silver, Thomas Hubert, Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, (22(6419):1100-111 144, 2018
[67] Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees. Advances in Neural Information Processing Systems, 15:10777 2022.
14

---

[68] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
[69] Yining Wang, Ruosong Wang, Simon Shaolei Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. In 9th International Conference on Learning Representations. ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[70] Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
[71] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[72] Lin Yang and Mengdi Wang. Reinforcement learning feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pages 10746-10756. PMLR, 2020.
[73] Andrea Zanette, David Brandfonbrener, Emma Brunskill, Mattco Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020.
[74] Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-Hua Zhou. Online stochastic linear optimization under one-bit feedback. In International Conference on Machine Learning, pages 392-401, PMLR, 2016.
[75] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-857 2022.
[76] Yu-Jie Zhang and Masashi Sugiyama. Online (multinomial) logistic bandit: Improved regret and constant computation cost. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[77] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learn- ingvia reference-advanttaen decomposition. In Advances in Neural Information Processing Systems, volume 33, pages 15198-15207, 2020.
[78] Zihan Zhang, Jiaqi Yang, Xiangyang Ji, and Simon S Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34:4342 4355, 2021.
[79] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Model-free reinforcement learning: from clipped pseudo-regret to sample complexity. In International Conference on Machine Learning, pages 12653-12662. PMLR, 2021.
[80] Dongruo Zhou and Quanquan Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing xystems, 35:36337-36349, 2022.
[81] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576 PMLR, 2021.
[82] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12802, PMLR, 2021.
15

---

Contents of Appendix
Related Work
16
B Notations & Definitions
18
Detailed Regret Analysis for RRL-MNL (Theorem 1)
22
C.I Concentration of Estimated Transition Core 0%
23
C.2 Bound on Prediction Error
32
C.3 Good Events with High Probability
33
C.4 Stochastic Optimism
33
C.5 Bound on Estimation Part
36
C.6 Bound on Pessimism Part
38
C.7 Regret Bound of RRL-MNL
41
Detailed Regret Analysis for ORRL-MNL (Theorem 2)
42
D.1 Concentration of Estimated Transition Core 0
42
D.2 Bound on Prediction Error
50
D.3 Good Events with High Probability
55
D.4 Stochastic Optimism
55
D.5 Bound on Estimation Part
57
D.6 Bound on Pessimism Part
66
D.7 Regret Bound of ORRL-MNL.
67
Optimistic Exploration Extension
67
E.1 Optimism
69
Experiment Details
70
G Auxiliary Lemmas
70
Limitations
72
A Related Work
There has been a growing interest in studies that extend beyond tabular MDPs and focus on function approximation methods with provable guarantees 42
RL with linear function approximation
7I 43 733 53
14
9
68
70
g2
37 35 38). In particular. for minimizing regret in
linear MDPs, Jin et al.
propose an optimistic variant of the Least-Squares Value Iteration
(LSVVI algorithm
13 59 under the assumption that the transition model and reward function of
the MDPs are linear function of d-dimensional feature mapping and they guarantee Õ(d H 3 VT) regret. Zanette et al. [73] propose randomized LSVI algorithm that incorporates exploration by perturbing the least-square approximation of the action-value function, and this algorithm guarantees ((d regret. Ishfaq et al. [37] propose a variant of the randomized LSVI algorithm that combines optimism and TS by perturbing the training data with i.i.d. scalar noise, achieving regret bound of (dd H VT). Similarly, Ishfaq al. 38 introduce randomized RL algorithm that employs Langevin Monte Carlo (LMC) to approximate the posterior distribution of the action-valuc
16

---

Table I: This table compares the problem settings, online update, performance of the this paper with those of other methods in provable RL with function approximation. For computation cost, we only keep the dependence the number of episode K.
Algorithm
Model-bused
Transition model
Reward
Computation cost
Regret o
LSVI-UCB [4
X
Linear
Linear
[(K)
OPT-RLSVI
X
Linear
Linear
((K)
((F1PTT)
LSVI-PHE 37
X
Linear
Linear
O(K)
UC-NatrixRL 7P
V
Linear
Known
O(K)
((d3112/T)
UCRL-VIR
V
Linear mixture
Known
((K)
Ö(dHtVT)
UCRL-MNL (35
MNL
Known
((K)
06.-1HHiTT
RRI-MNL (this work)
/
MNL
Known
O(1)
O(c''iHHVT
ORRL-XNL (this work)
MNL
Known
O(1)
UCRL-MNL+ (this work)
/
MNL
Known
O(1) ÖdHBVTT
function, also ensuring regret bound of Odd (HVVT) Also, there have been studies on model- based methods with function approximation linear MDPs, such as Yang and Wang [22, which assume that the transition probability kernel is a bilinear model parametrized by matrix and propose algorithm with an upper bound of Õ H2VT) for regret. He al.
34 propose an
algorithm achieving nearly minimax optimal regret Old TT). Jia al. consider specific type of MDPs called linear mixture MDPs in which the transition probability kernel is a linear combination of different basis kernels. This model encompasses various types of MDPs studied previously Modi et al. [53), Yang and Wang (72.. For this model, Jia et al. [4] propose UCB-basee RL algorithm with value-targeted model parameter estimation that guarantees upper bound of Ō OdH' 3 /T) for regret. The same linear mixture MDPs have been used in other studies such as Ayoub et al. 19. Zhou al. 88 82 Specifically, in Zhou al. [1], variant of the method proposed by Jia et al. [41] suggested and proved that the algorithm guarantees an upper bound of Ö(dH /T) regret with a matching lower bound of 2ddH (T) for linear mixture MDPs. More recently, there are also works achieving horizon-free regret bounds for linear mixture MDPs 78 46 80
RL with non-linear function approximation Studies have been conducted on extending function approximation beyond linear models. Ayoub et al. 9 Wang et al. [68]. Ishfaq et al. (37 provide upper bound for regret based on eluder dimension sample-efficient methods with more "general" function approximation [48] 42
63 Also, there has been effort to develop
19
21
28 37
75 18 39 However, these attempts may have been hindered by the difficulty of solving
computationally intractable problems [48] 42 21 28 44 [8), the necessity of relying on stronger
how define the posterior distribution supported by given function class and how to draw the optimistic sample from the posterior [4] 5 75). That why even after there exists a so-called "general function -based result, is often the case that the results in specific parametric models are still needed. Despite the large number of studies on RL with linear function approximation, there is limited research on extending beyond linear models to other parametric models. Wang et al. (69 use generalized linear function approximation, where the Bellman backup of any value function is assumed be a generalized linear function of feature mapping. Hwang and Oh (35] discuss the limitations of linear function approximation and propose a UCB-based algorithm for MNL transition model in feature space achieving (dH vT). Ishfaq et al. 33 present TS- based RL algorithms that utilize approximate samplers, such as LMC or Underdamped LMC, enhance the implementation and computational tractability of TS for RL with general function classes.
assumptions 220 37), or the lack of discussion
Contextual bandits Faury et al. 23 first provide a UCB-based algorithm with r-independent regret for binary logistic bandit and Abeille et al. 3 present UCB & TS based algorithms achieving nearly minimax optimal regret for the same setting. Faury et al. (24 propose jointly efficient UCB-based algorithm that achieve k-independent regret bound with Olog t) computation cost. In the context of MNL model, Oh and Iyengar [54] employ TS approach, while Oh and Iyengar [55] incorporate a combination of UCB exploration and online parameter updates for MNL bandits. Both of the methods have (V= regret. Amani and Thrampoulidis g propose an optimistic algorithm with better dependence
Agrawal et al. 66) design UCB-based algorithm with
17

---

((VT) regret bound without in its leading term, and Perivier and Goyal [6] establish O ( TT/// regret for the uniform reward setting. Zhang and Sugiyama [76] develop jointly efficient UCB-based algorithm for non-uniform MNI. bandit problem. Lee and Oh (50) propose nearly minimax optimal MNL bandit algorithm for both uniform and non-uniform reward structures.
B Notations & Definitions
In this section, we formally summarize some definitions and notations used to analyze the proposed algorithm.
Inhomogeneous MNL transition model
For [H] the probability state transition to s' Sana when an action a is taken at state given by
Pa s.,) == Po (s' s,a) = csp(p((s,,s''T
Eses,. (xp((o(s,a,3) 0%)
The estimated transition probability parameterized by 0 is denoted as
x TQ)
Po(s' (8,0) = Eves... 8)
Feature vector
We abbreviate the feature vector as follows:
Ps..s == (psss s') for (s, E S Ax Ss..
PkA = s at, for (k, E [K] x [ and s' E Sx,b = St
PR,A a) as,, a) for argmax (p((s, a, s') Arhh
.'ES,,
(p((0, 8)]] Ps ( = ( a, , = 8') - Po..,.(1...))
Pk.h.or (0) p a 0):
Response variable & per-episode loss
The response variable v given by
v = (s'(s'))ssss, where v/(('))= 16s/411 = 8)) for s' E Sk.h
The per-episode loss la, (0) is given by
(0) = Σ
Po(s' |s a
s' S'.
Gk,(()) = (0)
Σ
(Pols') st,, att - (5")) ka.her
S'E
Ha)x(0)= = (0))
Σ Pols' 1 * ( )k. P Pk
Σ Σ Po(s' Po si Phn
s'ESu.N
e'ESe, SES.,
18

---

Regularity constants
H Horizon length
K Episode number
T KH Total number of interactions
Lip m2-morm upper bound of (p(s,, a, s), i.e., |1,0(s, a, s'2l2 S Lu
Lo f--nrrm upper bound of 0% i.e., |0 S Lo:
Problem-dependent constant such that inf @EBu(Le)
Pols' s, (o s,
U : Maximum cardinality of the set of reachable states, i.e., U = max Sz.al
Estimated transition core
The estimated transition core for RRL-MNL is given by
1
arginin
0
0% k--ll I A + (0 00-0% VVa--nn000
2
(LB)
and the estimated transition for ORRL MNL is given by
g++t h
argmin (EB,(Lo)
0 0
+ + ((.)
2n
B2,
Gram matrices
The Gram matrix with global gradient information i: is given by
k-1
A XL
Σ
Σ
p(sh oh s' (s))p(s s')
s'ES.A
The Gram matrices with local gradient information are given by
k-1
B = BR + 7 ( (0%) and B = Ala + Σ
Confidence radius
For some absolute constants C3. Ce > 0,
ag ar (6)
8d K
L
16)
(1+ 2 log, kl Lo Lol)k² k2 + 222 + 2X13
log
1+
+
+
log
dA
3
Ök 1/2 11/22//2)/
HV1 + 2h 8
h: 1+ dx )x)) + AL
8x = (5) = Coy logul Allo(((k)) + log(U(k) log
+ ddlog
log log(k()))
2h (8) C
Filtration
For arbitrary X, denote the E-algebra generated by X E(X). Then define the following filtrations
Fs = Σ (() H} (m)) lick S
= E 1| 1 U ( (
(m))
19

---

Pseudo-noise
For RRL-MNL, the psiue is sampled
slm (0 of k,))
and for ORRL-MNL. the pseudo-noise is sampled as
(m) kn (O,, of
for M times independently.
Estimated value functions
The stochastically optimistic value function for RRL-MNL is defined as follows:
Qh+1 =0, 0,
(s) min (((,,a)
Por Po s,a) + (s,
1l T Sk
((m)
for h e [M]
mE(Ad]
s'ES.,a
The optimistic randomized value function for ORRL-MI -NL is defined as follows: 0)+ =0
(h),)))= = min (((sa)+ + Σ
Por | (i)))() + vs
(s, a) H for h e [M],
s'ES,,a
where
raand (s,a) =
Σ
P 8, (1) Th + 3H BC max 1|s(,,, (e(s,,,,')113 8')l e'SS.
Vi.h
S'ES,,a
mmle)) Sh = Sk. for m(s) wrgmaxp(ss.au Ek. T
mE|M]
Prediction error & Bellman error
Definition 1 (Prediction error Bellman error). For any (s, S x A and (k, [K] [H].
we define the prediction error about 0% as
a) = Σ (Por (, (o1(8,)))) Vh+i(())
8'ES.a
Also we define the Bellman error as follows:
(s) a(s,a) + PA Vi -
Good events
For any 8 (0, 1). we define the following good events:
For RRL-MNL,
( = | a)l < (olll)l@raaaa
GE (5)
max (1E(TR) Anna S sma(0)) ME(M]
(g) (A) n g
GL(8) == n (0),
KE[H]
g(K, 6) n (x(
K
20

---

For ORRL-MNL,
6 (6) [ S HBa(d) Popy( s a)
(0
B
S'ES,,a
max s'Saa
11
Brr
6 4,4 (0)
1 BE. S =a(0)}
max mE[M
(6) (5) B
(5))
(%(6) N (0),
(KK, = n (())) K
Derivative of MNL transition model
Proposition (Derivative MNL transition model), The gradient and Hessian of Po ., can be calculated as follows:
Pelss s, = Pols' |
Ps.as' Σ
Pols"
18,0)
(8)
s"ES..a
= Pols' |s,a)p
and
PoPols' s)
-Pols' 8, s,
- Pold' a)
Σ
Po(s" I 8,a) (4 ( + 4 Pa.aa e, + Pa.
(9)
8'ES.,
+ 2P 8,
Σ S"ES..
Po(s" 5.
Σ
Pols" (s,))4ss...
Proof of Proposition 7 Let 0 = (f1....,aa) Oa) and le be the i-th component of ss.a,, Then, we have
0
Pols' s))a)
00,
exp 0) (8 sprrr exp (4 (a E) exp (4T (sa.a,orls
EveSS, exp
Es"Esoo exp (pT (p)
= Polss a, (Paaall - Σ
Pols" |s, s.a))ls,a,rr))
s"ES...
Then, the gradient of Po(s' s, is given by
Pooss' s, s, Po(s' s, a) Pols' ss,a) Σ
Po(s" |s, a
s"ESa.
= Po(s' s,,)) Poias
Σ
Pols" (ss))))
R'ES.
= Po(ss' 1,, s,,))s..,.'
21

---

On the other hand, the second derivative 06,08; Po(s' S, a) can be obtained as follows:
Pe s))
00,00,
Po s,,)
(ennarle- E
Pols" s,))lesasrll
s"ES..o
E
Pols" |s s
s"ESu.a
+ Polss s,
Σ s"ES.ia
Pols" (,,a)
Σ
Po( a,))ls,,,, 10 (ssaarll
3ES..a
= Pooss 5,a)
Σ
Po(s" 8, a) ail + te ([
s"ES,,a
Σ
Po(s" a))l
Σ d'ES...
Pols" s, s,a))9sa,00ls
E'ES...
Σ
Pols" s, ss aa
s"ESn.a
Pa( 8, a.) }
Σ Pols" | s,
Σ
S"ES.a
iES.
Pals' (8,))
{1p 19 (1
Σ e"ES,,a
Pols" s, s, (l + (e
Σ Pols" 8, s, /.
s"ES.,.
Pols" 1 (. )
Σ Pa(s" s,,a)lp..a.
Σ S"EESe
+2
8"ES,,
Thus, get the desired result follows: 4 Po a)
Po(s'
|s, 1,0)) a.a.s'
Po(s' a, Σ Pols" a) (Ps,a. + @ as J.a.o + P F....r))
8"ES..a
)
+2Po(s' ss,a)
Σ
Pols" (s
Σ S"ES...
Po(s" ss s,0)4paaan"
s"ES...
C Detailed Regret Analysis for RRL-MNL (Theorem 1
In this section, we provide the complete proof of Theorem 1 First, we introduce all the technical lemmas needed to prove Theorem D along with their proofs. the end of this section, we present the proof of Theorem
22

---

C.1
Concentration of Estimated Transition Core 0%
In this section, we provide the concentration inequality for the estimated transition core run by the approximate online Newton step. The proof is similar to that given by Oh and Iyengar [55]. For completeness, we provide the detailed proof.
Lemma (Concentration of online estimated transition core). For each h E [H) if L.p then we have
IP (vk 1, 1 A.l.AA I Lal()) 2 1 1-
where ork (6) is given by Ork (6)
8d log
k dd
L2
16)
(1+ [2 2og, h h2
+
+
log
+ 2v + 2
3
Proof of lemmal 7 Recall that the per-round loss (0) and its gradient Gk, (0) is defined as follows:
(0)
Σ
(s's log Pols' s a Gk (0) = (o)r,
s'ESu.h
For the analysis, we define the conditional expectations of (0) & G ( as follows:
(0) == B ( FR.n) G = E (G (0) Fk,n]-
By Taylor expansion with v0t + 2)0%, for some v E (0. 1). we have
(0,) = a (0%) + G (0%) (0) 0% + + 0 - 0 HHR - 0,), (10)
where (0) is the Hessian of the per-round loss evaluated at 0, i.c.. (0) = (0,
(11)
= Σ Po sh ah oh..k.hhee.....
s' V
Pols' sh Po sh o P
Note that for 0 =v0 + (1 1)0 with (0, 1), have
H = Σ Ps sh at Pp.h
d'ESt,h
Σ
Σ
Pals' sh at Po(s sh ah
S'E 8ES+.6
Σ Po(s'1 sh an
d'ESt,
Σ Σ Pals' sh Po sh ai PRinsPin
S'S BES+.
Σ
Pa(s') sh Pa..
S'ESt,h
Σ Σ Pols' Po sh de P
S'SLA FESUA
= Σ Pols') shi Pr.hh
Σ S'ESAA FES+
P sh Po sit at ohwhh.hh
23

---

where the inequality utilizes the fact that xx T + +yy = xxy" yxx for any x.y E R Therefore, we have
(0) =
Σ
Po
she and Pk.h, Ppknh
d'ESk.
E
E
Pols' sh Po sh a ohn
Su SESE,
E
Pols's 8h th P
8 F
E
E
Pals' sh Po(5 shi Ph. Pbnn
6 tbr Bfie,
Pols' oh) (1-
Σ
(
E Po( @ ati)
Σ
Pols') sh ah)
sh (ol)).kk.... (k..at))kk....r... Pkiitn
Σ
RKkkh, s Phin.
Σ KiPkA,, Pii,
S'ESk.h
where 6n,6. A is the state satisfying sp ((5% ar, 82,n) O₂ and the last inequality comes from the Assumption 4
Using the lower bound of the Hessian of the per-round loss evaluated at 0, from 10 we have
(0,) 2 (4.n (O)) (0% 0% -0 -
1
Σ
Pk
(0% 0%)
Pk.h,
s'ESk..
By rearranging, we have Cu (O,) S (0,) + GO TO0) 00,)
K 10, - oh W W. O 2
where we denote kh = EvESE, P sk,,,.' By taking expectation over v we have (O < (O,)) + (O,) T(0). - 0%
an (0 - 0% Wa. 0%
"
(12)
2
On the other hand, for any 0 E Rdd, since we have (0) - (0%)
Σ Poi (6') sh at) log Pols' si a +
Σ
Po: (5' 8h at) log Po (5' a
d'ESE,
s'ESen
Σ
Poz(s (5' shi att (log Poz (s' at:) log Po s/.
e'ES
Ps att)
Σ
Poy (5' sh at) log
Pols' st, a
S'ESe,n
(Po; Po)
2 0, where (PL Q) is the Kullback-Leibler divergence of P from Q, from
12 we have
0 - (4.1 (0%) (..
- (0,) T(O); 0%,
k 0 2
2
= (O)) T(o) 0%
k
0
w + (GrA(O)) - GR.(O))) (Ø) - 07) (13)
2
24

---

To get an upper bound of G,,) T(0)) - -0 recall that the estimated transition core is given by
0
2110 0% A + + - T GR. ( OEBa(L.)
argmin
(14)
Since the objective function in 14 is convex, by the first-order optimality condition for any 0 E (a(L.) we have
(R.)((O))) + Ast1, 08)) (0 1 0,
which gives
θ (0 -0% (TT 10 - -
TO%) 1tt1).. (15)
Then, we have
1
1
A 11. 10
1 A
(0)) T A 1 -00 (T) A
k+1 +2(0)) A -0%)
(0%) 1, -00 (I) ASt1NO
(0 1 0%)
-2G (
[0) -0
(by (15)
(0h) T A +(O
k+1 -2 A 2G T00 0%++1
110% 1 "1AAn- 22 (0%)
(0) 2
100 0 -112 + 2GR (0%)
(0) 0% + (0 -07)
2 - G 112 A + a. T 0,),
(16)
where the last inequality follows by the fact that
100 1 + 2... T(o)+
((O) - 0%² 2 min
{1011a + (GG 0}
@EBu(T.o)
-H, Act..n"
Therefore, from 16 we have
1 2100% 07 -1,12 110
(O 0 S (0
+
17,1 u. (17)
k+1.
By substituting 17 into 13
have
0 < GR.h (1:)122 A + 111 - -0,1 +10 -
K 10 - 0xllwza + (Gr,(Ot) - GkA(O T (0) -0))
(18)
2
25

---

Note that since we have
[GG,NOO A
E
(Por sh: 1sh - - -h((6)) (Po: (3 sh vh(3) Pkn PAA.
1
Σ
(Pag(o' a - -h((') (Pot (31 ak) - vt(33)
2
A
( (pKh A + 3k. k- 1, Pk.
1
Σ
(Pog(8' 18h - sk(6') Pkihi t Pk
S
2
8 a
(Po b/ at) -)((()) Pkin, A PR..
Σ
sh. 1 - s/(6') Pkih A KtIN
8'ESe,h
Σ
(B sh ah) - 33) sk A K+in
S'E
$
Σ
(Pot(1
sh aht + wh())) sk A A
S'E
Σ
Pog shi d.i)pptTm.... Ak,,,
Σ S
A
S'
2 max s'ESx.h
1| ANLLA
(19)
TT where the first inequality utilizes the inequality T Ay + + Ax y Ay for any positive- semidefinite matrix A, and the last inequality holds since 0 S Poz (5' 1% a S 1 and En Po (s'
sh: = 1.
Combining the results of 18 and 19
we have
0 S max 114 d'ESu.n
Ali. -110% 0%1 A
1
11
-0,1 A
2 10% - @ + (Gr,, - (R,
K
T (0) 0%
= max 3'ESe.h
11 A + =1100% - 0 +
7 110
K
0 W
- 110 ARti.
12
T
2 1110% l + (Gu,N(0)) - (
(0) 0%
max d'Se.
11 Aetin -110% 0.
14 110%
7
0% W. 11 1 1
+ +(Gn,(0H) GR,((O)) (0) 0%),
where for the first equality we use ARt1,h = A + $ Wa. By rearranging the terms, we have
110ht1
-0, 2
110²
0 17 +2 max 1|y Il At.. -110% 0%,1 Wen 3'Eden
(G.n(O)) Go.( (0): -0%)
2
26

---

Then summing over & gives
k 2
|10% 0% 01
1 101,1 -
10 1211 +2 max s'Esi 1=1
11 1 A7th,
10 - 0% 1l
1=1
+ 2 Σ
(G),(00)) - (o T (0) 0%)
1=1
< 2XL3 +
max S'ES,,
1|sp,n 1|A-1 Σ 110 0%
ArtLin
(O,) - (o)(()))) T (0) -7%)
+
For the final step, note that Gi,, (0)) G. (0%) (0) 0%) is martingale difference sequence. To bound this term, we invoke the following lemmas:
Lemma 2. For 8 E (0,1) 1) and (k, h) E [K] (M), with probability at least 5 we have
(O,) - (o)( T (0) 00)
0 Wl + 16LigL0 K
+ [ log
8
(1+ [2log, Lo h2
+ V2.
3
K
Lemma 3 (Generalized elliptical potential). Let S (x.1...., xt,, } C Rd. For any < ST
and i E [K] suppose [xtalla S L. Let V, = Ala + E E Eies, Xr, T, for some > If
L2, then we have
TKL dA
Σ max [|[
Xx, 12, S 2d
1
By Lemma with probability least 1 1-6 5, we have
110
11
< 2AL2 + 2
Σ
max
||
112 A
r'E.,A
==1
16
(1+ 12 kUL Lol)
+
log
+2
3
K
k
32 32 up To
16
[22log kld Io 1 log (1+
k2
< 2A12 +
doog
+
10
+
+ 2
d)
8
where the second inequality comes from Lemma Note that the Gram matrix A in Algorithm and the Gram matrix V in Lemma 3 are different by the factor of 5, which results in additional factor for the bound of E max,reS.a || 12 A
In the following, provide all the proofs of the lemmas used to prove Lemmal |
27

---

C.1.1
Proof of Lemma 2
Proof of Lemma quence, i.e.,
Note that (f)) (0))) (0) 0%) is martingale difference se-
(G), G.,((O)) T (0) - -f%) | Fe.h)
(0)) - [G.,(0)) | Fi,a)) T (0) - 0%
0.
On the other hand, for any 0 E IR,, since we have
(G)l2
Σ
(Po(s'
-
(/')) Pii
d'ES.A
<
Poo sh, ah)) (/') |1 l12
R'ES.A
$ Lip
Σ
Pals' of) +
Σ vh()')
d'ESLM
8' s'ESt.
2T.pp
then, it follows by
(G)) - ())((()) (0) - 077)
(G),(O))) T (0) - -0,) + (G)) T (0) 0%)
(2.)) 0%112 G., (B)lll)) 11200,00 17
11p 0%
LL
(20)
where the last inequality follows by 10 0 - |10 |10,122 S 2T. Hence, if we denote
Ma Ei= (O)) (..) (0) 0%) then Ma.h is martingale. Note that also
28

---

have
Ekgh
Σ
Byy
(G))(()) ((,) (0), -0i))
i=1
([GG)(0))] T (0) )o)= Byg
(IGIN(ON) (0 01)) =
Byi
10
(GG (0) 10%-007 (0)--
1=1
27
Byg
Σ
(os (5' ah)
- wh()') (0h - -iA)
D'ESLA
Σ (6) - )
Byh
Σ
(0 - 07))
7m1
MESIA
(21)
(
Σ Byj Σ
(Pog (s' sh. vh(()))
Σ (0k-))))
s'ESi,n
N'ES.,
2
(4PT.hior (0 -07))²
(22)
1=1 N VESL
4:
0% Ww,, =: BR. 110%
where 21 holds by the Cauchy-Schwaad inequality, (22 holds because
Σ
Pos (8') shh - ví. (6())) 2
8 E'S
Σ
{ (Pog (6') ahh)) 2o (s') sh, + {}))
S'EEL
< 2.
However, if we denote BR, : 2 |00 0 1 W.,.. since BR is itself random variable, to
apply Freedman's inequality to MR. we consider cases depending on the values of Ba
Case 1: BK <
4 ku
29

---

Suppose that B,, = == 2 100 -07ll.,.
$
4 kir
Then we have
MR,6 Σ (Gh)(Oh) Go)( T (0 -0h
k
Σ
Σ (uh(s') (by)() IT. (0) - 0%,
i=1 d'E
k
Σ (vh((')) po (5' ah)) 2T.n, -0%)
i=1 d'E
k
1 -0x
1=1 S'E
ku
Σ
(0h 07)
BEG
kl
22.
Case 2: Bugh Rd
Suppose that Be, = 2 2 110]
1l > ker
Then, we have both a lower and upper bound
for BE, as follows:
< BRGh 2
Σ
Σ
0 < 8
ku
d'SS
Then by the peeling process from Bartlett et al. for any Th > we have
161%-LupLo
P Ma, 2 2 BE, +
3
167 Lo
4
=P
Ma. 2 2/ BrBBA +
Br s 8
3
kll
16m Lo
4
=P
Ma. 2 nEBA +
B S ShuLL3 L3g En.o S Ba...)
3
kill
m
16m Tup T.
4. 4/
4.20
Σ
PP
Mr. 2 m/ BE,
< Ba, kill
EEA S Bk.
klll
8. 2
16m Lup Lo
4. 2
MR.k 2 V
1k
ΣeE, S
(23)
kull
kild
where = 1+ [2 kil Le For 15. note that from 20 we have
(Gr,,(0%) - (O)) (0) - 0i) s LL
30

---

By Freedman's 's inequality (Lemma 29
we have
8
2
16m To Lo Ek,, S
4.20
I
Ma,h 2
Th
+
kil1
kild
8.23 kidd
161 Lupha
11k
I exp
8:21 RI
+
3/B LL
8:24 (VTh
16me Lap
3
8-21 kil
/6 MopL
exp
8-25 kld
+
16 Le
8-25 kMl
16 nu Lg
3
3
8-21
Th 3
127
< exp
8-23
L2 La 3
8:22
16 12
1]k:
3
exp( (m))
(24)
By substituting Eq. (24 into Eq.
23
we have
L
MR, 2 2 BB.B +
m
3
(1+ log, ki Lo 1)k²
Then, combining with the result of Case & letting f)s log 37k² log and taking union bound over k with probability at least we have
k 27k
16m LupLo + /2.
MR S 2
0
0
(25)
3
By applying 2 S + to the first term on the right hand side, we have
k
87k
2,
27k
0
10
0% I
W.....
(26)
W..k
K
Combining the results of Eq.
25 & Eq.
26). we have
MR
Σ (Ot)
(. (0), 0%)
k 10,, 0,, +
1161igl +
8
(1+ [2 klL Lo 1) 62
5
log
+ /2.
k
8
1=1
31

---

C.1.2 Proof of Lemma
Proof of Lemma
3
By definition of Vt, we have
det(V = det Ve+ Σ
x1,
iESt
det(V,) det
La
+ Σ
V
xx vo
iESt
(V,)
+
Σ
||x,,
2 Vi+
ieS.
dee(AAa) II
1
||XT,il 11
rml
iES,
2 det() II
1 max rE
Xx++ li2v
(27)
Since À 2 L2, we have
L X pl S 1. 1.
max IES-
Since for any 2 E [0, 1], it follows that S 2log(1 + 2). Hence, we have
T
T
max ES
xx,,
< 2 Σ log
1 max iESt
t=1
T
= 2 log II t=1
1 + max SE
|| |
dot(VV+1)
< 2 2lo det(ALa)
(1 1
TKL
< 2d 2d
dA
where the second inequality comes from Eq. (7 and the last inequality follows by the determinant-
trace inequality (I (Lemma) 28
C.2 Bound on Prediction Error
In this section, we provide the bound on the prediction error induced by estimated transition core 0 Lemma 4 (Bound Prediction Error). For any 5 E (0, 1). suppose that Lemma 7 holds. Then for any (s, a) E S x A, we have
(+(s, & Ha..))lllassssaall
Proof of Lemma
Recall that
Ah(s,))= = Σ (P (s's(ssa)) Poy (s' s,ai) Vitrass)
S'ES.,a
eXplypT e, V
explyp_ oxp(+I....0%)) 02 h+1 (s')
Σ
Exes.. explyp 2.,3 0%) e'ES...
Exes,, explyp_ 20, 2,0,3 07)
S'ES..
32

---

Then by the mean value theorem, there exists 0 - p0 + (1 - p)0% for some [0, 1] satisfying that
as) = (EvEs... exp(y),,,
0) (xvees.eepp(P)... s,0,a'
(5)) 10 - -07) (Eiess.. exp(1p.,,,
(Eses,, exp(< axp, s,a,3 8)
Eressn exple 0 ( (Eres.. exple 0)4 (0) 0%)
E Esss... exp((p.a.;30
E Pols' (s (0) -%))
s'ES.,a
Eves,,. exply s.,, 0V
Σ
Pold' 8, (,,)) -0,)
Esesun exp(1) s.0,
e'ES..a
Vitta6s) Eves,,. exply T s.0 0)V (5')
Σ
Pols' s, (0 0%)
Eses. exp(1) s,0.3 0)
S'ES.,a
Since (s') < 11 for all s' E [K], and h E [1],, we have
Σ Po(s' 8, a. 0%)
s'ES.,a
H max d'ES,aa
I (0) -8))1
- H max s'ES,,
114
1| A 110 0%llarn
S Hog
where the second inequality comes from the fact that Pals' I s,a) I 1 is multinomial probability, the third inequality holds due to the Cauchy-Schwerd inequality, and the last in- equality follows from Lemma and the definition of P i.e, an, (8) a,),,,,8 for
I argmaxyes,.. ||sp(s, s') A (')
C.3 Good Events with High Probability
Lemma (Good event probability). For any K e N and 8 E (0, 1). the good event ( 8') holds with probability at least 1 5 where 8' = (2K..
Proof of Lemma
For any 8' E (0, 1), we have
G(K,8) N n (o))
N KSK NSH
n
(o) n ((.)
kSK ASH
On the other hand, for any (ks, h) E [K] [H]. by Lemma 30 gf (6') holds with probability at least
1 8'. Then, for 8' 6/(2K H) by taking union bound, we have the desired result follows:
P(G(K, 8') 2 (1 - 2) 2K - 8.
C.4 Stochastic Optimism
Lemma (Stochastic optimism). For any 8 with 0 8 < (--1)/2 let 0 (ox Ö(H =(H
we take multiple sample size M [[1
log H
then for any E [K], we have
log (11
P ((VV >0 2 =0)()))0
- 2-1)
33

---

Proof of lemma 6 Before presenting the proof, we introduce the following lemmas.
Lemma 7. For any [K]. holds
H
(* - (it Ex-
Σ
1/ (1n, an) 1 21 =
where (=) := rs) Ph Q%
Lemma 8. Let 8 (0, be given. For any (k; [K] x [H], let oz = Ho)(()) If we define the event (6) as (6)
(0) = { a) s Hon (8)l (s, (
then conditioned on g (6), for any (s, E x A, we have
P (=) 2 2 9 (6)) 2 - $(1)"²
Lemma 9. Let ò (0, be given. For any kh [H] [K], let ox Hax(0). If take log H 1. then conditioned the event ( (6) Nhee ( log (11)
multiple sample size M [1 we have
P (sh. an) 2 0, vh E [M] (f 2 (--))
Now, we define the event of the estimated value function being optimistic at the start of the k-th episode as
x= {(V (s) 2 0}
Then for the event Gx((6) Gk. have
IP(A)) 1 P(())
P(AE n 9k) P(ME n 99)
2 1 P(AG n GR) P(G))
2 P(N n 9x)
where the last inequality comes from lemma 5
On the other hand, by Lemma we have
H
(14 - V
2 Eg
# (xn, an) | =
H
E | 1/ (2), and | 20 =s/-
If we define event
H
Ex- [- [- [1h, an) 10 = st] 20
Vk
then, by Lemma 9 we have
PP0 9x) 2 (--1)
- P(Y 9x) 51)
PO ( < (1 2 (-) (PG))) S ((-1))
Note that since X n C CD n GL. we can conclude that
P(())) 2 - P( n Gk) - PPC/ n Gk) -
2 (1 - (--)) -
((-1)=
2 (2
where the last inequality comes from the choice of
In the following, provide all the proofs of the lemmas used to prove Lemmal 6
34

---

C.4.1 Proof of Lemmal 7
Proof of lemma 7
In this proof, we use of, as the states sampled under the x² to distinguish with s%
Since we have,
(*))) (s+()
(((()
= =r(s", " (s() +
PV(V2
-
(st) [(V =
or (et) [(9]
02)(2 - -
Rag-eet -ef (of))
Baja (at) [1' - [z)( - (2 x (xb)) ((0 (+f))
E wot o (of)
Bui (x)) [133 - V3 [x)]
Bag (VV) v3)
E (( (< xt (x+)) + (s x (sf))
then by applying this argument recursively, we finally have
E
Σ (1p: an) 1 1=1=sh
C.4.2 Proof of Lemma 8
Proof of Lemmal g Since we have
- (s, = (h a) (r(s,a) + Pa (s)))
=min a(s,a)+ +
Σ
Por (5, ( + max me(M) ( cc(m)) H
8'ES.aa
((r(s,a) + + (s.)++
min Σ (s s/a) + max (s Py V (
mE(M]
d'ES...
is enough show that
Σ
(o (8,a8) (6) max (x, a) Tclm) Pa. V (s, mEjM
e'ES...
at least with constant probability.
On the other hand, under the event (K), by Lemma we have
Σ
(s 8, V (5') + max ( a) c(mm) PA (s, mE(M]
ESS...
2 max PR (8, aaT ((m) (s ME(M]
Now, for Vm E [M], since clm ~ ~N(a.. of we have
(s,
Te(m)
Sk.
35

---

which means,
P( ( (0, aaaaT)") - 2 Hox (0) (8, a)) 2 $(-1),
by setting = (aH((()))) Then, finally we have the desired results as follows:
P (s, a) (5))
2 P max P (s, a) ch. Hax (fa.(0))lpnnss.))ll:: (2)(0))
mE|M]
= 1 IP (frnn a) T " < (axx (s, A>) Vm E [M] (2 (6)
2 1 - (1 - (11)))
= 1 - (1)
C.4.3 Proof of Lemma 9
Proof of Lemma 9 For each h e [4] and & [K], define an event E it holds
(-1h and 2 03 Then
11
n
P (- and 2 wh E [H] 9 (6))
=
E 9
"
U(e)) 19 (0)
= -
h=1
2 1 - Σ
P ((E (x))
h=1
2 1 H1(1)
2 (-1)
where the first inequality uses the union bound, the second incquality comes from the Lemma g and the last inequality holds due to the choice of M = [1
log log 40
C.5 Bound on Estimation Part
We decompose the regret into the estimation part and the pessimism part as follows:
K
K
Σ
(sf))
A==1
Pessimism
Estimation
and we bound these two parts in the following sections, respectively.
Lemma 10 (Bound on estimation part). For any 8 (0,1), if 2 Tgg then with probability least
1 - 8/2, we have
Σ - 0
Proof of lemma 10
For any given & E [K].
(Vi+ VI )s
(Q) oF (oot.ff) + ( at) - - ((sss
= =Q) oT (st at) + PV -
(28)
+ +(A ( at) - a4)
d
Pi(V3 155" (st (st) (VB Vgr (st) +(V v)r"(($)) (f(ttaat)
2t
36

---

where the second equality holds due to the variant of (5 ax) follows:
(sh. a r(sh a Ph Vi (s o s ab) + + (sh aht (sh
= r(hh a + Ph V ( (sh abi
+ Qh (sh ax) (r(st) aht + Ph. V (s ot))
Ph (5 a/) (Q (5 af)
Then, by applying this argument recursively for whole horizon, we have
-V--V 17 (5))
Σ
(s a +
Σ ch
(29)
where cx = Ps. (v (sh. (Vi
Let = H)) By Lemma 5 the good event GKK, 8') holds with probability at least 8/4.
Then under the event G(K, 8"), for any h E [H] we have
(oh, ali))
Qh ahh (r(sh. i ahi)
min
Σ
Po oh a (8')
& (8h (sk.
TT Sk.h H
mEiM
e'ESe,h
(r(sh, aht) + PAVhi
Σ Pog(d') | a/) Vi+1
G (sh (t) Telmm Pa V mE(M)
Vh++1 (0h
max
e'ES
Σ Poz(s' shi Vol - PA 1 (sh a/t
+ max me(dd]
&R,, (sh, (h))
Sk. T
c(m))
(5 at)1+ + max
1 (5 attilll 115f. IlAr,
(30)
MEMi
< (8))(8) + (50)) (s a A::
(31)
where 330 comes from the Sauchy-Schwarr inequality and (31) holds due the the Lemma 4 & 30
Then, with probability at least 5/4, we have
H
+ 1 af
(32)
On the other hand, for 2) we have 1. < 2H and Elit Fu.n)= = 0, which means (š) F is martingale difference sequence for any [K] and [H]. Hence, by applying the Azuma- Hoeffding incquality with probability at least 8/4, we have
ΣΣ< t 2 k=1
(33)
37

---

Combining the results of 32 and 33
with probability at least 1 8/2, we have
(VT VT" )s
H
$ 2H (og(//))
(Hax((")) + +x(1))))))) 11 (sh (sh.
K
+ ( (8') S 2 log(///)))))))))) (Hax(0)
pp (s ah)lll
(34)
H
K
+ xxk(8') < 2HH (H
K
|| 6 P (s a
(35)
h=
A=
1
H
KUTL222
2H (Hax(8) +xx (8))
115 Kdlog
1+
(36)
dd
h=1
KUL
7k(11)) V -2H /2T (Hax(8) + (Hxx
Ar6 dn--THdlog
1+
dd
=
where (34) follows from the fact that both an (6) and (6) are increasing in k. (35) comes from
Cauchy-Schwarz inequality and (36) holds by the generalized elliptical potential lemma (Lemma 3
C.6 Bound on Pessimism Part
Lemma 11 (Bound on pessimism). For any 5 with < ( let og = Hoy If 2 1 and we take multiple sample size M =[1
log H log (11 1. then with probability at least - 6/2, we have
Σ (V. - -1)s) = 5 (x
Proof of lemma 77 Similar to the techniques used in [73. we show that the difference between the optimal value function Vi* and the estimated value function Vf can be controlled by constructing an upper bound V and lower bound on V. In this proof, consider three kinds of pseudo-noises, E. and & that we define later in the proof. Also, for d' = 8/10, we denote G(K, ((), K, 8') and G(K, 8') as the good events induced by ε and respectively. From now on, we denote G(K, 6') by the event ((K, 8') n n (*) (g(K, Then, by Lemma the event G(K, 8') holds with high probability at least 1 - 36/10.
(m)
First, we construct the lower bound of V/k For any given E let a set of vectors for h E [H] and (-: be the value function obtained by the Algorithm with <(m) non-random Eg. in place of ((m) Then consider the following minimization problem:
let = (ER,A ImE[M] C Rd be
min
(s
(m)
(5k mE(M)
(m) max [| Ilaaa I ( vh (H)
s.t.
mE[M]
And we denote & ( Me(H)) by minimizer and (**) by the minimum of the above minimization problem, i... VV(() == (-:E). Then, under the event G(K, 8'), since ( me(() is also feasible solution of the above optimization problem, and since V V () thus we have
(((t < (st).
(37)
38

---

(m(m))
Second, find upper bound for V considering i.i.d copies (Se,h me(H) of (Sk, [Ne[M] and run Algorithm get corresponding value function Vi and Q% for all E [H]. Define the event that V (s*) is optimistic in the k-th episode as
& = ((V) - 2=)
Then by Lemma for given 6, we have
P( Fx) 2 (--1)/2
Then by the definition of optimism, under the event g(K, 8'): we have
(Vi (+ v
R & [V - (+1)
E & (Vf
(sf)
(38)
where the expectations from (37.. On the other hand, under the event G 8¹) by the law of the total expectation, we have
the eos conditioned on the event Xs and the second inequality comes
B (VF - (s) = x (v/ - (s4)
P(())) + E
(V (+) P(Z))
2 Eq ( - (**) P((X))
(39)
where 339 comes from the fact that (Ek,h Me(HH,mE[M also a feasible solution of the above optimization problem under the event G(K, 8'). i... (sf) 2 (st).. Then, by combining the results of 39 and 38), under the event G K, 8'), we have
(Vr (31) & BE
(V/ - (()(s))
$ Eg
(1/* (b (+)) /P({zt)
(-1) Eg (V/ V + Vt - 2O(+
2
(rrt - -k))(+)) + c..
(40)
(-11)
where we denote
Č = Φ ((-1) EEg [V+ v+(
Note that since & is the i.idd copy of &. therefore UR, and V4.1 are independent, which means 2H
{šx F is martingale difference sequence with l&xl क Therefore by applying
Azuma-Hoeffiding inequality under the event G(K, 8'), with probability least 1 8', we have
2H
<
V 2K log(1/8)) (--1)
(41)
On the other hand, by dividing the first term in 40 into two terms we have
(V+ - (()))) = (v / (st)) (VT"
(+)
For I1 note that since it is related to the estimation error, under the event G(K, 8') we can bound the sum of I for the total episode number using Lemma 10 as follows:
KUL3
Σ (v Vi )(t) < (Hag (8') + (8))))
V
4x 4x-ITHdlog
1+
dA
+ 2H / 2T log(1/8"))
(42)
39

---

For 12, since we have
1 Qi asj.af? vi())
Qi (sf, - ( ar)
(43)
oi as) (o at) af) af)
+
Pi(V2T - (s) of) + +#(st.of)
(44)
PIVVT* L a (VT" (+2) +(T
++)+ (st,
+
where (33 comes from of argmax, (f(, a) and 44 holds by the following definition of (s D:
2 (sh at) == r(sh at) + Pv vi (5h, at) (sh ah)
=r(sh att + Ps V h+ (s a 21 aht + 2 (s a Q (s
= PhiLVh++ V (s a + 1Q% - (5h ah.
Then by applying the same argument recursively for the whole horizon, we have
H
mk
12
S
+
Shi
h=1
Aml
where we denote
l C = PV - -httz o - (Viti - (
Note that { .ock event G(K,8) by applying the Azuma-Hoefdding inequality with probability at least 8', we have
(hh FR.A }
is martingale difference sequence with (2 S 2H. Then, under the
k.
K
H
b C S
2H 2T log(1/"))
(45)
To bound Eim1 (o )t),, we divide the whole horizon index set into two groups as follows:
H+
= j E [H]] r(())
Σ
Poz 15), af) + max (t,(()) (im)
) >
mE[M]
S'S
H = [H]
Then, for j E H since - V+ H - and ((f),a8) S 1, we have
H
(1 a)) = - 5+1 (5), at)) -H - 1) S.
(46)
On the other hand, for E -H- under the event G(K, 8') we have
(s)) at) P,V 1 (5t.
Σ
Por (s') | a V (5))
(s), T
max mE(M]
8'ESks
<
Σ S'SE.s
Por (s') st (6))))))6'))
+
max ME[M]
(5)
- {((m)
< Han(6')ll (5)) al) mE(M]
max
Pk (s) at) Te(m)))
(47)
I Hax(5')ll (5)) (2)11 ب|ااا
+ mEiM
max
|| 1 (s) a بلااا
((1)) ||
< (0) + () | (s), af)
(48)
40

---

where 47
holds by Lemma
By combining the result of (46) and 488)
have
H
2 < Σ (Hox( + mx(')) |k (6). (A
JeH
h=1
H
Σ
(Hax("") + (8')) 1 (othaaalllll +
ok
S
h=1
h=1
Then summing 12 over the total number of episodes, under the event G(K, 8'), we have
K
K
V - k+) -
(Ha) + (6')) |1 (6 ())
h=1
K
H
K
H
(Hak (8') + 7x)()))
P (sh a
k=1h=1
h=1
4K /4x- -d [ KULL
I (Hax + + (+x
V
(49)
dd
+ 2H 2 1o7T0g(1//)))
(50)
where the last inequality holds due to the Lemma and 45)
Finally, by summing (40) over lt and plugging the results of
42 50 and
41 then, we have
K
Σ (Vi - (s}))
k=1
KUl
(Hax(8) + +xx(0)) (Hax())+>x(0)) ( (1+
+ 2H
/2
2T log(1/8))
o(-1)
dd
2H
((-1) /2K (ogg(11//8)
< 2 112
To conclude the proof, by setting 8' 5/10 10 and we take union bound over the two applications of
Azuma-Hoefiding (Sk, 2h and the event G(K, 8'), we get the desired result with probability at least
1 1-8/2.
C.7 Regret Bound of RRL-MNL
Proof of Theorem
We can decompose the regret with estimation part and pessimism part as follows:
K
Regret, (K)
k=1
Σ (Vi (+)(s))
Σ V/ (st))
Since both Lemma 10 and Lemma 11 holds with probability at least 1 - 5/2 respectively, by taking the union bound the following holds with probability least 1 5:
Regret, , (K) = -((== ( HVT HVV+HHK))))))))H + 6 (K - 11 H VT HVT)
o -((x-dtH
41

---

D Detailed Regret Analysis for ORRL-MNN (Theorem 2
D.1 Concentration of Estimated Transition Core 0
In this section, we provide the detailed proof of Lemma 12 which demonstrates the concentration result for 0% independently of k and U. Note that we adapt the proof provided by Zhang and Sugiyama [76] in the MNL contextual bandit setting MNL-MDPs and improve the result, making it independent of 41 We provide the lemmas for the concentration of the online transition core for completeness, noting that there are slight differences compared their work, which stem from the different problem setting.
Lemma 12 (Concentration of online estimated transition core). Let = (log and X = 4)) Then, for any (0, 1] and for any E [H]. we have
P 4k 2 1,
0
0%
S Ba(0)
2 1 21-6,
BA.b
where (x) O(Vdlo log(k)))))
Proof of Lemma 12.
Recall that the transition updated by the online mirror descent is represented
by
1
0++
argmin & (0) OEB(Lo)
+
0
0
2m
B
where (0) lx 0
(0
0%)
Vex.
0
We introduce the
following lemma providing that the estimation error of the online estimator 0% can be bounded by the regret.
Lemma 13 (Lemma 12 in 76 Let = logut + 2(1 + Loluo) and X > O. If we set the step size
? = a/2, then we have
10%
1
07
I
- -l,,((((+1)) -
+ AL
BR.
1=1
(51)
3v 2T
0
0+1
0x
B.,
Now, we bound the first term of 51 To simplify the presentation, for all (k, h) [K] x [H],
define the softmax function k.
R Sm.al
[0, 1] SS as follows:
exp(1z]er
(. ExreSin exp((z)a".)
where H.r denote the element corresponding to s' S of the input vector. We also define the log((p)>) which has the property that for all E Ajsu, we have ( 2. (p)) = and Exese, exp (lo (p)l.) ( =
pseudo-inverse of the softmax function oi via (o
We denote PAAA = Ish. E (S..a for simplicity. can also be written as Po(s' st at)
Then, the transition model ( 07)... We further define ž.
for our analysis. Then, we have
(0,) - (,,
Σ (1,)(O)) e(ann vh)) +
Σ
((Zmn. (Oxt1)
(52)
We can bound the first term of 52 by the following lemma.
42

---

Lemma 14. Ler 8 E (0, 1]. Then. for all (k. E [K] x [H]. with probability at least - 6, we have
(0,( - -l(zi, - (0),
where (8) (3 Lug Lo) 4(3log(Ukk) Lo) log HvI+2k
2.
Furthermore, we can bound the second term of 52 by the following lemma.
Lemma 15. Lef X 2 72I22eu cd. Then, for any 0 and all (k:, h) [K] x [H]. we have
k Σ
(o vih) (,,((0)t1))
S
0x11 0
+ (8).
2c
B.A
where (6) /Bed log (1+
2 dA
Combining Lemma 13 Lemma
14 and Lemma
15 and by setting 7 a/2,,c 2xx/3 and
À 2 max maxx122/222) 122/222 2
derive that
0h 0% Ba.
<aT aT (8) + XL2 + +3
0
0
a
Σ
0
0
2c
B,
< <TT aT (8) + AL
H HvI+ 2h
+ dlog 1 :b)
)) ALA
- C'ooul Alog(Ukk) + log(Ukk log
(6)
(53)
where C' is an absolute constant. the above, we choose À = O(dlog()), a = O(log(). The second incquality of (53) is derived from the fact that
k
3 21
a
0F
+
0
0
2c
B.
1=1
i=1
= =3V2L a Σ
@++1
0
0
0
Bi
k
< <3/2L
0i+1
0
2
+
0
h
1=1
0..
The first inequality holds from B. ALg, and the second inequality is obvious from setting of X. Therefore, we can conclude that
0
0%
Bb()0) O(Valog(//ogg(kF))
BE.
In the following section, provide the proofs of the lemmas used in Lemma 12
43

---

D.1.1
Proof of Lemma 13
Let (,, = (0,) + (O)) (o (0-0%)
0%) + 00- 0% 2
Proof of Lemma 13
be
(0, (0
second-order Taylor expansion of (.)(()) at 0 Since we have
@++11 argmin (T))
0
0%
+ V4
argmin (0) +
1
0
0
21
B
Te)
2n
B
by Lemma 31 if we define (b( = コ 01 B.n
we obtain
V - 0%) s 27
1
0 0%
01+1
0%
0t
0%
Bi
B.
BB
(54)
By applying Lemma 33 we have
1
(,,(0/tt)) (,, I (le, (0)++))))+
0,01+1
0%)
0%
(55)
aish
where ogih = log | + 2(1 + Lup Lo). By setting 1) /2,n/2 and merging equations (54 and 55
we arrive at
(,,1(0 (0,) S (le,n(0ht))) Vlin (0++1
++++1
0%
+ 0
1
(10%
0% |
0% @
0
0%
Bin
B
B
(56)
Mcanwhile, obtain
(0)=
( 0%.
(57)
by taking the gradient over both sides of the Taylor approximation of (0). Using (77 to bound the first term of (56) as follows:
we proceed
V (l
Vean + A
1),0 0%
(VeLA( ((i,(())) - -V (0)))
0,+ 0-)
(D (0 11 [0%- 0 (0)t1 0,,,0 0*)
Ø 0 2
< <3/2L.p
01111
0%
(
< <3V2L
10 0
h
< 21
0
0
where 0/ a convex combination of 0% and 0%+1 The second equality arises from the Taylor expansion, the first inequality is due to the celf-conn property, and the final inequality is justified by the following:
"la,, (+1)
Σ
Ports (s') | shy af P.....
s'ES..
Σ Po 1hh a/, Pott sh ah Pi Ph
S'ES., 8'ES..
Pa (s') sh ah..phhhhhh
K'ESAA
3 L3 la.
44

---

By summing over i and reorganizing the terms, we arrive at the final result as follows:
00t11 -0%
B2+1A
ainh
(l1,((0) - ((((t))))) +
00
0%
11,6
k=1
+ 3v 3/ Σ aiih
00
0/112 Σ
0
0
B.A
&
2
4
S - la,(( + AL2 + 33
Σ
0 +
0
2
0%
B.
1=1
where the first inequality holds by Assumption 2 and the last inequality holds since a = logu 2(1 + Lo) 2 ai for all e [k].
D.1.2 Proof of Lemma 14
Proof of Lemma 14 The norm of 2,, -i (E <B.I.) lBB (9, generally un- bounded 227 In this proof, we utilize the smoothed version of 2,, defined as follows:
x o (smooth"", 15 Bo-N(0 lo (TT,,
where the smooth function smooth",, (p) = =(1 (1-u)p (u/L1)1 with [0, 1/2], and 1 1lS. an all-one vector.
Exploiting the property of Ji such that in (o (p)) for any E AIs it straightforward show that ž,, o (smooth",, (o (Z,, Then, by Lemma 34 we have
Σ ( vii) - Σ (Z whh) S 2uk, and 1 s log(U/u)..
(58)
Given the definition of b, we know that E(zi, s/ = (0%)) where zi, = D We can bound the gap between the loss of 0% and ii as follows:
(c.,(0%) - E(Z v())
(e(z),n. -E(zi, vi))
Σ
(V [V eli uh), "iin
||z|, - -2,
11
Min
1=1
V Ve
elzzz
Bh)) 25, ZNiN)
||
(59)
Mr.
1=1
where Min [og[[Se.] ( 2 log(U///) /u), and the second equality holds by direct calculation of the first order and Hessian of the logistic loss.
Now, first bound the first term of the right-hand side. Let di -2,,,, Z/,))/M Lo) where M logl/ 2 llg((4/u)) Then, one can check that ||di, llo I 1 since |izi,nloo S maxx'eS... Il.p.,..~ |l2 ll & Lo and | S log(2//u). Moreover, since 2i,n and 2 are independent of vi. d is -ea-uuasra.ble. Since El(or,, (orlo - vi) Fi, = Vor. (2), and o I (z),.) v Il < 2, we apply Lemma 32 For any & and E (0,
45

---

with probability at least --/H, we have
V el Uh), 2i,n )
k
= (M + Tup Lo)
V V=l(at drn) Σ
1=1
S (M + Lupba)
A
1 11
H
Σx == ||d | (B
VT
+
log
VX
HVT + 2h
S (M + IopTo)
A
Σ I (o
4lo
(60)
6
where the second inequality holds since ||d; Il Plugging (60) into (59) and rearranging the term, we get
d Vo (2,, S 2 and À Σ 1.
(l)) (( vi))
k A
VT
V1 + +
$ (M + Lo)
d (o
+ 4log
H
4
8
|2
2i 2 Vonn
Mis
VT + 4log
HV +
< (M + Lnp
A
| (
8
b
-M + Lo)
Σ
|| ||dg,nl
HvI+ 2h
< (M- + Lo)
A
Σ
| (ll
+ (M + Lubt)
4log
8
-M + Lo)
Σ ||d (
< (M LLLo)> 4(M - Lo) log HVI+ - 2k
(61)
8
Finally, combining 58 and 66 by setting 1/k, we derive that
Σ (0), ((2,,,
Hv1 27
7 (M + Lo) + 4(M + Lo) log
+ 2uk
8
5 1 (3og(((kk) + Lo) 4(3 log((kk)) + T.) (oo))oo
H H + 2k
+ 2
5
where the last inequality holds by the definition of M log 11 log(U/u). Taking the union bound over h [H], we conclude the proof.
D
46

---

D.1.3 Proof of Lemma 15
Proof of Lemma 15 We start the proof from the observation of Proposition 2 in Foster et al. 127 stating that Zi,n represents the mixed prediction, which adheres to the following property:
Ml vi) S log (BowN(0) (exp (-t,, - -log
exp (xp(-Li,n())
Zzih JR
(62)
where T.i,(()) (0) 20
0 B;
and 7i,h
(27)dec ceBBB B
Consider the quadratic approximation
(0) (0,, + ( (0 (0*+)),0 0 0(+1)
0
B.A
Using the property that l,, is 3y 2 sfnn function as asserted by Proposition B.1 in [50, and applying Lemma 35 we obtain
(0) & (0) + exp 181. 0 / 11))
110
0 ||
Also, we have
1
exp(
(i))
Zi,h
JR
1
(Li,N(0)- exp 18L2 0 - 00:t1 ) - 0 (e. d0
exp
Zi
Rdd
exp
(LLi,
(1+1,1(0) exp (-(VIn,n(0)t) 01t1) d0.
(63)
Zi,h
where we define the function
Fi, B(Oa, 1) + R
T1- = exp =exp
0
0
exp 1862 0 0₂ 0.-11()) --
0z (
2c
B.d
We denote Z = Iga F
h (0) do S too and define 1.41,6 as the distribution whose density function is S,+1,,1 (0)/ Z++ 1, Then, we can rewrite (63) as follows:
Zt,b (xp(-L,,((B))o de
(-Len(0htt) ZEtL
exp
E exp (-(VL,,(0) - --000,11))))))))) 1))
Ztn
(L ZitLA
exp
exp (LEp-rriaa (V 0z ));
Zin
(0)+1)
Zet1A
exp
(64)
Zi
where the second inequality is by Jensen's 's inequality and the last inequality holds because @ is symmetric around 0++ and thus E E..ö... [( (L -0-0) 0 0 0.
Combining
62 and 64 we get
l < (0 + log Zi, - log Z,4
(65)
47

---

Moreover, we have
log Zi+1,
log
exp Rd
0
2c
B,
exp
181
0++
0 0-1
d0
-
log
Z+411 B
exp
exp
18L 2 4
0 0+++
[2)
22
110
0i+1
(e )1)
< - log Z141. + E8
1812
0 0%
(1) |0
0
exp
(0
log Zi, + 1
exp
18L2
0i+1
2) |,)
0
0
(6
(66)
S exp
where 6/+1,1- NO cB and 2141,
h
d0, and the last
B.
inequality holds because 2441, and Zi, are identical normalizing factors. Integrating (65) and (66) and summing over yields
hZ v
& Σ B
+1+11 (0
1882
0 0bt 1):111)) ||0 - F (
exp
Moreover, we can further bound the second term on the right-hand side of (66). By Cauchy-Sehwand inequality, get
E 1.
1812 0
0:+1 112)
0
E B
exp
36L2
0 1[3)
E BO-ôr...
0 0
(1)
Since 0,41, N (0)t) cBB cBB,...
0 follows the same distribution as
cd B
X,ej, where X3 is.d. NOO, E [d].
(67)
1=1
where Xj B 1.4 of Rdd Furthermore, since we know that B B < A we can bound the term (I) by
denotes the j-th largest eigenvalue of B and (ci,..., ca} are orthogonal basis
d Ex, (exp (3612cA-1X33)
(I) < Ex; II exp (3612c1-1X3)
$ (x [exp (36I² cA - < Ew [exp 1
where x2 is the chi-square distribution and the last inequality holds due to Jensen's inequality. By choosing À 2 72L3,co cd, we arrive that
(T) < Ewax²
exp
S 2
(68)
48

---

where the last inequality holds because the moment- gennrrting function for x2 d-ddstibbuutin is bounded by Ew- [x [exp(tW) 1/v1 2 for all 1/2. Now, we bound the term (II).
(II) B
0
(B.N((..BB.))
|111 (
[1012]
-1/2
-1/2 Let X; := > (cBr,) be the j-th
where B. (v2
B
largest eigenvalue of the matrix. Then, similar analysis (67) gives that
27
(l))
Ex
Σ X
Ex
Exxx3
Non <
Xgyy V3c (Brh))
j=1y'=1
where the last inequality holds due Ex,.x, Xxy.X,,~N(00.. [33X3] < when considering the case where
j = j' and the last equality is derived from the fact that (E 2²) tr (cBr.h)) Here, we denote
tr(A) as the trace of the matrix A.
We define matrix R == ALa/2 + Ei=1 V (0++).)). Under the condition 2T we
have 2 (0.+1.)) 3 L la < 2 Lg. Then, we have B. 2 Ri+1A Therefore, we can bound the trace by
[ 11 i.h
ir B Ba (0+t1.))) s ir (R Ve (l1,n00+1))
det (et(R.+1,.))
R (R h RR,)) S log det(R,,,))
where the last inequality holds due Lemma 4.7 of Hazan et Therefore we can bound the term (II) as
det det(RR,))
III)
V3clog
(69)
Combining (68) and (69) get
det det(R.+1.))
E B exp 6
$ VBclog det (R,,),
(70)
Plugging 666) and 70p into 665.. and taking summation over derive that
& log
det (R,,,),,,)))
(Zz,,, vi)) x i=1
( (0, + B6
det(RR.))
1
)
det (R
01+1
+
0 B
+ /oc Σ
log det(R.,
2c
1=1
1
2kL2
(,, 1 ))+ +
0
0
Vocd log
1+
2c
Bi,
dA
where the last inequality holds because D log
det (e
(At s
det(R.
dlog (1+
2k13 dx
By rearranging the terms, we conclude the proof.
49

---

D.2 Bound on Prediction Error
In this section, we present the bound on the prediction error of parameters updated by ORRL-MNL. First, we compare the problem setting of MNL contextual bandits with ours and introduce the challenges of applying their analysis to our setting.
Perivier and Goyal [1] consider an assortment selection problem where the user choice is given by MNL choice model with the single-parameter. At each time I, the agent observes context features { C RR. Then the agent decides the set S [M] offer to user, with [Sy] S N. Without loss of generality, we may assume |Sa] = .N. Then the user purchases one single product j E S, U {0} and the probability of cach product is purchased by a user follows the MNL model parametrized by unknown fixed parameter 0* E R
MNL dynamic assortment optimization Seingl--paramete & uniform reward) 66
exp(x exp(x
j E S
qt. (s,,
kes, exp(x 0*)
if 0.
1+ exp(x; 0*)
Then the difference between the revenue induced by 0" and that by an estimator @ in Perivier and Goyal expressed as follows:
Σ JES.
(t 0*)
Σ (S, 0)
(71)
jES.
If we define Q : -R IR, such that for all (n) (.1,..., uN) E R.N Q(u) Σ exp(%)
I+ exp(uy)
and let v* = (x, 0" ""....,,x,, as follows:
x Tix 0*) and v = (x 0 ....., T 0), then Eq. (11) can be expressed
Σ JES.
9h (S,,
Σ (S,, -) Q(v")((v=)))))))())) -(())
JES.
= -QQ(v)) -v) +v+ 1 +2 v) V'Q(v((v' - -v), (72)
where V is convex combination of v* and v. For the first term in Eq.
72 we have
VQ(V") (v* v)
Lies, exp(x,, 0²) (0) U2) Eies, exp(x.,, 0') exp(x],00'(() - vz) Ejes, exp(x,,00)
1++EEE, exp(xI,
= Σ
9t (S, 0" )xTx -0 ΣΣ JES, iES,
(S 0 (S,, 0²) (x, (0"
JES,
Σ
9t. (St, 0*)
1 E nr,1 (S, 1*)
00)
JES,
iES,
Σ (S,, 0" (()),,(SS, 0 xxT, T (0' - 0)
=
JES;
< Σ (S,, 0" )9, 0" | | (0.) -10 - 0 H,,0'))
(73)
JES.
where H.(0) is the Gram matrix used in 61 defined by
H0) Σ
Σ JES.
9ru (Sr 0" x")xx
(no(Sr, 0" (S,, 0¹ 0')=,x] Σ JES, SES.
Σ
Note that the term timated parameter.
|0" 0 (l) can be bounded by the concentration result of the es- On the other hand, to apply the elliptical potential lemma to the term
50

---

Ejes, (S, 0² (s, 8*) xx) (0-) note that H, (0") can be bounded as follows:
H²))")
=H,-1(0") + Σ (S 0² 0'xss
Σ
(r 10,,00' (S:;,, (x1,xx,, + (x.)
jES.
WES.,
1
- + Σ
(r.s(S 0") وبر
(t 0² (S,, 0*) (xL,zx x(,
jES,
LJES
-H,-100") + Σ (..(S 8-) (1 11-11111 qe..(S 10) Xل,
JES;
-H,- +
Σ (S, 0" (,, 0* X
(74)
Now since the coefficient gt..i (S,, 0") (r (St, 0-) of ||X|| H, (e-) in Eq. (73) aligns with the coeffi- cients of the lower bound of H, (0") ) in Eq. (74), the elliptical potential lemma can be applied. Note that such a lower bound in Eq. 74 holds since Perivier and Goyal [6]] deals with the uniform reward, i... 1 Eies, (S, 0*) or ( 0*).
Zhang and Sugiyama 776 address the multiple- parameter MNL contextual bandit problem where at each time step t the agent selects an action X₁ E I and receives response feedback Ye E {0} U [N] with N + 1 possible outcomes. Each outcome i E [N] is associated with ground-truth parameter 0, E R and the probability of the outcome Ply: i x,) follows the MNL model,
Mulitinomial logistic bandit problem 766
Pl = i x²) = exp(xx 03) + exp(xx
N
P(y= = 0 x.) = 1 Σ
P(ye = xx).
In this model, there are N unknown choice parameter O* @² := (o....., 0 E RdxN and the agent chooses one context feature that is why call multiple-paramett MNL model. Then, the expected revenue of an action X₁ in 76 is given by
N
exp(x, 0.)p:
= ====((0'x,)
E exp(x] 07)
where we define the softmax function R... - [0, 1] by
exp([z]:)
[z(z)] 1 1 ΣØ=1 (xp(
VK E [N] and [a(z)]o
Vk E [N].
1 Ej exp((z),)
and p:= [p....., pNl E R N+1 represents the reward for each outcome j E [N] with Po = 0. Then,
the difference between the revenue induced by O* and that estimator θ in 76 is expressed by
P )(xx)))
Σ ps (0(00),))]+ - -
Σ Pk (Vlo((xi)la)
(0) -0-- - + Σ Pk ( -)xx
(75)
k
51

---

where E - - + + - x) Then for the first term in Eq. 75 we have
Ph (((r(( (0r -
@x - @)x
p (x (IN x (vec(O") vec(O))
vve((*) vec( H. H
(IN 6 x (xxx))
(76)
where H; is the Gram matrix used in 76 defined by
H. AIN
Vo ( @ X
Note that the term ||vee vee(@)) || in Eq. 76 can be bounded by the concentration result of the estimated parameter, and the term ||H (IN @ x, (xxx))) also can be bounded as follows:
H x
@ Vo - H, (IN @ x (xx.)))
Here Zhang and Sugiyama 766 bound the term H (IN xx Vo using matrix version of elliptical lemma. However, they assume ||p|| - (Assumption (76)).
Now, regarding the prediction error in our setting, the estimated values (V/+1 (-)) for each reachable state typically distinct, and we do not assume constant upper bound on the E--norm of the
estimated value vector for all reachable states. Instead, we can bound the f--norm of the estimated value vector for all reachable states follows:
VI 1 S max S'ES,.a
( ( SSaal S HVU,
where VA (8, .)
V ( VES,
E RlSS.al, However, such bound leads looser regret
VES,,.
by factor of Vu. To address, we adapt the feature centralization technique (50] bound the prediction error independently of U, without making any additional assumptions. The key point is that the Hessian of per-round loss (0) is expressed in terms of the centralized feature as follows:
Σ Pols' s at (ss of s': (':0)((s) ai s²:
S'ESu.
where (ss,, a, 8'; = : s, a, 8' provide the bound on prediction error of the estimated parameter updated by ORRL- -NNL.
Eg- Pa(: Po (sss, a, 3)] is the centralized feature by 0. Now,
Lemma 16 (Bound on the prediction error). For any E (0, 1), suppose that Lemma 12 holds. Let us denote the prediction error about 0% by
(s) = Σ
(sa(('1 (s,a) Poz (s' s,a)) (
S'E
Then, for any (8, E x A, we have
( a)l S H3x(0)
Σ
Poy(s' s, ( 1771
+ 3x)2 max || 1|9,,.,'' B s'ES..a
e'ES...
Proof of Lemma 16
Let us define F(0) Eves., Pols' 8, 5 Then, by Taylor expan-
sion we have
F( F(O):)
VF T.:
0 0 (=F(()( 000)
52

---

where 0 = (1 -1 0 + 20% for some v E (0, 1). By Proposition
|
we have
VP(0)= E
E'Ea.a
Σ
Po(s' 8,0) (ssaa'' Σ
Po(3 8, 8,0))9,a.3
Vot
e'ES,,a
SES...
Σ
Pols' s, s (0) (5))
S'ES,
and
FFF(0)
Σ P'Po(s' (o((s'ss,a)1)) s.a)
S'ES..
E Pols' V. (5)) (s)))e,,,
S'E
Σ
Pols' ss,a)
s'ES,,a
Σ
Po(s" 8,a) (4 v Poa,e" + "Paa + 2e Peaa )...)))
E"ES..a
+2 Σ
Po(s' 8, s,
8'ES..a
Σ
Pols"
8, 8,
Σ A'ES...
Pols" s, s.a)ypma.s"
S"ES,.
Then, the prediction eтrоr can be bounded as follows:
A = (F(0%) F(Ot))
I VF(O)) (0) 0%) + 0 -k;-0, T' - -07)
(77)
For the first term in Fq. 77
VF T 0%)
Σ Par (s,0) (0) 0 0
D'ES...
< H Σ Pa s,a) Pan (+5) B
10 - 0%
Bx.b
s'ES..a
< (8)
Σ s'ES.
Porls' s,
Peaa (0%)
(78)
B
where in the first inequality we use VA (8') S H and Cauchy-Scharvy inequality, and the second inequality follows by the concentration result of Lemma 12
53

---

For the second term in Eq. 77 since 0 I V (5') S H,
(0)
V2) 0%)
< H Σ Po s,a) (10 -0%) "'s,,,))))
s'ES.
H
Σ
Pols' 8,
8' E'ES.,n
Σ
Pols" (s,0) (0) 0%) (Pean P (0) 07,)
SEES,.a
+
Σ
Pols' 18))
E
Po(6" (,,a) (0) 07) - "Pa...)))
s'ESr,a
s"ES,.
Pols" | s.a))p....r)) ))
+HH
(0) 07)T
Σ
8"ES...
< H Σ
Pold' 8,,))l4,,,,
0 0% Br,b
Bil
8' S'E
H
Σ
Pa(s' s,a)
E'ES..a
Σ S"ES
Po(s" s. (0) 0%) (Dsn + " (0) -07)
|B Bil 0 0% 1
Σ 8"ES,,a
Pa(s" 8, 88
Be.a
+2H
Σ
Pols" |s,a)l
Br1
0 - 0%
(79)
Be,
s"ES,,a
where for the second inequality we use Sauchy-Schward inequality, xx +yy 2 xy + +xx for any x, E Rd, and triangle inequality. Note that
H Σ
Pols' ss,a)
s'ES.a
Σ
Pols" (.))) T (De.a + ( (0): 07)
&'ES,,a
H Σ
Pols' ss)a) ((0) 0%) "p..a.e)) )²
2
s'E
2
Σ
Po(s" (8,a) (0) 0 T ",,,,""'
+
e"ES,,a
2H Σ
Pals' s8s))lllss.....
1 ! 0
0%
(80)
B
8'ES..a
54

---

By substituting Eq.
80 into Eq. 79 we have
v2 (() 0%)
< 4H Σ
Pols' 8, a))lls,,. sa, B
0% 0% Bx.
e'ES,,a
+2H
Pa(s" 8, a,)alls,,,,
0% 0%
Ba.b
$"ES,.a
2
max 4H3
1B B
+ 2H
BBx max s'ES,,
1| llB.h
s'ESa,a
< 3
max SES,
lle s, 1 B
(81)
where for the second inequality follows by Lemma 12 and Eess., Po(s' s, = Combining the results of Eq. 778 and Eq. (81) and, we conclude the proof.
D.3 Good Events with High Probability
this section, we introduce the good events used to prove Theoremaann show that good events happen with high probability.
Lemma 17 (Good event probability). For any K E N and E (0, 1), the good event ((K, 6') holds with probability at least where = H)K..
Proof of Lemma 17 For any E (0, 1). we have
((K,8)) = N n (x,)
N ASK A
n
B (8)
RSK N
On the other hand, for any h)) E [K] [H), by Lemma 30 Φ (8') holds with probability at least
1 8' Then, for 8' 6/(2K H) by taking union bound, we have the desired result follows:
P( 8')) 2 (1 - 8)2KH 2 HK = =1 1
D.4 Stochastic Optimism
Lemma 18 (Stochastic optimism). For any with 0 < < ((-1)/2, ler or H3x(0). If we take then for any [K], we have
multiple sample size M = log (11)
log( HE()
( -
2 0 sf. ž 22-1//2.
Proof of Lemma 18 First, we introduce the following lemmas.
Lemma 19. Let 8 (0, 1) be given. For any (k, h)) E [K] x [H]. let o% = (5). If we define the event @ (8)
s (d) (d) = a)) (3x(8)
Σ
Por(s' s,a) (...
B
S'ES,
+ (3) max s'Er,a
||ps.a.
1| B
then conditioned @ k. (8). for any (s, E S A, we have
P P 2 20 (0) > - M
55

---

Lemma 20. Let å E (0,1) be given. For any (h E [H] x [ let o% = H3x(6). If we take
multiple sample size M [1 we have
lug [H)) then conditioned the event @ (6) = Cheler 6 (,,
1og
P (- an) 2 0, [M] ()) (-1).
Based on the result of Lemma 20 using the same argument as in Lemma 6 we obtain the desired result.
In the following section, provide the proof' of the lemmas used in Lemma 18
D.4.1
Proof of Lemma 19
Proof of Lemma 19 Recall the definition of Bellman enror (Definition T. we have
(s,
()) - (r(s,a) + Ps ve (s.
min (r(s.a)+ + E Pos(s' (,a) + v vond (5.00) (r(s,a)+ + (.
s'ES,,a
2 min Σ
Po (s' 18,0) Pa Vhe Vhtt + (snd (s,),,)
yand
d'ES...
Then, is enough to show that
Σ
(o (8,68 (5)) Pn P as + v v (s, 2 0
S'ES
least with constant probability. On the other hand, under the event @ (8), by Lemma 16 we have
Σ (s ss Pa V. (s, a) + khh (s. a)
()(s, + 1khh
(s,
(0)((0) Σ Po 8, (eaa
Brl
S'ES,,a
(8)2 S'S.
max
Br
+ vkh
(s,
Σ (s s, s,
(0%) Eh (8)
(T
Σ
(s s,a) Pen. B
s'ES.,
s'ES.
Note that since < N0O k.)). follows that
as Oh T (m) ~ N (0. Paayo (0%)
(0)))
Vm E [M].
B.
Therefore, by setting σ = (8)), we have for m [M] and s' Sa.r
P P
S 2 (8)
(m)
P Paa. B
((-1))
56

---

Recall that kk em((') where m(s') argina Ps Psia,
(m)) SE
Then, we can deduce
P
Ps Ps. ( Ek 2 (1)x(d) (Pe.. B
P
max P Ps.a, mE[M
T 2 HBnx(0)
(0%)
B
9 a (0%)
< (0)
vm [Mr]
Bx
2 1 (1 क ( 1)) 1 (1)
(82)
Consequently, we arrive at the conclusion as follows:
IP( (1-))(8,)) 20 (5))
P
Σ
Pap
(s,a) Pa (AV + ( 201 (0)
S'ESa,
2 P
Σ
Pos s Ein
(83)
d'ES..
2 H3x(0) Σ Pap s,a) (oaaa
B
s'ES.,a
2 P Φ Peass (0%) T Ehi 2 H3k(0) (Pam
Ao E S,aa
(T,A (5)
Br.h
(35' Se s.t. a P
|| 10a00 (0%)
(0)
Bich
UP (8sa. (0%) (,3 (100011ex.0 (e..
(0%)
18
(R.1((0)
(84)
Br,
(1
(85)
where 84 comes from the fact that maxs, SS, = 24 and the union bound, and 85 follows
by
82
D.4.2
Proof Lemma 20
Proof of Lemma 20 holds
(- an) 2 0, e [H]) = (3h E [H] s.t. - (5 an) < 0)
P
2 HPP (- an) < 0)
> (1)
2 (<-11)
where the first inequality uses the Bernoulli's inequality, the second inequality follows by Lemma 19
and the last inequality holds due to the choice M = [1
log(L4
log ((1)
D.S Bound on Estimation Part
In this section, we provide the upper bound on the estimation part the regret: E (V+ Lemma 21 (Bound on estimation). For any 8 10, if À OLL dog U), then with probability least 6/2, we have
Σ (Vt
VT (st) = Ō (
57

---

Proof of Lemma 27
With the same argument in Lemma 10
we have
- (())
Σ
(s a +
(86)
where ch = Pr. - aa)) - (V/i1 Vitta (+tt)($(42)) Note that
-1 a = Qh (sh alp - (r(sh a/) + Ps Pa (ot at:))
Σ Pap(s' 1hh at V/+2 Pr. 1 ah) vand (s ah)
a
A afl unand (sh:aat)
H Σ
Por (6 1// aa) (p.h
+ +3H3 max
11 B
B e'E
d'E
+ vkS (sh: ahi)
(87)
where the last inequality follows by Lemma 16 Now we introduce the following lemma.
Lemma 22. For any hk) E [K] [H] and (8,a) E S x A, it holds
Σ
Poc(s' 8, 0, (0aa B
S'ES..a
< Potti(S' 8, (.a))Ipa..
16p
|
(0)+t) (0k+1)
max S'E
1
s'ES,,e
By plugging the result of Lemma 22 into Eq.
87
we have
- (sh dft)
5 113x E
i (5') sh a
ab)
B
S'E
+ H3s
16
max S'DA
12
+
3H3
max S'ESL
11 B +
rand (sh (s at)
B
< Hip Σ
P P
shi aft)
P (0+t))
B
s'E
(s s/y Pw.. T
T
+ H&
16
max S'E
(0)
g0++1) 1
+ 66
3
max s'ESkh
1
Bat
By letting denote
(s,
16
max S'E
(0)+1)/
+6H 88
max 11 e'E
(88)
VX
B
58

---

and summing over all episodes, we have
K
K
H
K H
Σ
)(+)
= Σ Σ
(s
a +
+EX
Sh
km h
Amm
H K
ΣΣΣ
Par+ (s') |oh; att I (0%+1)
B
1=1 &
(1)
E
Σ S'E
Po
(s'
syy Pk. (0%) TE
(ii
K
K
H
r (s
(89)
Note that Σ Em Evesun is hereafter abbreviated Ex.h.
For term (i), we have
Σ
Pa Popti (s') sh att | (0
B
k.h,
Σ k.h.s'
P Patet (o' s/ att
Σ k.hi
Poit (s') ati
| (0h+2)
B
11 K
VT
Σ
Popt2(0') I sty, at) |0h (1)-))
Bi,
1=1k=1 E'Eu
(1+
KULL
S STV220
2Hdlog
(90)
dA
where the last inequality follows by the following lemma:
Lemma 23, For each h E [H, if 2 EZ then we have
KUT.
ΣΣ Po sht at) (0++1)
S 2d
1+
B7l
dd
k=15'E5k.
Then, term (i) can be bounded as follows:
(i) = H3K ΣΣ E
Potti sh at) (0%
B
11kEl F'ESL.M
kuLL
< HBK VT, 2Hdlog
d)
= O(
(91)
For term (ii), we introduce the following lemma:
59

---

Lemma 24. Let E (0, 1) be given. For any (k, E [K] x (H] and (s, E S x A, with probability
least 6, it holds
E e'ESra
Pok (5'
(8,0)) (0%) T
S (d)
Σ s'ESun
Pottils' (s' sy ah)
BR.h
16
P (0%+
(1++1
max d'ESe,h
VX
Br
where (6) = Cear / (log(Md/j) for an absolute constant Cg > 0.
By Lemma
we have
Σ kyhi
Pog
(s' sh Pk. (0%) T
$ (0)
Σ
sh ah)
P (0%+t)
B
k,b,
+ 16
K
11
/
1P.m.00pp (0%+1)
max S'E
BT,,h
k= A=1
I (x)
V
20d
1+
KULZ
16
K H
max E'u
(0h+1)
1/2
d)
Br.h.
Rm
(92)
where the last incquality follows by Eq. (90).
Note that
max E
Pk.
(0)
K
max VESt
Pk.n. (0)
(0)
A
K
Σ
Pk.h.s
S'
SESk.h
A
211spu, +2
Σ
P
Pat+1 (3 sh at..m..
d'E
SESo
K
H
K +2
max S'E
1|P
AT,
> Σ
Σ
P ah, Ag
A= h=1
A= h= 3ESt.
K H
max s'ESk.h
|| Ar...
k=1 1=1
KUL
< 16x 16x dH log
1+ dA
(93)
where the first inequality holds since B 2 A the second inequality follows from (x + y) < 2xd + 2y²,, and the third inequality uses the triangle inequality, and the fourth inequality uses
ExESEA P p (s st a 1, and the last inequality follows by Lemma 3 By substituting
60

---

Eq.
993
into Eq.
992 we have
(ii) S xk(o) VT V 2Hdlog (1+ kutz//da)
25 dd log (1+ /
VA
1 /T - -d0/2 11²)) For term (ii))
(94)
Σ
Σ
(
a
K
H
16
2
HBk
VX
max S'
Pk.n.s (0h (0++))
B
+
+6H3
max s'ESAA
11 11
Br,
#= h=1
16 < HBK
K ΣΣ,
K
max S'ESA.A
( g0t+1)
(0)+1)
max E'Ee,
1| A
k=1 1=
k= h=1
256 x dH log (1 /ul,,/(X)) + 24k dH2 8 log (1 + K /dd))
S SK
VX
=
(95)
where for the second inequality we use the same argument used to derive Eq. 93 and Lemma 3
For term (iv), since we have K S 2H and E FR.a] 0, which means (ch Fu,AJR, is martingale difference sequence for any k [K] and h E [H]. Hence, by applying the Azuma-
Hoeffding inequality with probability at least 8/4, we have
H
ch s 2H log(4)))/)))
(96)
Combining all results of Eq.
91
94
95
and 96 we have the desired result.
K Σ k=
vT 8/2 3/2 /2 1122 + HVVT)
-
-
In the following, provide the proof of the lemmas used in Lemmal 21
61

---

D.5.1 Proof of Lemmal 22
Proof of Lemma
22
Note that
Σ
Ps s,
(Ps.a. (0%)
B
P s,
(0
B
s'ES,,a
|
p, (0%)
Pr 10%
ge+11
B
x Σ
Pottils' 8.0)
P Pa Br,1h
s'ES,,a
(Pp((' 18,0)
Par
(s' P
(s)
P (0)
B
8 VES
Σ
Peo,, (0%) 4 (aa.0
B
S' S'ES,.a
where the first inequality holds by triangle inequality. For (i), we have
(i) = Σ
(s,a) (Ø): - -0%+1) (0.00
B
8'ES..a
<
Σ s'ES.,a
PP s.a))lBB). 0
@h+1
(0)+))
(1++1)
(97)
Bi.h
B
where the equality we apply the mean value theorem with 0 0 + (1 v) 0 for some E [0, 1], and the inequality follows by Cauchy-Sehwarz inequality. Meanwhile, since we have
Par (5' ss (raa (0))))
Poz (s" s, (.,)) (0th))
(98)
8lf ES...
Σ BES..a
Pak+1($ s,
P Pgk+1($ |s s,a) 1)
Σ
Pas (s" s,a) Psa.er
8'ES.,o
Pac (s') ||sss (8,a)44
Poy(s' (s,a)
Σ Pas+1($ s, a).....
BeS..
-Poy (8)1,)))))
Σ Por(s" 8, (8,))4s,a,.""
s'ES..a
+ Poyy(' (
Σ Pox 10,0)
Σ
P 1 s,
8"ESS.
Pog (s') (88,)9ssaad Poy(d'l 18,0) Σ
(5" | 18, 18,0)
s"ES..a
VP s,
62

---

by substituting 988 into 97 we have
(1)
< Σ
{l|Po (5' 18,a)peaa.r00
e'ES..a
- Po (,,a)
E
Poz (6" 8, 88,)) (1
6"ESr,
0% 0/:t1
G Pa (0++1)
BR..
B3 k.
Σ
Paz (5' (s
|||||| (
0%
0%
Br
e'ES,,
2
Σ S'ES,
Po 8,0)
(0t
0
0
(99)
B
BR.
Note that by Jensen's 's inequality, we have
Σ Po 8, (.a))leaa0000 (0+
2 )²
(Ey (( (1aaa)
||0aa00 (0 (0%
2
B
B
8'ES..a
||| | (0h+1))
Eer Pp (11,a)
B
Pay 8,a) | (0)+1)
s'ES.,a
(100)
Also, we introduce the following lemma:
Lemma 25. For any ls E [K] and h E [H], the following holds:
|
0%
An VT
Bin
Then, substituting (100) into (9), we have
(i) 2 Σ Pay (,,0) (
0
06+1
B
BR.
s'eS..
81pLup
Σ
Poy (8' (0 Rai (0h+1)
Vx s'ES...
1
8qpuup
2
max S'ES...
P (0)+1)
(101)
Br
where the second inequality comes from Lemma 25 and the last inequality holds due to Eves,. Por(s' (s' s,a) = 1.
63

---

For (ii). we have
(ii) Σ
P 2ak(6 (6' 8
(,,,,. Peaa (0%+1))
E
Es PenPag(-aaa [4 - E9 S ght (11,00 [Ps (s ss)))
s'ES,,
B
Σ
(3 8,a) P 0 8,a) s
SES.,a
B k
Pot(( 8, 10 (Pr.a,3
Bo' Pott potti (1e,0) [ps
FES..a
Bay
P a, 1 s, 0s.a,((th
RES..a
Snp
2
max <'ES..
(as.a (0)+1)
(102)
VX
B
where the last inequality is obtained through the same argument as used bound (i). Combining the results of Eq. (IOT) and Eq. (02). we have
Σ
Pok (s' a, Pe.., (0,h
B
S'ES,.a
16
Pocti(s' (1,((s1ss)app)))))))( P (1(+1)
(0)
+
max e'ES,.
Bz
VA
s'ES,,a
D.5.2 Proof of Lemma 23
Proof of Lemma 23
Note that
BR- BAN Σ P s at) (0 ( (0, +
S'E
= B +
Σ
( 10 (0
s'ESp,
where we define Pk,,, (0h+1)= =
Pot+1(8' Pk. (0+tt). Then, we have
det del(Bee1.)) = de((BaA))
I B
Σ
(0+t)) ( (0h+2) ( B
s'ES2,A
= dde((Be.))
1+
Σ
(1++1)
B
S'ESk,
K
= det
II
Σ
(
(0)+1))
(1++1)
B
1=1
s'ESk.
Taking the logarithm on both sides yields
log det(Bx+1.A) del()
K
log
1+ Σ
(0t
(0%+1)
k=1
S'ESa,n
64

---

On the other hand, since À 2 L.p.
Σ A
Pk.h. (0x+1)
12
skih.
(0%+1)) (k
Ba
5'E
Σ
X Pot+zis' s ah) (kn
s'ESu.
L
$
P 1 | shh
S'ELE,
S 1,
where the last inequality uses EveSEA for any 2 E [0, 1]. it follows that
P P P (8' 11/ 0%) = 1. From the fact that S 2log(1 + 2)
k
log
1+
Σ
(0
(0
B
e'ESE
#= 1
s' S'E
Finally, we obtain
K Σ
K
S 2
log 1
Σ
B
BR
Rm 1 of SS.
s'ESa,
del del(Br+Ip
log
dot(ALa)
KUL +
$ 2d
1+
dA
where the last inequality follows by the determinant-trace inequality (Lemma 28
D.5.3 Proof of Lemma 24
Proof of Lemma 24
Since
(m) Sk
NO,, o BB by Lemma 30 for each m E [M]. we have
||
(m) k.A |BL S Ceax dlog
Following the result of Lemma
22
we have
Σ
(s sh a/t
PPa.. (0h)
<
P
s D (0h+1)
B
B
S'
S'E
16n
max (0/+2)
VX
S'E
1
Then, we obtain
Σ
(s sh, Pk., (0%) T
8' S'E
< Parls' // atti 1eannor (0
Il
Bich
s'ESp,n
Cean Volog(Modd
Σ Po 1 af
(0
e'ESc,n
78)(8)
Σ
P (s' afii
(aain// (0)t1)
B
NES.
16
(0)+1)))))))
max s'E
VX
Br,
65

---

D.5.4 Proof of Lemmal 25
Proof of Lemma 25 We provide a proof for Lemma of [6.. From the definition, we know that
25
since it is slight modification of Lemma 20
0
+1
Ee, (0%) + 1 0
0%
00%
21
Ba,
By rearranging the terms, the following holds:
@k+1
0 1
0
Vla.n(0%)
21j
BE,
g++1
Venn (0/)
h
Ba.
Brck
Thus, we get
0 g++1
0
$ 2m
Vlan
BA
Br.h
Since B 3
B and B k.
x
-
Ida we obtain
0
0%
0 t
S
2n
(
27
4nLup
BE.
BE.
B
VĀ
(103)
For the last inequality of (003) provide the upper bound of no-m of (.), Since
Eu.A (0)
Σ
wh')') log Pa ak),
d'ESe,n
the gradient of the loss function is given by
Σ vi
(s')
Σ
Po(s"
S'E
e"ESu.
Σ
sh")
Pols" sir s,a
Σ
sf E
S"ESkI
S'E
Σ
Pols" | ah.ahhe ah
Σ (h(s')sp,na
s'ESkI
Σ
(Po('') ath - -hi(s')) 4 Ds.a,s'
8 ESE
Therefore, we have
Σ S'ESu.h
(Po(s') sh - (1((s) ssaa
=
|Poss aht) - -f((s))) 1era
s SE..
< 2Li
and this concludes the proof.
D.6 Bound on Pessimism Part
In this section, provide the upper bound on the pessimism part of the regret: Σk - (st)) Lemma 26 (Bound on pessimism). For any with 0 < < (-1//2 let σ = H If =
(Vi
OLL2 and we take multiple sample size M = [1 1 6/2, we have
log HU) (og(H()
1, then with probability at least Tog +b()
+ Σ (Vi - v/)(st)) 5 = +
66

---

18 by using multiple sampling technique we show that the optimistic randomized value function V of ORRL-MNL is optimistic than the true optimal value with constant probability Hence, with the same argument used Lemma [T we can show that the pessimism term of ORRL-MNL is upper bounded by bound of the estimation term times the inverse probability of being optimistic, i.e..
Proof of Lemma 26 As seen in Lemma
VI (st)s
Σ k=1
Vi V/ (sf)
Φ $(-1)
D.7 Regret Bound of ORRL-MNL
Proof of Theorem 2
Since both Lemma 21 and Lemma 26 holds with probability at least - 5/2 respectively, by taking the union bound we conclude the proof.
E
Optimistic Exploration Extension
In this section, we introduce UCRL-MNL+ (Algorithm which both computationally and statis- tically efficient for MNL-MDPs with CCBB-asee exploration. The main difference compared to ORRL-MNL is that UCRL-MNL+ constructs an optimistic value function that is greater than the optimal value function with high probability. At each episode k E [K]. with the estimated transition core parameter 0% for (s,a) A, set
a) O. For each h E [H]
(+ = rs) +
Σ S'S...a
opt (s a, (6') + KK (),
(104)
where (s) = min A (5, o), H} and M a) is the optimistic bonus term defined by
opt (s) = HBk
Σ
Ps s.a)ll((s,a s 0 B + 3H
max 11y(ss, a, B,
s'll
&'S
S'ES...
Based on these optimistic value function Q each episode the agent plays greedy action with respect to Q) as summarized in Algorithm
Algorithm 3 UCRL-MNL (Upper Confidence RL for MNL-MDPs)
1: Inputs: Episodic MDP M, Feature map &p S A S Rd, Number of episodes K,
Regularization parameter X, Confidence radius {3x Step size 17
2: Initialize: 0) 0,, B 1. AI for all h [H]
3: for episode k = 1, 2, ... K do
4: Observe st and set (x-))))
as described in (104)
he(m]
5: for horizon = 1, 2....... ... do
6: Select at argmax .E Q (s a) and observe s
7: Update BA, B + 2 2 4 h (0t) and 0/++1 as in (5)
8: Update B = B + V L @1)1)
9: end for
10:
end for
The main difference in regret analysis lies in ensuring the optimism of the estimated value function Q) (Lemma 27p. In the following statement (formal statement of Corollary 1b. we provide regret guarantee for UCRL-MNL+, which enjoys the tightest regret bound for MDDs.
Theorem (Regret Bound of UCRL-MNL+).. Suppose that Assumption 1 hold. For any 5 E (0.1). if we set the input parameters in Algorithm X dogg 8g O(V log(kkH)
67

---

Ollog(), then with probability at least - 8, the cumulative regret of the UCRL-MNL+ policy π upper-bounded by
Regret, n (K) = ( +f
where T K.H.H. is the total number of time steps.
Proof of Theorem 3 By Lemma 17 suppose that the good event ((K, 8') holds with probability at
least 1 - 8. Then, we show that the optimistic value function 2% is deterministically greater than the true optimal value function follows:
Lemma 27 (Optimism). Suppose that the event (6) holds for all k E [K] and h E [H) Then for any () E S x A. we have
(h(s, a) S as)
Conditioned on 8'K,8"), by Lemma 27 we have
(VT - 1/"""" (sf) Qi x" (s{)) Qi a1)
S x - Qi (sf) at)
s (+ - oi (st at) = (s (sf. + P1 - V/2
Note that
(V/2 '/2" (s čt where we denote c = h++11 ( Es [V//+z v ($) argument, we have
P1 V22 (s) a = E3 at [1/ Vē (3)
Then, with the same
- - VT (s
kih (s ahti) +
opt
h=1
h=1
By summing over all episodes, we have
Regret, (K)
opt k
sh a%)
(105)
k= 1=11
On the other hand, note that
K
H
k.h he a
opt &
P
His Σ
Pog (s'
Px, (0%) MB
3H3
max 2'ESshh
||
R=1 h=1
e'ESt,h
k=1
H3K
Pos(s' shi at (0/))
h= s'
22 +3H
II 1B21 ES
PK
max
k=
H
< H3K
Σ
Patta(s' sh, at)
(
(+++1
B k.h
S'E
16 H3K
K H
max VESE
(0) (0)+1))
3H B2
K H
max o EES
Br
Jomn 1
Amm hm
(ii)
(iit)
68

---

where the last inequality follows by Lemma 22 Term (i) be bounded in Eq. 991
K H
HBK
ΣE
Σ
P
i
(8'
lo ab)) (0tt))
=
Ö(dH3/2
(106)
13
For term (ïi,, recall that as in Eq. 993 we have
KULL
max S'
11x--1-dd HH log
[+
dd
k=
Then, have
1
H
H3K
max ESEr
( (0++1)
=x -dH))
(107)
s
B
For term (iii), since we have
3133
max S'Ssh
IlB S 33133
max S'&
| Ax
k=
$ 12k dH''" 3 log (1 + /ULL///d
Ok= H²)
(108)
Combining the results of Eq. (166. 107 and 108), we have
H
( x
/
k.h
Finally, by Azema-Honfiiding inequality as Eq. 96
we have
K
H
O(HVT)
This concludes the proof.
In the following, we provide the proof of Lemma 27
E.1 Optimism
Proof of Lemma 27
We prove this by backwards induction on h. For the base case = H, since
V8+1(8) V/+11( = 0 for all E S, we have
(), r() ())
69

---

Suppose that the statement holds for h+ where h E [H - 1]. Then, for and for any (s. E SxA.
(s))))
= +
Σ
Por
(s,aVV+t1($$ + kkh k. ())
rr(8,a) +
Σ
Por (0 (8.0)
+ 20 (s.
8'ES,aa
= +
Σ
Po s,a)
s'ES,a
+ Σ
(op s,
vpt ()) (s) - PP: (s' (s,)) ( +
opt
S'Eo
r()
Po 8, V++
S'E
= (s,
where the first inequality follows from the induction hypothesis and the second inequality holds by Lemma [6
F Experiment Details
0.4
0.6
0.6
0.6
0.35
0.35
0.35
(1,r
1000
81
0.05
92
0.05
0.05
8n-1
0.4
Sn
(0.6, r = 1)
Figure 2: The "RiverSwim" environment with states 588
The RiverSwim environment (Figure 2 consists states that are arranged in a chain. The agent starts in the leftmost state with relatively small reward of 0.005 and aims to reach the rightmost state, which has a relatively large reward of Choosing to swim to the left moves the agent deterministically to the left, while swimming the right has probability of transitioning the agent toward the right state, but also a high chance of remaining the current state or even moving left due to the strong current of river. Therefore, efficient exploration is crucial in order to learn the optimal policy for this environment.
We fine-tuned the hyperparameters for each algorithm within specific ranges. Figures la and Ib show the episodic returns the RiverSwim environment over 10 independent runs with S 4, H 12, and K = 10, 000 and |S| = 8. H 24, and K = 10, 000, respectively. The shaded areas represent standard deviations (1-sigma error). Figure Tc compares the running time of the algorithms over the first 1,000 episodes. All experiments were conducted on a Xeon(R) Gold 6226R CPU @ 2.90GHz (16 cores).
G Auxiliary Lemmas
Lemma 28 (Determinant--rrcc, inequality (... Suppose Xi,...,X4 Rdd and for any 1 S $
|x+||2 5 L. Let V, Ala + Σi= x for some X > 0. Then,
dct(V.) S (A + /Ly/
Lemma 29 (Freedman's 's inequality (29). Consider a real-valued martingale (Y: : = 0, .,..
with difference sequence (Xp k = 0, 2, 3, Assume that the difference sequence is uniformly
70

---

bounded, Xx S R almost surely for k = 1.2,3.... Define the predictable quadratic variation process of the martingale:
k
WR =
Σ
E, Ex-1 for 1,2,3....
j=l
Then, for all 0 and 0² > 0,
-t12
IP (3k 2 0: Yx:Y3 11 and W S 2 S exp
02
Rt/33
Lemma 30 (Gaussian noise concentration (Lemma D.2 in
(7 Let g(1) _ ,..,, E (M) be M
independent d-dimensional multivariate normal distributed vector with mean Oa and covariance a² A for some a > 0 and a positive definite matrix A -1, i.e. g(m) NN o2 A- for m E [M].
Then for any E (0, 1), with probability at least 1 - ó, we have
|| a| S ((oov ==
max ME[M]
where Ce is an absolute constant.
Lemma 31 (Proposition 4.1 of 15). Let the w4+1 be the solution of the update rule
Wi+1 arg min (/(((w) + Do wt).
wEV
where V C W C Rd is a non-empty convex set and (w w2)
wi
w2) is the Bregman Divergence w.r.t. a strictly convex and continuously differentiable function
bb : W - RR. Further supposing (w)) is 1-strongly convex w.r.f. a certain norm || in W, then there exists a 9t E (1,4w))1) such that
(NiS'e W1+1 u) S (Vu(w)) - Vy( w++1 u)
for any u E W.
Lemma 32. Let (Fi) be filtratiion Let {zj 1. be stochastic process in B2(U)) = {z R ||z||>o S 1} such that 2 is F; measurable. Let {Eclr=1 be a martingale difference sequence such that e, E RR is Fet1 measurable. Furthermore, assume that conditional on Fi, we have ||=:|] S
almost surely, and denote by E, Ele,e] [Fo.. Let X >> O and for any t 2 1 define
U+= Σ (E) and B. =
2 113
Then, for any 5 E (0, 1]. we have
VX
4
B
4 log 5.
Pr 3 U, B
log
+
VX
Lemma 33 (Lemma 1 of 76). Let {(z,y) Σ*
1'y
k}} log ( ) 1-C,0|
y E {0) U [K] and b RK where C 0. Then, we have
1
log(K K + +)C+ (a (a-b) b) (V2[(b, -b). Lemma 34 (Lemma 17 of 76). Let l(z, Σk 1/y k} log (,क)) and E R be where smooth, = (1 u)p
f(a. y) 2 ((b, v) + Vl(b, y) T T(a (a- bb) b)
a K K-dimensional vector. Define n² A o- (smooth,, 11/(K + 1). Then, for μ E (0, 1/2), we have
E(z", y) E(z,)) y) S 2p
for any y E (0) U [K]. We also have ||24 < log(K] K/p).
Lemma 35 (Lemma 18 of (76). Let L,, (0) + 1 0 - IB.... Assume that lip, is
-f-ssolfconnoortanttiike function. Then, for any 0, 0,0% B(O,, 1), the quadratic approximation
(f) = (1) + (V Li,n (0++1), 0++1) + zz
0,11 sutisfies
B.
(0) < (0) + exp N 0
2 0,11
0 0
2
71

---

H
Limitations
We make an assumption about the transition model of MDPs by using the MNL model, which is specific parametric model. This assumption implies that we assume the realizability of the MNL model. It's worth noting that the realizability assumption has also been commonly made in previous literature on provable reinforcement learning with function approximation, including works such as However, we hope that this condition can be
72 43
73 53 22 [4 9 68 70
relaxed in the future work.
72

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract is to propose provably efficient random- ized algorithmss for MNL-MDPs. In Section [ (Introduction), we provide the motivation and main contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation of this work in Appendix H
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
73

---

Answer: [Yes]
Justification: We provide the full set of assumptions Section 2.2 and a complete proof of main results in Appendix C and D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide numerical experiments that support our main claims in Section and the detailed information of experiments in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
74

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have attached the data and code with sufficient instructions to reproduce the main experimental results in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
public/guides/CodeSumii wttpsuumiiiiiooooiiiooiooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https htcc/public/guuiees/Ccddee
ssi sisionnnicc for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the detailed explanation for the experimental setting in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report error bars (standard deviation) in our numerical experiment results shown in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
75

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the detailed information on the computer resources used to conduct numerical experiments in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in this paper adheres to the NeurlPS Code of Ethics in all aspects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no negative societal impacts of the work performed because this research focuses on theoretical aspects.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
76

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The research conducted in this paper does not pose any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use any external assets such code, data, or models.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datatss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
77

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
78


Reviews:
[{"review_id": "g3ORaKXxvL", "reviewer": "Reviewer_QBih", "summary": "The paper introduces a computationally efficient randomized algorithm for MNL-MDPs, addressing limitations of previous exploration algorithms. It presents the RRL-MNL algorithm, focusing on online transition core estimation and stochastically optimistic value function design. This paper provides a frequentist regret analysis for MNL-MDPs with theoretical comparisons to other algorithms.", "questions": "1. Can you give a more detailed comparison between MNL-MDPs and Linear MDPs settings? Can you give a detailed discussion on the setting MNL-MDPs and show it worth studying? What is the connection between this setting and generalized linear MDPs?\n\n2. Can you summarize the theoretical challenges of randomized algorithms in MNL-MDPs compared with that in Linear MDPs?\n\n3. Can you explain the necessity of Assumption 4, which seems lack realizability motivation? I find that you mention this assumptions also use in generalized linear bandits, can you compare the assumptions in generalized linear bandit and in MNL-MDPs. Also, how about the generalized linear MDPs?\n\n4. The regret bound of ORRL-MNL is interesting. Do you have any new theoretical analysis techniques to obtain this?", "limitations": "This paper lacks more discussions on the setting, MNL-MDPs to show it worth studying. I hope the authors can answer my questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-structured and effectively communicates complex theoretical concepts.\n\n2. The proposed algorithm, ORRL-MNL, is interesting, and it regret bound has an attractive improvement.", "weaknesses": "1. The focus on multinomial logistic function approximation and specific types of state transitions (inhomogeneous) may restrict the generalizability of the proposed algorithms. \n\n2. The paper lacks some discussion on the setting, MNL-MDPs to show it worth studying.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n- - -\n### __[W1] Generalizability of the proposed algorithms__\nWe respectfully disagree that the stated point is a weakness of our work. For instance, in the contextual bandit setting, the logistic bandit assumes that the expected reward for an action is given by a logistic function of the action's context features. The logistic bandit addresses a specific type of reward setting but can also handle problem instances that the linear bandit cannot. Additionally, substantial research [3, 23, 24, 49, 43, Lee et al. (2024)] has been conducted to develop improved algorithms tailored to this specific logistic reward setting. We would like to emphasize that our main contribution in this paper is also to present an improved algorithm for MNL-MDPs, overcoming several limitations of linear MDPs, which we will detail in the second bullet point.\n\n   >Lee et al. \"Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion.\" AISTATS 2024.\n\n---\n\n### __[W2 & Q1] Discussion on MNL-MDPs & Comparison with Linear MDPs__\nWe are happy to address this issue. Although improved algorithms for linear MDPs continue to be proposed, linear MDPs inherently have fundamental limitations:\n\n1. As introduced in [35], a linear function approximating the transition model must ensure that the function output is within [0, 1] and that the probabilities over all possible next states sum to 1. This restrictive assumption limits the set of feature representations of state-action pairs that are admissible for the transition model (Proposition 1 in [35]).\n\n2. Additionally, Theorem 1 from Lee \\& Oh (2024) shows a fundamental limitation of linear MDPs. In linear MDPs, the ambient feature dimension $d$ is lower bounded by $|\\mathcal{S}|/\\mathcal{U}$. This implies that unless the size of the reachable states is proportional to the total number of states, i.e., $\\mathcal{U} = \\Theta(|\\mathcal{S}|)$, the feature dimension inherently depends on the size of the state space. \n\n  To overcome these limitations, [35] proposed a new class of MDPs (MNL-MDPs) using multinomial logistic function approximation. MNL-MDPs have garnered significant attention in the RL community, leading to many follow-up works (Park \\& Lee, 2024; Li et al, 2024) and numerous open research questions.\n\n  If the generalized linear MDPs you mentioned refer to [67], they assume the Bellman backup of any value function to be a generalized linear function of feature mapping and propose a *model-free* algorithm under this assumption. In contrast, in MNL-MDPs, the state transition model is given by a multinomial logistic model based on state-action features, and we propose a *model-based* algorithm.\n    \n   >Lee and Oh. \"Demystifying Linear MDPs and Novel Dynamics Aggregation Framework.\" ICLR 2024.    \n   \n   >Li et al. \"Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation.\" arXiv 2024.\n\n   >Park and Lee. \"Reinforcement Learning for Infinite-Horizon Average-Reward MDPs with Multinomial Logistic Function Approximation.\" arXiv 2024.\n\n---\n### __[Q2] Theoretical challenges of randomized exploration in MNL-MDPs__\n - __Absence of the closed-form expression of value function in MNL-MDPs__ \n     Unlike linear MDPs, where the value function is linear in the feature map, in MNL-MDPs the value function is no longer linearly parameterized. Therefore, we cannot control the perturbation of the estimated value function in MNL-MDPs by perturbing the estimated parameter directly as in linear MDPs. \nHowever, as shown in Lemma 4 (RRL-MNL) or Lemma 16 (ORRL-MNL), we were able to express the prediction error in terms of the estimated error of the transition parameter, providing a basis for how we can control the perturbation of the value function.\n- __Ensuring the stochastic optimism of the estimated value function__\n    The main technical challenge in analyzing the frequentist regret of randomized algorithms is ensuring the estimated value function is optimistic with sufficient frequency. However, the substitution effect of the next state transition in the MNL model makes ensuring the stochastic optimism much more challenging. If the probability of the estimated value function being optimistic at horizon $h$ is denoted as $p$, this would result in the probability that the estimated value function in the initial state is optimistic being on the order of $p^H$, implying that the regret can increase exponentially with the length of the horizon $H$. Instead we establish that the difference between the estimated value and the optimal value is expressed by the sum of Bellman errors along the sample path obtained by the optimal policy (Lemma 4) and adapt the optimistic sampling technique to ensure the stochastic optimism with sufficient frequency (Lemma 6 \\& 18). Please note that while [37] presented a frequentist regret analysis for general function class using eluder dimension under the assumption of stochastic optimism, __our work deals with non-linear function approximation and directly demonstrates stochastic optimism without any additional assumptions.__\n\n- - -\nDue to the space limit, we will leave responses to the remaining comments in the following official comment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xLCP4ZXuX9", "reviewer": "Reviewer_Ftt2", "summary": "This paper studies reinforcement learning of an MDP with multinomial logistic (MNL) function approximation, which approximates the unknown transition kernel of the underlying MDP. The setting is the finite horizon episodic MDPs. Two algorithms are proposed. The first algorithm is statistically efficient with a provable frequentist regret bound, and is computationally efficient with constant-time computational cost per episode. To further improve the dependence on problem constant of the first algorithm, the second algorithm utilizes gradient information of the MNL model of the unknown transition. These two algorithms are the first randomized algorithms for the MNL transition model with both statistical and computational efficiency. Furthermore, numerical simulations show the good performance of the proposed algorithms.", "questions": "My concerns are included in the **Weaknesses** session.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "**Significance**: \n\n**1.** The MNL transition model is a reasonable model for approximation to the unknown transition kernel and thus has potential practical usage. \n\n**2** The two algorithms are provably statistically efficient, which is further corroborated by numerical simulations. \n\n**Originality**: This paper has originality. It proposes to use multinomial distribution for modeling the transition kernel of MDP, and proposes the first efficient randomized algorithms for the MNL transition model.\n\n**Clarity**: the main text of the paper is clearly presented: algorithms are explained well (e.g. the intuition behind stochastically optimistic value function is provided); the theorems are presented with in-depth discussion of its relation to existing works, and the comparison of its proof techniques with other algorithmic guarantees in the area.", "weaknesses": "I did not find any major errors or technical flaws. However, the following can be improved.\n\n*Weaknesses*\n\n**1.** The theoretical analysis, especially the appendix, is a bit hard to read. This is caused by two issues: (i) there are many displayed equations that are very long; (ii) some derivations/steps are missing a proper explanation. \n\n**2.** The formatting of the equations in the appendix should be improved. There are many lines of equations which significantly exceed the length limit within a line. Probably should consider breaking the equations into combinations of shorter ones with proper explanation.\n\n*Other Minor issues*\n\n**1.** This paper so far only demonstrates the efficacy of the multinomial logistic model for approximating a synthetic MDP environment. Although the result from the numerical simulation is convincing, it would be very interesting to see how it works if applied to more realistic environment. This might be an interesting future direction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n- - -\n### __[W1] Presentation__\n> there are many displayed equations that are very long\n\nThe comprehensive nature of our analysis required the inclusion of detailed proofs, resulting in lengthy equations. Some of these equations slightly exceeded the line limit to enhance readability. In the revised version, we will ensure these equations are displayed more clearly. Additionally, we have organized the definitions and notations used in our analysis in Appendix B for convenience, so please refer to it.\n\n> some derivations/steps are missing a proper explanation\n\nIf there are specific derivations or steps that were not clearly explained, we will address these in the revised version. We would greatly appreciate it if you could point out any particular areas that were unclear, so we can improve them.\n\n---\n### __[W2] Format__\nWe will pay closer attention to the formatting in the revised version, breaking long equations into shorter ones with proper explanations. Thank you for pointing this out. \n\n---\n### __[M1] Experiment on realistic environment__\nAmong dozens (if not hundreds) of papers on provable RL with function approximation, there are very few papers with numerical experiments. The vast majority of the papers do not contain any experiments at all. To the best of our knowledge, the ones with the experiments (with regret guarantees) are only [9, 35, 37] -- we would be more than happy to add to this list if the reviewer knows of any other related theory RL work that contains more extensive experiments. Hence, we would like to point out that we conducted a significant number of experiments compared to the existing theoretical RL papers [41, 66, 69, 70]. As this is a theoretical paper, we respectfully request that it be mainly assessed based on its theoretical merit. Yet, as the number of states increases, our proposed methods are the ones that remain competitive and superior to the existing methods, showing the efficacy of MNL function approximation and empirical evidence for our theoretical claims for our algorithms.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rGshveejTx", "reviewer": "Reviewer_rYza", "summary": "The paper considers the MNL MDP setting and provides several regret bounds. The MNL setting is one where the transition probabilities are modeled as a soft-max over a linear transformation of state-action-next-state features. The work improves the dependence on an important problem parameter. The main results are presented using randomized exploration but a deterministic exploration scheme is also included in the appendix. Concretely, $\\kappa$ is a problem dependent constant that lower bounds any individual transition probability estimate. The authors explain that it relates to information gain in the transition kernel regression problem through the Fisher information matrix.", "questions": "See above.", "limitations": "N/a", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The new algorithm does not need to know $\\kappa$ (this is not the case in previous works)\n2. The obtained regret bound is improved from $\\approx \\kappa^{-1}\\sqrt{K}$ to $\\approx \\kappa^{-1} + \\sqrt{K}$\n3. the memory and computational requirements per episode are reduced from linear to constant in the number of episodes.", "weaknesses": "**Setting:**\nWhile the MNL model is quite intuitive, it has several shortcommings that, in my opinion, limit its usefulness.\n\n1. It does not seem to allow for a compact characterization of the value or policy. This is because these depend strongly on the size of the next state sets $\\mathcal{S}_{s,a}$. While instances where these sets are small exist this is still very limiting.\n2. The sets $\\mathcal{S}_{s,a}$ must be **known** to the algorithm.\n3. It is very hard to imagine a setting where $\\kappa^{-1}$ is not exponential in natural problem parameters.  \n\n\n**Presentation:**\n\n4. The paper is written in such a way that makes it hard to appreciate its contributions beyond the objective improvement to the regret bound. There are some discussions as to what makes the analysis more involved compared to standard TS and MNL bandits but I find it vague. Moreover, there are no proof sketches of any kind, which contributes to this issue. Overall, this makes it hard to appreciate the soundness of the paper and whether it contains meaningful technical contributions or not.\n\n\n**Results:**\n5. Most importantly, while the paper improves computational efficiency, It seems to me that it still has at least $|\\mathcal{U}|^H$ computations per round (to calculate the Q function along the policy trajectory). This exists in past algorithms as well and makes all of them inefficient (not polynomial in the natural problem parameters). Is this the case?\n6.  I do not see the randomized exploration as significant contribution. It both complicates the analysis significantly and deteriorates the regret. I appreciate the potential practical appeal but I do not think this strengthens the paper significantly. I personally think the focus of the paper should have been on the improved regret with the standard deterministic bonuses. This would also simplify the presentation.\n7. There is a recent concurrent paper ([1]) on this topic that seems to obtain similar results. While it is concurrent, I would appreciate if you provide a comparison in your response.\n\n[1] Li, Long-Fei, et al. \"Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation.\" arXiv preprint arXiv:2405.17061 (2024).‏", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n\n- - -\n### __[W1] Compact characterization of the value or policy__  \nWe believe that the lack of a compact characterization of the value or policy should NOT be considered a weakness of our work. Including almost every generic model-based setting [9, 21, 4, 35], even in tabular RL or similar settings like linear mixture MDPs, a compact characterization of the value or policy is not always achievable. \n\n---\n### __[W2] Known reachable states__  \nWe respectfully **disagree that this assumption constitutes a weakness when compared to other function approximation approaches** such as linear MDPs and general function classes. While we acknowledge this requirement, it's important to note that other approaches also come with their own inherent limitations. Recent studies have highlighted fundamental limitations of linear MDPs:\n\n1. As introduced in [35], a linear function approximating the transition model must ensure that the function output is within [0, 1] and that the probabilities over all possible next states sum to 1. This restrictive assumption limits the set of feature representations of state-action pairs that are admissible for the transition model (Proposition 1 in [35]).\n\n  2. Additionally, Theorem 1 from Lee \\& Oh (2024) shows a fundamental limitation of linear MDPs. In linear MDPs, the ambient feature dimension $d$ is lower bounded by $|\\mathcal{S}|/\\mathcal{U}$. This implies that unless the size of the reachable states is proportional to the total number of states, i.e., $\\mathcal{U} = \\Theta(|\\mathcal{S}|)$, the feature dimension inherently depends on the size of the state space. \n\nFurthermore, to the best of our knowledge, there are no computationally tractable algorithms that can handle the general function classes [46, 40, 19, 21, 28, 42, 18] (See Line 640).\n\nIn contrast, MNL-MDPs do not require the restrictive linearity assumption present in linear MDPs and can be effectively addressed with computationally tractable algorithms, such as those we propose in our paper. For these reasons, MNL-MDPs have received significant attention within the community, leading to several follow-up works (e.g., Park & Lee, 2024; Li et al., 2024). We note that under this well-established problem setup, our main contribution is to present both computationally and statistically efficient RL algorithms.\n   \n   >Lee and Oh. \"Demystifying Linear MDPs and Novel Dynamics Aggregation Framework.\" ICLR 2024.    \n   \n   >Li et al. \"Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation.\" arXiv 2024.\n\n   >Park and Lee. \"Reinforcement Learning for Infinite-Horizon Average-Reward MDPs with Multinomial Logistic Function Approximation.\" arXiv 2024.\n\n---\n### __[W3] Discussion on kappa__  \nThis is the exact motivation behind our second algorithm. To address this issue, we proposed ORRL-MNL (Algorithm 2) and UCRL-MNL+ (Algorithm 3), each achieving a frequentist regret guarantee with improved dependence on $\\kappa$. These algorithms can mitigate the worst-case exponential dependence on $\\kappa$.\n\n---\n### __[W4] Presentation__  \nDue to page limitations, we could not include the proof sketch in the main text. Instead, we have provided the main theorem and the necessary lemmas step-by-step in the appendix, with detailed and clear proofs. We hope this will be helpful for your understanding. In the revised version, we will include the proof sketch in the main text.\n\nFor the proof sketch, the frequentist regret analysis of the proposed algorithm follows the flow of linear MDPs if stochastic optimism is guaranteed. Specifically, we decompose the regret into an estimation part and a pessimism part, and then bound each part. The estimation part is upper bounded by the Bellman error of the sample trajectory according to the agent's policy in each episode. The Bellman error is further bounded by the prediction error and the bonus term due to randomized exploration. Here, we use the elliptical potential lemma to bound the estimation part (Lemmas 10 \\& 21). For the pessimism part, as shown in Lemma 11, the pessimism term can be upper bounded by the estimation term times the inverse of the probability that the estimated value function is optimistic. This is why we need to ensure that the probability that the estimated value function is optimistic is lower bounded by a constant value, regardless of the problem instance. As shown in Lemmas 6 \\& 18, we show that the probability that the estimated value function is optimistic than the true optimal value function is lower bounded by $\\Phi(-1)/2$, which is an absolute constant. Combining all the results, we can achieve the proposed regret bound.\n\n---\n\n### __[W5] Computational efficiency__\nWe believe there may be a misunderstanding. Our proposed algorithms do not need to calculate the Q function along the policy trajectory; rather, we calculate the Q function before proceeding with the episode and choose the greedy action with respect to the estimated Q function. Therefore, the computational cost is polynomial in the *natural parameters of the problem and constant* per episode. In this case, the amount of computation for these Q functions is not necessarily more expensive than those in linear MDPs. For instance, eq (3) in [9] includes the integral over all states to estimate the action-value of a given state-action pair. Therefore, except in the case where the set of reachable states for each state-action pair exactly matches the entire state space, it is difficult to conclude that the computational complexity of our algorithms is more expensive compared to other linear model algorithms.\n\n>Due to the space limit, we will leave responses to the remaining comments in the following official comment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9ciMjNf0UZ", "reviewer": "Reviewer_u5d2", "summary": "This work proposes the two randomized RL algorithms, RRL-MNL and ORRL-MNL, for the MNL transition model that for the first time achieve both computational and statistical efficiency without stochastic optimism. The complexity of ORRL-MNL has better dependence on the large problem-related constant $\\kappa^{-1}$ than RRL-MNL.", "questions": "(1) Assumption 4 is equivalent to $\\inf _ {\\theta\\in \\mathcal{B} _ d(\\mathcal{L} _ {\\theta})} P_{\\theta}(s'|s,a)\\ge \\sqrt{\\kappa}, \\forall s,a,s'$, since $\\inf _ {s',\\widetilde{s}}P _ {\\theta}(s'|s,a)P _ {\\theta}(\\widetilde{s}|s,a)=[\\inf_{s'}P _ {\\theta}(s'|s,a)]^2$. \n\n(2) In eq. (2), how to select $L_{\\theta}$? Does eq. (2) aim to minimize the lost function $\\sum_{k=1}^N\\ell_{k,h}(\\theta)$? Why do you use Newton step instead of first-order algorithm? \n\n(3) Could you explain the intuition of eq. (3)? Is it inspired by the Hessian of the loss $\\ell_{k,h}(\\theta)$? \n\n(4) In the paragraphs about ``Stochastically optimistic value function'' after eq. (3), it seems that most words are about the drawbacks of existing works on optimistic estimated value function, and then you adapt optimistic sampling technique instead. It would be more clear to me if you introduce your eq. (4) first with more explanations, for example, what adjustments are made to the original optimistic sampling technique [7, 52, 37, 36] and why, why is $A_{j,k}^{-1}$ used instead of Euclidean norm in $\\hat{s}$ definition, and then list its advantage over existing works (maybe with less words than the current version?). Also, is your Remark 2 an advantage over relevant works like [35]? If yes, you may claim this advantage. \n\n[35] Taehyun Hwang and Min-hwan Oh. Model-based reinforcement learning with multinomial logistic function approximation. In Proceedings of the AAAI conference on artificial intelligence, pages 7971–7979, 2023.\n\n(5) In eqs. (4) and (7), is it tighter to truncate at level $H-h+1$ instead of $H$? \n\n(6) In eq. (6), is there an intuition why $\\nabla^2\\ell_{k,h}$ has coefficient $\\eta$ while $\\nabla^2\\ell_{i,h}$ ($i=1,\\ldots,k-1$) have coefficient 1? \n\n(7) Is there an intuitive explanation of $\\nu_{k,h}^{\\rm rand}(s,a)$ defined after eq. (7)? \n\n(8) You could also define $T$ in Theorem 1 to facilitate readers. The total number of steps is $T=KH$, yes? Is yes, is it better to use the equivalent sample complexity $\\kappa^{-1}d^{\\frac{3}{2}}H^2\\sqrt{K}$? \n\n(9) To ensure reproducible experiment, some hyperparameters are missing such as $M$, $\\lambda$, $\\kappa$, $\\eta$, $\\sigma_k$, $\\beta_k$, etc. \n\n(10) Could you compare your work with contemporary work [a]? \n\n[a] Li, Long-Fei, et al. \"Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation.\" ArXiv:2405.17061 (2024).\n\n(11) Is it possible to extend your work to stochastic policy and unknown reward? For example, will $\\epsilon$-greedy policy also encourage exploration more than greedy action? \n\n(12) Typo at the beginning of Section 2: {$P_h$} $_ {h=1}^H$ instead of {$P$} $_ {h=1}^H$.", "limitations": "The final appendix section mentions the limitation of realizability assumption. I agree with the authors' claim that there is no negative societal impacts because this work focuses on theoretical aspects.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "MNL parameterization is important and convenient since the parameterized transition kernel is always a probability distribution. This work is computationally more efficient than the existing work [35] on MNL parameterization.", "weaknesses": "Some details of the algorithms are not easily understood and are thus better to explain intuitively, as mentioned in questions 2-4 and 6-7 below. The regrets of both proposed algorithms are higher than $\\widetilde{O}(dH^{\\frac{3}{2}}\\sqrt{T})$ of [35]. Experiment reproducibility could be improved as shown in question 9 below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time to review our paper and for your valuable feedback. Here are our responses to each comment and question:\n\n---\n### __[W1] Regret bound__  \nIt is generally well-known that the regret bound of randomized algorithms is higher than that of optimism-based algorithms. For example,  \n- in the linear bandit setting: UCB $\\tilde{O}(d \\sqrt{T})$ [1] vs. TS $\\tilde{O}(d^{3/2} \\sqrt{T})$ [2];  \n- in the MNL-bandit setting: UCB $\\tilde{O}(d \\sqrt{T})$ [53] vs. TS $\\tilde{O}(d^{3/2} \\sqrt{T})$ [52];\n- in linear MDPs: UCB $\\tilde{O}(d^{3/2} H^{3/2} \\sqrt{T})$ [41] vs. TS $\\tilde{O}(d^2 H^2 \\sqrt{T})$ [71].\n\nThis gap originates from the fact that randomized algorithms require the perturbations to have sufficient variance to guarantee optimism of the estimated reward (or value) with a constant probability. Note that although randomized algorithms have a higher regret bound than UCB-based algorithms, randomized exploration not only exhibits superior performance in empirical evaluations but also necessitates a more rigorous proof technique to obtain a theoretical guarantee. Hence, proving a particularly frequentist regret bound for TS algorithms in any given bandit or RL problem has been widely recognized as making significant contributions to both RL and bandit literature.\n\n---\n### **[Q1] Assumption 4**\nWe intended to define $\\kappa$ for $s'\\ne\\tilde{s}$. In this case, Assumption 4 is not equivalent to what you mentioned. We will clarify this in the revised version.\n\n---\n### **[Q2] Eq. (2)**\n  - $L_\\theta$: $L_\\theta$ is specified in Assumption 2, which is common in the literature on RL with function approximation [41, 70, 71, 37, 35], to ensure the regret bounds are scale-free.\n  - Eq.(2): Eq.(2) is designed as an online update scheme to find an approximate solution for minimizing the cumulative loss function $\\sum\\_{k=1}^K \\ell\\_{k,h} (\\theta)$ since computing the exact solution for MLE can be inefficient in terms of time and space complexity.\n  - Newton step: We believe there may be a misunderstanding. The optimization method used to estimate Eq.(2) is not an exact Newton method because there is no calculation of the Hessian matrix. Instead, we use the lower bound of the Hessian matrix (i.e., $\\lambda \\mathbf{I}\\_d + \\sum_{i=1}^{k-1} \\nabla^2 \\ell_{k,h}(\\theta) \\succeq \\mathbf{A}_{k,h}$), which is why we mention that we use a variation of the online Newton method. Note that this approach is inspired by online algorithms for logistic bandits [72] and MNL contextual bandits [53]. We applied these techniques to estimate the transition core in MNL-MDPs, and as a result, provided both computationally and statistically efficient randomized algorithms for MNL-MDPs.\n\n___\n### **[Q3] Eq. (3)**\n  The typical form of Eq.(3) is referred to as the Gram matrix, which is widely used in the existing feature-based bandit and RL literature [cite here]. It aggregates the feature information based on the decisions made by the algorithm in previous episodes. Once more, we would like to note that the Gram matrix in Eq.(3) is a lower bound of the sum of the regularized Hessian matrix.\n\n___\n### **[Q4] Stochastically optimistic value function**\nTo help understand the concept of a stochastically optimistic value function, we will provide additional explanations. In this paragraph, our intention is not merely to list the drawbacks of related literature. Instead, we introduce the key challenges of regret analysis for randomized algorithms, explain how previous works have overcome these challenges, and then describe why the techniques from previous works cannot be applied to MNL-MDPs. In the revised version, we will clarify this further to make it easier to understand.\n\n   For the definition of $\\hat{s}$, at the end of the proof of Lemma 4, the prediction error can be upper bounded by the maximal inner product of the feature and the difference between the estimator, i.e., $\\Delta^k_h(s,a) \\le H \\max_{s' \\in \\mathcal{S}\\_{s,a}} | \\varphi\\_{s,a,s'}^\\top (\\theta^k\\_h - \\theta^*\\_h)|$. We apply the Cauchy-Schwarz inequality with respect to $||\\cdot||\\_{A_{k,h}}$ because we have the concentration result for $\\theta^k\\_h$ with respect to $||\\cdot||\\_{A\\_{k,h}}$ in Lemma 1. That is why the dominating feature $\\hat{\\varphi}(s,a)$ is defined with respect to the $||\\cdot||\\_{A\\_{k,h}}$ norm rather than the $||\\cdot||\\_2$-norm.\n\n   For Remark 2, as the reviewer mentioned, it explains why RRL-MNL is computationally efficient compared to relevant works in MNL-MDPs [35]. We respectfully remind you that we clearly state our proposed algorithms are both computationally and statistically efficient in the main contributions.\n\n---\n### **[Q5] Clipping in Equation (4) and (7)**\nIt is possible to truncate $Q^k_h$ to $H-h+1$, but it does not change our analysis or result in a tighter regret bound.\n\n- - -\nDue to the space limit, we will leave responses to the remaining comments in the following official comment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: A summary of the strengths and weaknesses based on the reviews and rebuttal (including the follow-up discussion and that among the reviewers) is provided below:


**STRENGTHS**
 
1. This paper proposes novel randomized algorithms for MNL-MDPs that are efficient statistically.

2. The authors have provided a regret analysis and an improved regret bound for their proposed algorithms without assuming stochastic optimism.

3. The main paper is well-organized and clearly presented.


**WEAKNESSES**

1. **As mentioned by Reviewer rYza, we agree that it is not correct for the authors to claim that their method is computationally efficient. This is misleading. Like the authors have said, "there is NO efficient method for planning that avoids dependency on $|S|$ or that is not exponential in $H$", though anytime algorithms have been used to mitigate the latter issue. In such a case, we would like the authors to withdraw all instances of mentioning that their method is computationally efficient since it is not.**

2. This paper initially lacks a discussion of the positioning and challenges (in particular, the theoretical analysis) of its proposed work w.r.t. linear MDPs. The authors have adequately addressed this concern in the rebuttal.

3. Multiple reviewers have agreed that the ease of readability of the derivations and proofs has room for improvement, such as reducing lengthy equations with shorthand notations, giving the results used for each step of the proof/derivation, giving proof sketches, etc.


Nonetheless, the **pros of this work outweigh the cons**.


Also, the authors are requested to make clear the following points, as requested by the reviewers during the discussion:

- The authors explained that Eq. (2) aims to minimize $\sum_{k=1}^N\ell_{k,h}(\theta)$, why only $\nabla\ell_{k-1,h}$ is used? Similar question applies for Eq. (5).

- Also, the new notation $s_{i_1},\ldots,s_{i_{\mathcal{S}_{kmh}}}$ in line 170 should be defined.


As a minor comment, while we agree that the main contributions of this work are theoretical and the authors have provided numerical experiments (unlike several prior works), the authors can ask themselves why stop at that and not go beyond to more realistic environments (is it simply because no other work has done it?). Why not be one of the first few works to move the needle by demonstrating the practicality of model-based RL? If not, the authors can discuss what stands in their way to be able to achieve this and their position on whether there is any hope of doing so by pursuing this line of work. We would strongly urge the authors to reconsider their position here.


The authors are encouraged to revise their paper based on the above feedback and that of the reviewers.
Decision: Accept (poster)