Provably More Efficient Q-Learning in the One-Sided-Feedback/Full-Feedback Settings
Authors: Xiao-Yue Gong
David Simchi-Levi
Venue:  (2021)
Keywords: Q-learning
episodic MDP
full-feedback
one-sided-feedback
inventory control
inventory

Abstract: Motivated by the episodic version of the classical inventory control problem, we propose a new Q-learning-based algorithm, Elimination-Based Half-Q-Learning (HQL), that enjoys improved efficiency over existing algorithms for a wide variety of problems in the one-sided-feedback setting. We also provide a simpler variant of the algorithm, Full-Q-Learning (FQL), for the full-feedback setting. We establish that HQL incurs $ \tilde{\mathcal{O}}(H^3\sqrt{ T})$ regret and FQL incurs $\tilde{\mathcal{O}}(H^2\sqrt{ T})$ regret, where $H$ is the length of each episode and $T$ is the total length of the horizon. The regret bounds are not affected by the possibly huge state and action space. Our numerical experiments demonstrate the superior efficiency of HQL and FQL, and the potential to combine reinforcement learning with richer feedback models.

Under review as a conference paper at ICLR 2021
PROVABLY MORE EFFICIENT Q-LEARNING IN THE
ENN-SSSDD-FEEDDBACAFULLEEEEDRD SETTINGS S
Anonymous authors
Paper under double-blind review
ABSTRACT
Motivated by the episodic version the classical inventory control problem, we propose new Q-leaming- based algorithm, Cimmination-Based Half- Q-Learning (HQL), that enjoys improved efficiency over existing algorithms for a wide variety of problems in the one-sided-feedbant setting. We also provide simpler variant of the algorithm, Full-Q-I
(FQL), for the full-feedhack setting. We estab- lish that HQL incurs Ó(H3 TT) regret and FQL incurs ((H2 regret, where H is the length of each episode and T is the total length of the horizon. The regret bounds are not affected by the possibly huge state and action space. Our numer- ical experiments demonstrate the superior efficiency of HQL and FQL, and the potential to combine reinforcement learning with richer feedback models.
INTRODUCTION
Motivated by the classical operations research (OR) problem -iveenrryy control, we customize Q- learning to more efficiently solve a wide range of problems with richer feedback than the usual bandit feedback. Q-learning a popular reinforcement learning (RI. method that estimates the state-action value functions without estimating the huge transition matrix in a large MDP (Watkins & Dayan (1992), Jaakkola al. (1993)). This paper is concerned with devising Q-learning algorithms that leverage the natural one-sided- wewedefeecbbcllllfeeeeeeoo
structures in many OR and finance problems.
The topic of developing efficient RL algorithms catering special structures is funda- mental and important, especially for the purpose of adopting RL more widely in real applications. By contrast, most RL literature considers settings with little feedback, while the study of single-stage online learning for bandits has history of considering a plethora of graph-based feedback mod- els. We are particularly interested in the prevalence in many famous problems, such as inventory control, online auctions, portfolio man- agement, etc. In these real applications, RL has typically been outperformed by domain-specific algorithms or heuristics. We propose algorithms aimed at bridging this divide by incorporating problem-specinn structures into classical reinforcement earning algorithms.
Motivation
models because of their
1.1
PRIOR WORK
The most relevant literature to this paper is Jin et al. (2018), who prove the optimality of Q-learning with Upper-Confidence-Bont
bonus and Bernstein-style bonus in tabular MDPs. The recent work of Dong et al. (2019) improves upon Jin al. (2018) when aggregation of the state-action pairs with known eтror is given beforehand. Our algorithms substantially improve the regret bounds (see Table 1) by catering to the mull-feedback/one-tie wwddd-feeddeeeeeeeeeeeeeeeeeeeee structures of many problems. Because our regret bounds are unaffected by the cardinality of the state and action space, our Q-learning algorithms are able to deal with huge state-action space, and even continuous state space some cases (Section 8). Note that both work and Dong et al. (2019) general episodic MDP problems. We focus on problems with richer feedback; Dong et al. (2019) focus problems with nice aggregate structure known to the decision-maker.
designed for subset of the
The one- one-sided many different learning problems outside the scope of episodic MDP settings, for example learning in auctions with binary feedback, dynamic pricing and binary search (Weed et al. (2016), (Feng al. (2018), Cohen et al. (2020), Lobel et al. (2016)). In partieular, Zhao & Chen (2019) study the
setting, or some similar notions, have attracted lots research interests in

---

Under review as a conference paper at ICLR 2021
one-sided- feedbbdcee setting in the learning problem for bandits, using similar idea of elimination. However, the episodic MDP setting for RL presents new challenges. Our results can be applied to their setting and solve the bandit problem as special case.
The idea of optimization by climination has a long history (Even-Dar et al. (2002)). A recent exam- ple of the idea being used in RL is Lykouris al. (2019) which solve very different problem of robustness to adversarial corruptions. Q-learning has also been studied in settings with continuous states with adaptive discretization (Sinclair al. (2019)). In many situations this is more efficient than the uniform discretization scheme we use, however our algorithms' regret bounds are unaf- fected by the action-state space cardinality so the difference is immaterial.
Our special case, the full-feedback setting, shares similarities with the generative model setting in that both settings allow access to the feedback for any state-action transitions (Sidford et al. (2018)). However, the generative model is strong oracle that can query any state-action transitions, while the full-feedback model can only query for that time step after having chosen an action from the feasible set based on the current state, while accumulating regret.
Table Regret comparisons for Q-leaniig algorithms on episodic MDP
Algorithm
Regret
Time
Space
Alearning+Bernsteen bonus Jin et al. (2018)
O(VHaSA)
O(T)
O(SAH)
Aggregated Q-learning Dong et al. (2019)
Ó(VHAMT +
((MAT)
O(MT)
Full-Q hall-Q-learning (FQL)
O(VHTT)
O(SAT)
O(SAH)
Elimination Based Half- nala-Q-learning (HQL)
O(VH6T)
O(SAT)
O(SAH)
PRELIMINARIES
We consider an episodic Markov decision process, MDP(S, A, Hr,, where S is the set of states with |S| = S, AA is the set of actions with IA| = A, H is the constant length of each episode, P is the unknown transition matrix distribution over states some action y is taken at some state x at step h [H] and ry S x A + Jo, 1] is the reward function stage h that depends on the environment randomness Dr. In each episode, an initial state i is picked arbitrarily by an adversary. Then, at each stage h, the agent observes state Ty E S. picks action yı. A, receives realized reward Th (In, )h). and then transitions to the next state 2h+11 which is determined by 2h. Uh. D₁. At the final stage H. the episode terminates after the agent takes action уи and receives reward rи. Then next episode begins. Let K denote the number of episodes, and T denote the length of the horizon: = H K, where H a constant. This is the classic setting of episodic MDP, except that in the one-sided-feedback setting, we have the environment randomness D₁,, that once realized, can help us determine the reward/transition any alternative feasible action that "lies on one side" of our taken action (Section 2.1). The goal is to maximize the total reward accrued in each episode.
policy π of an agent is a collection of functions (m^ : S - A}RE(H) We use V S + IR to denote the value function at stage h under policy æ, so that V (x) gives the expected sum of remaining rewards under policy æ until the end of the episode, starting from r:
V (x)
=
Σ Tw (ow, Tw (IN))) xn = x :==h
OF S A R denotes the Q-value function at stage h, so that (T y) gives the expected sum of remaining rewards under policy until the end of the episode, starting from &n = I, yn = y:
(T( = B[r((on
Σ Tw W=++1
x, Mr
'eere M is the number of aggregate state-action pairs; is the largest difference hetween any pair of optimal state-action values associated with common aggregate state-action pair.
2

---

Under review as a conference paper at ICLR 2021
Let n" denote optimal policy in the MDP that gives the optimal value functions (z)
sup, (/(()) (2) for any I E S and h E [H]. Recall the Bellman equations:
(x) 2% (x)))
Vz) miny (x y) (z, == Er (. [Th + Vit (z')
(z, = (( [Ta + VK41 (x') V (x) =0, O,
Va ES
( = O, Va E
denote the expected cumulative regret against n- on the MDP up to the end of episode k. Let nı denote the policy the agent chooses at the beginning of the kth episode.
We let
Regret =
[V' (at) R=1
-1 (x4)]
(1)
2.1 ONE-SIDED FEEDDACK
Whenever take action y stage h, the environment randomness D, is realized, can learn the rewards/transitions for all the actions that lie on one side of y, i.e., all y' S y for the lower one-sided feedback setting (or all action space can be embedded in compact subset of IR (Appendix B), and that the reward/transition only depend on the action, the time step and the environment randomness, even though the feasible action set depends on the state and is assumed to be an interval A n [a, 20) for some We assume that given Dr, the next state (-) increasing 3/. and (n(+) is increasing in setting. We assume the optimal value functions are concave. These assumptions seem strong, but are actually widely satisfied OR/finance problems, such as inventory control (lost-sales model), portfolio management, airline's overbook policy, online auctions, etc.
y for the higher side). This setting requires that the
a, (2x). )
Th for the siee--sidddffeedbal
2.2 FULL-FEEDBACK
Whenever we take an action stage h, once Dj is realized, we can learn the rewards/transitions for all state-action pairs. This special case does not require the assumptions in Section 2.1. Example problems include inventory control (backlogged model) and portfolio management.
3 ALGORITHMS
Algorithm 1 Ciimination-Based Half-Q-learning (HQL)
Initialization: (1) + H, v(y, h) E A []; 4 + A, [H; Abt + A, 4K E [K];
for 1,.... K do Initiate the list of realized environment randomness to be empty D3 = []: Receive x/;;
for = 1, L...., H do if [A)
} is not feasible then
Take action v closest feasible action to Al::
else
Take action f (a
Observe realized environment randomness Dj append it Da;
Update * h+1 <- 2//41 yh. D/y,
for h = H, ......... do for y E A do
Simulate trajectory
(x.,)) as if we had chosen y stage h using Dy until find **, v). which is the next time able choose from A (ax)))))
Update (x + (1 - (l--a))Qiie Qn)) + au aulFnettinn) + Vi+i V (2/+4) (a vh DRD)];
Update v arg max Q+(v):
Update A k+1 -- {u E A (Qr( Qn(v)) < Confidence Interval?):
Update (x( + maxteasible given Qn(y);

---

Under review as a conference paper at ICLR 2021
Without loss of generality, present HQL in the lower-sided-feedbice setting. We define constants Ork = -(H + (H + k), vk E [K]. We use f,, to denote the cumulative reward from stage to stage h'. We use Th41 (2, y, D to denote the next state given and D By assumptions in Section 2.1, Qn v) only depends on the for Algorithm 1, so we simplify the notation to (v)-
Main Idea of Algorithm At any episode ks have a "running set" A of all the actions that are possibly the best action for stage h. Whenever we take an action, we update the Q-values for all the actions A To maximize the utility of the lower-sided feedback, we always select the largest action in A letting us observe the most feedback. We might be state where we cannot choose from AA. Then we take the closest feasible action A (the smallest feasible action in the lower- sided-feedback case). By the assumptions in Section 2.1, this is with high probability the optimal action this state, and we are always able to observe all the rewards and next states for actions in the running set. During episode k, we act in real-time and keep track of the realized environment randomness. At the end of the episode, for each h, we simulate the trajectories as we had taken each action in A and update the corresponding value functions, as to shrink the running sets.
Algorithm 2 Full- L-aaring (FQL)
Initialization: (I, + H, E(
for k 1==1, 1, K do Receive z/:
for h = 1,... H. do
Take action uh
arg feasibe given x Qn (2 y); and observe realized Dj:
for E S do
for y E Ado do
Update Qn y) Update Vx(x) &- maXfeasible given x ())
(x) y) + a (,,,,
[ D() Va+1 (1/441 (2, D
Update #1 1 2/141 (att vh. D
Algorithm is a simpler variant of Algorithm where we effectively set the "Confidence Interval" to be always infinity and select the estimated best action instead of maximum of the running set. It can also be viewed as an adaption of Jin et (2018) the full-feedback setting.
MAIN RESULTS
Theorem 1. HQL has O O(H3 total expected regret on the episodic MDP problem in the one- sided-fee feebback setting. FQL has O total expected regret in the full-feedbaad setting. Theorem 2. For any (randomized or deterministic) algorithm, there exists fulll-feebback episodic MDP problem that has expected regret Q(VHT), even if the Q-values are independent of the state.
OVERVIEW OF PROOF
We use Qh. Vi to denote the Qi, Vn functions at the beginning of episode k
Recall ag = (H + 1) + k). As in Jin et al. (2018) and Dong et al. (2019), we define weights - III
(1 - a1) and provide some useful properties in Lemma 3. Note that Property is tighter than the corresponding bound in Lemma 4.1 from Jin et al. (2018), which we obtain by doing more careful algebraic analysis.
ag II 1== (1 - az), and at = as
Lemma 3. The following properties hold for at:
1. Eim of 1 and ai 0.for 1 2 1; Ei of 0 and of = 1 for 0.
2. max of < 2H and Ei= (at)² < 2H for every 1. For convenience, we "Confidence Interval" of - (VHo),, where llgg(AT).
4

---

Under review as a conference paper at ICLR 2021
3. Ees oj 11 + 1 for every i 2 1.
4. 1 v7 - E i=1 vi - Vi h
for every t 2 1.
All missing proofs for the lemmas in this section are in Appendix B. Lemma 4. (shortfall decomposition) For any policy π and any [K], the regret in episode is:
H
VIT - V17T -V (2f)
=E= E
Σ h=1
max 27 (2h v) - Q% (2h vii) )].
(2)
yEA
Shortfall decomposition lets us calculate the regret of our policy by summing up the difference between Q-values of the action taken at each step by our policy and of the action the optimal n' would have taken if it was the same state as us. We need to then take expectation of this random sum, but we get around this by finding high-probabilityy upper-bounds on the random sum as follows:
Recall for any (I,, h, k)) E S x [H] x [K], and for any y E A 7 (x, y) the next time stage after h in episode & that our policy lands on simulated next state (x.p)) thht allows us to take an action in the running set A (a.))) The time steps in between are "skipped" in the sense that we do not perform Q-value updating or V-value updating during those time steps when we take y at time (h, 6). Over all the h' E [H]. we only update Q-values and V-values while it is feasible to choose from the running set. E.g. if no skipping happened, then T (z. y) = h + 1. Therefore, Th (zr y) is a stopping time. Using the general property of optional stopping that [[M+] Mu for any stopping time r and discrete-time martingale M,, our Bellman equation becomes
Qi = Epp or - ((-()))()))))))) her + V (2(+
(3)
hing " gg.
where we simplify notation <,,,,, y) to r when there is no confusion, and recall fn. denotes the cumulative reward from stage h to h. On the other hand, by simulating paths, HQL updates the Q functions backward h HI,..... , 1 for any S,y E A at any stage h in any episode k as follows:
2h+1(0 (v) + (1 an) (v)) + aul (u 7f (x. + vk+1 (ma)) "
(x'
(4)
Then by Equation 4 and the definition of o 's,s, we have
pi(y) ah H
Σ o (hintte + Viti ((z,s) (dt()w))
(5)
which naturally gives us Lemma 5. For simpler notation, we use Th = (2)
Lemma S. For any (x, h k)) E x [M] x [K]. and for any y E AG we have
k-1
(Qh Qi) (v) =a 0_ 1 (H QA((M)
Σ aak-1/
(vitl
7/ (otx)) + 7t hirt
- -ho + (Vitlem + th.ri
Epp - (1110)) Ihhrk + V (1r
}1)}
Then we can bound the difference between our Q-value estimates and the optimal Q-values: Lemma 6. For any (x, h, k) S [H] x [K], and any E Ale ler L = 9lgg(AT) we have:
--1
H3,
(o) Q2) (v) S 0
[iit Vi (1) (1) + Fhing - -ih + + k
i=1
with probability at least 1 1/ (AT)), and we can choose c 2v2..
#+1 to be list of values that satisfy the recursive relationship Now we define {
8n H (1 1/H) + ev HH,,, for any h E [M],
where is the same constant in Lemma 6, and 6 0. Now by Lemma 6, we get:
5

---

max Under review as a conference paper at ICLR 2021
Lemma 7. For any (h, k) E [H] x [K]. fōr K is sequence of values that satisfy
(Qh (v) & /
with probability at least - (AA))))
yEA
Lemma 7 helps the following three lemmas show the validity of the running sets A
Lemma 8. For any h E [H] E [K], the optimal action yi, is in the running set A with probability at least -AT)
Lemma 9. Anytime we can play in Al. the optimal Q-value of our action is within 36,/VKk k 1 of the optimal Q-value of the optimal policy's 's action, with probability at least 2/ (AT)².
Lemma 10. Anytime we cannot play in A our action that is the feasible action closest to the running set is the optimal action for the state x with probability at least 1 1
Naturally, we want to partition the stages = ...... H each episode k into two sets, r and T r& contains all the stages h where we are able to choose from the running set, and D B contains where A all the stages h where we are unable to choose from the running set. So I L = [H]. 4k e [K].
Now we can prove Theorem 1. By Lemma 4 we have that
Vi
EE
max Qi (v) Q% (vii WEA
)
S E
max yEA
(hh (v) - Qh (11)
1=1
Q% (v) - Q% (vh) )] + E
Σ
Q% (v) - Q% (uh) )
max yEA
max
yEA
hEr%
NET B
By Lemma 10, the second term is upper bounded by
1
1
0- (1
Σ
H
Σ
H
(6)
A5T5
ASTS
A57'5
heT
By Lemma 7, the first term is upper-bounded bounded by
5n
Sn
E
P
max yEAR
@ (v)
Q% (uhi)
Vh
kerk
Σ KET'
H
P max
@7 (v) 0h (uh)
Vk
5n
S
Vk
Ön
+0
Σ Encra
H A
yEAR
Energ
Then the expected eumulative regret between HQI. and the optimal policy is:
K Σ -
K Σ - VF- (21)
Regret MDP(K) (K) =
(VT - (=))
k= 1
k=
K
H
5n
H
O(
H
S SO(H'VT)).
A
Vk -
A&T5
Vk 1
2=2
hEr
Exer
Enery
k=2
5.1 PROOFS FOR FQL
Our proof for HQL can be conveniently adapted to recover the same regret bound for FQL in the full-feedback setting. We need variant of Lemma 9: whenever take the estimated best feasible action in FQL, the optimal Q-value of our action is within 35,, of the optimal Q-value of the VA-I
optimal action, with probability at least 1 - 2/(7)5... Then using Lemmas 4,5,6 and 8 where all the (v) are replaced by Q* (x. y). the rest of the proof follows without needing the assumptions for the onn-sided-feedbbcc setting.
For the tighter O(H²VT() regret bound for FQL in Theorem 1, we adopt similar notations and proof Jin et al. (2018) (but adapted to the full-feedhack setting) to facilitate quick comprehension for readers who are familiar with Jin et al. (2018). The idea is to use (V/ -V** (*%) as a high probability upper-bounde on (Vi- vT**) ) (zf), and then upper-bound it using martingale properties and recursion. Because FQL leverages the full feedback, it shrinks the concentration bounds much faster than existing algorithms, resulting in significantly lower regret bound. See Appendix E.

---

Under review as a conference paper at ICLR 2021
6 EXAMPLE APPLICATIONS: INVENTORY CONTROL AND MORE
Inventory Control is one of the most fundamental problems in supply chain optimization. It is known that base-stock policies (aka. order-up-to policies) are optimal for the classical models we are concerned with (Zipkin (2000), Simchi-Levi et al. (2014)). Therefore, we let the actions for the episodic MDP be the amounts order inventory up to. At the beginning of each step h. the retailer sees the inventory 2 E R and places an order to raise the inventory level up to yh 2 Th-- Without loss of generality, we assume the purchasing cost is (Appendix C). Replenishment of yn 24, units arrive instantly. Then an independently distributed random demand Dn from unknown distribution Fn is realized. We use the replenished inventory yh to satisfy demand Dn. At the end of stage h, demand Da is less than the inventory, what remains becomes the starting inventory for the next time (y/- Dr) and we pay holding cost oß for each unit of left-over inventory.
period Th+1
Backlogged model: if demand Dd exceeds the inventory, the additional demand is backlogged. so the starting inventory for the next period is T4+1 = 4/h - Dp. < O. We pay a backlogging cost by > for each unit of the extra demand. The reward for period h is the negative cost:
Th ( yh) = - (cn mn.) + on (y/= - Da)* by (Dn - yn)")
This model has full feedback because once the environment randomness the demand is realized, we can deduce what the reward and leftover inventory would be for all possible ttate-action pairs.
Lost-sales model: is considered more difficult. When the demand exceeds the inventory, the extra demand lost and unobserved instead of backlogged. We pay a penalty of ph > 0 for each unit of lost demand, so the starting inventory for next time period is #h+1 = 0. The reward for period h is:
Th (Th yh.) = - -cs (yh mA) + on (u Da)+ + Ph (D, - 31))))
Note that we cannot observe the realized reward because the extra demand (Dn - ynh)* + is unob- served for the lost-sales model. However, can use pseudo-reward (T ya) - (on(yn (yn D₂)* Ph, min(yk. Dr)) that will leave the regret of any policy against the optimal policy un- changed (Agrawal & Jia (2019), Yuan et al. (2019)). This pseudo-reward can be observed because we can always observe min(yh, Dn). Then this model has (lower) one-sided feedback because once the environment randomness-the demand is realized, we can deduce what the reward and leftover inventory would be for all possible state-action pairs where the action (order-up-to level) is lower can also observe min (1/, Dr) for all 3/h S y/h
than our chosen action,
Past literature typically studies under the assumption that the demands along the horizon are i.i.d. (Agrawal & Jia (2019), Zhang et al. (2018)). Unprecedentedly, our algorithms solve optimally the episodic version of the problem where the demand distributions are arbitrary within each episode.
Our result: it is easy on the action, the time step and the realized demand, not on the shate-the starting inventory. How- ever, the feasibility of action depends the state, because lower than the starting inventory. The feasible action set at any time is An [rr,, o0). The next state xh41(-) and (-) are monotonely non-decreasing, and the optimal value functions are concave.
that for both backlogged and lost-sales models, the reward only depends
can only order up quantity no
Since inventory control literature typically considers a continuous action space [0, M] for some M E RR+,, we discretize [0, .] with step-size 7r, so A = [A| = T Discretization incurs additional regret Regret gap ( M
HT) = o(1) by Lipschitzness of the reward function. For the lost-sales model, HQL. gives O 3 / log T') regret. For the backlogged model, FQI. gives 2 T) regret, and HQL gives OHH3, VT log 7') regret. See details in Appendix C.
T2
Comparison with existing Q-learning algorithms: If we discretize the state-action space optimally for Jin et al. (2018) and for Dong et al. (2019), then applying Jin et al. (2018) to the backlogged model gives a regret bound of (T3/4 O(T3/4//logT) T). Applying Dong et al. (2019) to the backlogged inventory model with optimized aggregation gives us (TT2/3 VlogT), See details in Appendix D.
Online Second- Pecced-Price Auctions: the auctioneer needs to decide the reserve price for the same item at each round (Zhao& & Chen (2019)) Each bidder draws a value from its unknown distribution and only submits the bid if the value is no lower than the reserve price. The auctioneer observes the bids, gives the item to the highest bidder if any, and collects the second highest bid price (including the reserve price) as profits. In the episodic version, the bidders' distributions can vary with time in an
7

---

Under review as a conference paper at ICLR 2021
episode, and the horizon consists of K episodes. This is (higher) cee-sidddffeeddaee problem that can solved efficiently by HQL because once the bids are submitted, the auctioneer can deduce what bids it would have received for any reserve price higher than the announced reserve price.
Airline Overbook Policy: is to decide how many customers the airline allows to overbook a flight (Chatwin (1998)). This problem has lower-sided feedback because the overbook limit is reached, extra customers are unobserved, similar to the lost-sales inventory control problem.
Portfolio Management is allocation of fixed sum of cash variety of financial instruments (Markowitz (1952)). In the episodic version, the return distributions are episodic. On each day, the manager collects the increase the portfolio value the reward, and gets penalized for the decrease. This is full-feed fellbeeebback problem, because once the returns of all instruments become realized for that day, the manager can deduce what his reward would have been for all feasible portfolios.
NUMERICAL EXPERIMENTS
We compare FQL and HQL on the backlogged episodic inventory control problem against 3 bench- marks: the optimal policy (OPT) that knows the demand distributions beforehand and minimizes the cost in expectation, QL-UCB from Jin al. (2018), and Aggregated QL from Dong et al. (2019).
For Aggregated QL and QL-UCB, we optimize by taking the Q-values to be only dependent on the action, thus reducing the state-action pair space. Aggregated QT. requires a good aggregation of the state-action pairs to be known beforehand, which is usually unavailable for online problems. We aggregate the state and actions to be multiples of for Dong et (2019) in Table 2. We not
fine-tune the confidence interval in HQL, but use a general formula (og(HKA) for all settings. B
We do not fine-tune the UCB-bonus in QL-UCB either. Below is summary list for the experiment settings. Each experimental point run 300 times for statistical significance.
Episode length: H = 1, Number of episodes: K 100, 500, 2000.
Holding cost: Oy = 2.
Backlogging cost: bj. 10.
Demands: Dn ~ (10 h UO0 1).
Action space: [0, 20 20
1 2
10].
Table 2: Comparison of cumulative costs for backlogged episodie inventory control
OPT
FQI.
HQI.
Aggregated Qt.
QL-UCB
H
mean
SD
mean
SD
mean
SD
mean
SD
mean
SD
100
88.2
4.1
103.4
6.6
125.9
19.2
406.6
16.1
3048.7
45.0
500
437.2
4.4
453.1
6.6
528.9
44.1
1088.0
62.2
4126.3
43.7
2000
1688.9
2.8
1709.5
5.8
1929.2
89.1
2789.1
88.3
7289.5
57.4
100
257.4
3.2
313.1
7.6
435.1
17.6
867.9
29.2
7611.1
46.7
3
500
1274.6
6.1
1336.3
10.5
1660.2
48.7
2309.1
129.8
10984.0
73.0
2000
4965.6
8.3
5048.2
13.3
5700.6
129.1
7793.5
415.6
22914.7
131.1
100
421.2
3.3
528.0
10.4
752.6
32.9
1766.8
83.8
11238.4
140.0
5
500
2079.0
8.2
2204.0
13.1
2735.1
114.1
4317.5
95.8
15458.1
231.8
2000
8285.7
8.3
8444.7
16.4
9514.4
364.2
13373.0
189.2
40347.0
274.6
Table shows that both FQL and HQL perform promisingly, with significant advantage over the other two algorithms. FQL stays consistently very close the clairvoyant optimal, while HOL catches up rather quickly using only one-sided feedback. See more experiments in Appendix F.
8 CONCLUSION
We propose a new Q-learning based framework for reinforcement learning problems with richer feedback. Our algorithms have only logarithmic dependence on the state-action space size, and hence are barely hampered by even infinitely large state-action sets. This gives us not only efficiency, but also more flexibility in formulating the MDP to solve a problem. Consequently, we obtain the first O (VVT) regret algorithms for episodic inventory control problems. We consider this work to be proof--of-oncce showing the potential for adapting reinforcement learning techniques to problems with a broader range of structures.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Shipra Agrawal and Randy Jia. Learning in structured mdps with convex cost functions: Improved regret bounds for inventory management. arXiv preprint arXiv: 04337, 2019.
Richard E. Chatwin. Multiperiod airline overbooking with single fare class. Operations Research, 4666))805-819, 1998. doi: 10. 1287/0pre.46.66.855. URL wwt.tttss/ppuscnneeee http//ubbbnnnnneeeme/eee informs. org/doi/abs /10. 1287 1ww.//pr8..... 46. 805.
/
Maxime C. Cohen, Ilan Lobel, and Renato Paes Leme. Feature-based dynamic pricing. Manage- ment Science, 0(0)null, 2020. doi: 10.1287/mmss:2219..4488 URL 1287 mnsc 2 2019.31.2 3485.
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. Provably efficient reinforcement learning with aggregated states, 2019.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT '02, pp. 2-00 Berlin, Heidelberg, 2002. Springer-Verlag ISBN 354043836X.
Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. Learning to bid without knowing your value. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC 188, pp. 505-522, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450358293. doi: N0.1145/3219166.33 662112226662 URL https: /doi. org/10. / 321 66 322 9208.
Tommi Jaakkola, Michael I. Jordan, and Satinder P. Singh. Convergence of stochastic iterative dynamic programming algorithms. In Proceedings of the 6th International Conference on Neural Information Processing Systems, NIPS'93, 93, pp. 703-710, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc.
cient? In Advances in Neural Information Processing Systems, pp. 1866348733 2018. Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi-
Ilan Lobel, Renato Paes Leme, and Adrian Vladu. Multidimensional binary search for contextual decision-making. CoRR, abs/1611.00822 2016. URL http::::/wxxi..orgg//o a1611 00829.
Thodoris Lykouris, Max Simchowitz, Alcksandrs Slivkins, and Wen Sun. Corruption robust explo- ration in episodic reinforcement learning, 11 2019.
Harry Markowitz. Portfolio selection*. The Journal of Finance, 7(1):77-91, 1952. doi: 10.1111/ URL https:://nnaiiii oonineniniarrrr wapaaaywywwii wiley com/ /t// abs/ 10. 10.1111/3 1540 1922 tb01525.xx
6,1540-6261.1952.6b0000
Aaron Sidford, Mengdi Wang, Xian Wu, Lin F. Yang. and Yinyu Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp- 5192-5202, Red Hook, NY, USA, 2018. Curran Associates Inc.
David Simchi-Levi, Xin Chen, and Julien Bramel. The logic of logistics. theory, algorithms, and applications for logistics and supply chain management. 2nd ed. 2014.
Sean Sinclair, Siddhartha Banerjee, and Christina Yu. Adaptive discretization for episodic rein- forcement learning in metric spaces. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3:1-44, 12 2019. doi: 10.1145/3366703.
Aleksandrs Slivkins. Introduction multi-armed bandits. arXiv preprint arXiv: 2019.
Christopher Watkins and Peter Dayan. Technical note: Q-learnin. Machine Learning, 8:279-292, 05 1992. doi: 10. (0.10077BF00999698.
J. Weed, Vianney Perchet, and Rigollet. learning in repeated auctions. 2016.
Hao Yuan, Qi Luo, and Cong Shi. Marrying stochastic gradient descent with bandits: Learning algorithms for inventory systems with fixed costs. Available at SSRN, 2019.

---

Under review as a conference paper at ICLR 2021
Huanan Zhang, Xiuli Chao, and Cong Shi. Closing the gap: A learning algorithm for the lost-sales inventory system with lead times. Available at SSRN 2922820, 2018.
Haoyu Zhao and Wei Chen. Stochastic one-sided full-information bandit. CoRR, abs/ 190,006606.0 2019. URL http: /tt///aaxiiii http:///.x...//aa/////asaee/ss//
wtt.:oogg/gbaaoooceoeoe 1996. 68
Zipkin.
Foundations of Inventory Management. McGraw-Hill Companies,Incorporatee
2000. ISBN 9780256113792.
URL https:/ /tto///ooooks////o google. wwtp:e/.coooooo.e.eeeoeee ? idd=
rjZbKQEACAAJ.
10


Reviews:
[{"review_id": "pCrX_TCzYsL", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Q-learning based algorithms called Elimination-Based Half-Q-Learning (HQL) and Full-Q-Learning (FQL). In the one-sided-feedback setting, the proposed algorithm improves the regret bounds over existing methods in terms of the dependency on the size of state-action space. Numerical experiments are provided to show the performance of the algorithm.\n\nOverall, I vote for rejecting. The detailed comments are as follows:\n\nPros:\n- By incorporating domain-specific structures into Q-learning algorithms, the author developed new algorithms tailored to one-sided-feedback/full-feedback models. The algorithm improves the regret bound in terms of the dependency on the state-action space.\n\nCons:\n- Although the algorithm improves the regret bounds with respect to the state-action space, the time complexity grows linearly with S and A (in Table 1). Therefore, I'm skeptical of the claim that \"the algorithms are barely hampered by even infinitely large state-action sets\".\n\n- The exposition in Section 4 could be improved. In the current version, there are only statements of two theorems. I think the authors should spend more space in Section 4 instead of Section 5. It would be helpful if authors can provide interpretation of the theorems and detailed comparison with existing results. And it would be nicer to provide examples that satisfy the assumptions made in Section 2.\n\n- I felt that the numerical experiment is not so convincing. For example, the episode length seems to be too small (H <= 5). In addition, since authors claim that the algorithms scale well to large state-action sets, it would be better to conduct the numerical experiment in that regime to show the efficiency of the algorithm.\n\n- The writing quality could be improved. There are several grammar mistakes and typos.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gk99AyMi7z", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##################################################################################\n\nSummary:\n\n\nThis paper is motivated by using reinforcement learning (RL) methods in inventory control. In particular, it customizes Q-learning for a special one-sided feedback/full-feedback setting. This combination of two areas is intriguing. The main contribution of the paper is a new algorithm leveraging the model structure, so that the regret no longer depends on the size of state and action space. \n\n\n##################################################################################\n\nReasons for score: \n\n \nI like the idea of introducing RL methods to classical operations research problems. The application of Q-learning in inventory control seems promising. My major concern is about the clarity of the paper and the novelty of theoretical analysis (See cons below). I think the paper is not suitable for ICLR in this current version.\n\n\n##################################################################################\n\nStrengths:\n\n\n- The one-sided feedback/full-feedback model is of high practical value. It is an abstraction and generalization of inventory control and applies to many other famous problems.\n- The proposed HQL and FQL algorithms are novel and well-motivated by the one-sided-feedback/full-feedback assumption.\n- The theoretical and empirical comparison with existing Q-leaning methods shows the benefits of utilizing model structures.\n\n\n##################################################################################\n\nWeakness:\n\n- The theoretical analysis is similar to Jin et al. (2018). It is not evident to me what new challenges are in the proof. Besides, the authors use Azuma-Hoeffding's inequality instead of Bernstein one so that the dependence on H is very loose.\n- In numerical experiments, the results would be more convincing if the authors could take a longer length of episode (currently H = 1, 3 or 5) and compare with traditional inventory control algorithms in the same setting.  \n- The writing needs significant improvement.\n\t* The model assumptions should be highlighted. The one-sided-feedback/full-feedback models are unconventional. It would help readers to better comprehend problem set-up if subsections 2.1 & 2.2 are written in a more organized way.\n\t* Section 4: Main Results lacks necessary discussion.\n\t* Section 5: Overview of Proof is lengthy and there is neither an evident clue nor an outline. Some technical results are more suitable to appear in appendix.\n\t* In the reviewer's humble opinion, Section 6: Example Applications could be placed before model description, so that the motivations are clearer at first glimpse.\n\n\n##################################################################################\n\nTypo: \n* Algorithm 1, Q-function update step, the subscript of value function $V$\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bZFihBqOOUi", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes two algorithms, Half-Q-Learning and Full-Q-Learning for the classic inventory control problem. It establishes cardinality-independent regret bonds for the two algorithms in terms of length of episode and horizon. Numerical results are presented to demonstrate the effectiveness of the algorithms. \n\nPlus\n- The paper is well written and the ideas are explained clearly. The proof flow is also explained clearly. \n- The inventory control problem in consideration is important. Exploiting the feedback structure in this problem is interesting. \n\nMinus\n- The regret performance w.r.t. H and running time are worse than prior works. \n- The experimental section could be improved, e.g., compare the algorithms with larger H values and running times. \n\nDetailed comments \n- The lowercase letter “k” above Eq. (1) should be “K”. \n- The reviewer would suggest the authors to place the inventory control problem before the formulation. This way, it is easier to see what assumptions are reasonable and satisfied by the target application. \n- It will be interesting if the authors could discuss why FQL and HQL are able to eliminate the SA factor from the regret but results in a larger regret w.r.t. H. Intuitively, the former is due to the feedback structure and a larger computational cost. But the latter is less clear and it would be nice to provide some intuition. \n- The experimental setting appears to be quite simplistic. The reviewer would suggest experimenting more scenarios to evaluation the performance. \n- The experiments use a fairly small H. The reviewer wonders what happens if the H value is larger? From the comparison results with Aggregate QL and QL-UCB in Table 1, it seems that FQL and HQL should perform worse than QL-UCB. It would also be interesting to compare the running time of the algorithms. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "4oy8fg55ypa", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After rebuttal:\n\nMy main concerns are addressed, and I changed my score to 5 accordingly.\n\n------\nMotivated by OR problems, this paper extends Q-learning algorithm to one-sided-feedback and full-feedback settings. With additional assumptions, this paper proves a $\\sqrt{T}$-regret bound with no dependence on the size of state/action spaces. Both proposed algorithms are theoretically and empirically shown to be more efficient than general Q-learning algorithms.\n\nThe novelty of this paper lies in applying reinforcement learning algorithms to the inventory control problem. It is interesting to see how can Q-learning algorithm be customized to problems with more structure. Technically, it is also novel to use elimination based algorithms in tabular reinforcement learning. However, the assumptions of this paper is a bit too strong, which is the major weakness of this paper. For example, it is assumed that the next state $x_{h+1}(\\cdot)$ is increasing in $y_h$, and the feasible action set is also monotonic, which means that the state and action spaces must be 1-dimensional. It is also assumed that both the transition and the reward depend only on action and environment randomness. But in the example (e.g. Backlogged model), the reward is a function of $x_h,y_h$. As a result, I'm not totally convinced that the assumptions in this paper is general and realistic.\n\nAfter spending considerable amount of time, I still have some concerns about the technical soundness. To be more specific:\n1. In Line 13 of Alg. 1, how is trajectory simulated? To be more specific, how does the algorithm choose action $y$ for step $h+1,\\cdots,\\tau_{h}^{k}(x,y)$ and how is the next state generated?\n2. Proof of Lemma 7 (page 3 of appendix): in the inequality before Eq. (12), how is the term $\\tilde{r}^i-\\tilde{r}^*$ bounded? If I understand correctly, $\\tilde{r}^i$ is the cumulative reward of the trajectory generated by the algorithm, and $\\tilde{r}^*$ is the reward generated by the optimal policy. When the trajectory is longer than 1 time step, the actions of the two trajectories on step $h+1$ may be different when the algorithm has not converged to optimal.\n\nAdditional comments:\n1. Since the state space is infinite and continuous, I'm wondering how function approximation RL algorithms behave in this setting.\n2. It is mentioned in Sec. 6 that the state space $x_h\\in \\mathbb{R}$ is continuous, but how to execute the HQL algorithm for continuous state space? Although the regret has no dependence on the size of state and action space, the time and space complexity do.\n3. In the bandit setting, the elimination algorithm has instance dependent regret (i.e., sum_i (1/Delta_i) log(T)). I'm wondering whether HQL algorithm has similar guarantee?\n4. Why is lost-sales model one-sided? What can the RL agent observe in this setting? If the agent can observe $D_h$, isn't it the case where the agent can compute the reward function for all possible $y$? If the agent can only observe min(y, D), how can the agent infer min(y-1,D)?\n\nIn summary, my main concerns are about the assumptions and technical soundness. Therefore, I would not recommend acceptance for the paper at this point.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper explores the performance of Q-learning in the presence of either one-sided feedback or full feedback. Such feedbacks play an important role in improving the resulting regret bounds, which are (almost) not affected by the dimension of the state and action space. The motivation of such feedback settings stems from problems like inventory control. However, the assumptions underlying the theory herein are often quite strong, which might limit the applicability of the theory. The dependency on the length per episode H can also be improved.   
Decision: Reject