Weakly Coupled Deep Q-Networks
Authors: Ibrahim El Shar
Daniel R. Jiang
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement learning
Deep Reinforcement Learning
Weakly Coupled MDPs
TL;DR: We propose Weakly Coupled Deep Q-Networks (WCDQN) a new deep RL algorithm for weakly coupled MDPs

Abstract: We propose weakly coupled deep Q-networks (WCDQN), a novel deep reinforcement learning algorithm that enhances performance in a class of structured problems called weakly coupled Markov decision processes (WCMDP). WCMDPs consist of multiple independent subproblems connected by an action space constraint, which is a structural property that frequently emerges in practice. Despite this appealing structure, WCMDPs quickly become intractable as the number of subproblems grows. WCDQN employs a single network to train multiple DQN ``subagents,'' one for each subproblem, and then combine their solutions to establish an upper bound on the optimal action value. This guides the main DQN agent towards optimality. We show that the tabular version, weakly coupled Q-learning (WCQL), converges almost surely to the optimal action value. Numerical experiments show faster convergence compared to DQN and related techniques in settings with as many as 10 subproblems, $3^{10}$ total actions, and a continuous state space.

Weakly Coupled Deep Q-Networks
Ibrahim EI Shar
Daniel Jiang Meta, University of Pittsburgh New York, NY dr serjannd@meta.cm com
Hitachi America Ltd., University of Pittsburgh
Sunnyvale, CA
ibrahim Strahim.elshar@iie elshar@hal tathhic..com com
Abstract
We propose weakly coupled deep Q-networks (WCDQN), novel deep rein- forcement learning algorithm that enhances performance class of structured problems called weakly coupled Markov decision processes (WCMDP). WCMDPs consist of multiple independent subproblems connected by an action space con- straint, which structural property that frequently emerges in practice. Despite this appealing structure, WCMDPs quickly become intractable as the number of subproblems grows. WCDQN employs single network to train multiple DQN "subagents." one for each subproblem, and then combine their solutions to establish an upper bound on the optimal action value. This guides the main DQN agent towards optimality. We show that the tabular version, weakly coupled Q-learning (WCQL), converges almost surely the optimal action value. Numerical experi- ments show faster convergence compared to DQN and related techniques in settings with as many as 10 subproblems, 300 total actions, and a continuous state space.
Introduction
Despite achieving many noteworthy and highly visible successes, it remains widely acknowledged that practical implementation of reinforcement learning (RI) is, in general, challenging [15]. This particularly true in real-world settings where, unlike in simulated settings, interactions with the environment are costly to obtain. One promising path toward more sample-efficient learning in real-world situations is incorporate known structural properties of the underlying Markov decision process (MDP) into the learning algorithm. As elegantly articulated by [44], structural properties can be considered a type of "side information" " that can be exploited by the RL agent for its benefit. Instantiations of this concept are plentiful and diverse: examples include factored decompositions [33, 10. 47], latent or contextual MDPs [21, 39, 52], block MDPs [14], linear MDPs [32], shape-constrained value and/or policy functions [49, 37, 31], MDPs adhering to closure under policy improvement [8], and
or hierarchical MDPs [23, 13], to name just few.
In this paper, we focus on class of problems called weakly coupled MDPs (WCMDPs) and show how one can leverage their inherent structure through tailored RL approach. WCMDPs, often studied in the field of operations research, consist of multiple subproblems that are independent from each other except for coupling constraint on the action space [24]. This type of weakly coupled structure frequently emerges in practice, spanning domains like supply chain management [24], recommender systems [65]. online advertising [9], revenue management [53], and stochastic job scheduling [63]. Such MDPs can quickly become intractable when RL algorithms are applied naively, given that their state and action spaces grow exponentially with the number of subproblems [45].
One can compute an upper bound on the optimal value of a WCMDP by performing a Lagrangian re- laxation on the action space coupling constraints. Importantly, the weakly coupled structure allows the relaxed problem to be completely decomposed across the subproblems, which are significantly easier solve than the full MDP [24, 1]. Our goal in this paper is devise a method that integrate the Lagrangian relaxation upper bounds into the widely adopted value-based RL approaches of Q-learning
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Full transition
T1
Subagent
T2
Subagent
Environment
Agent
TN
Subagent N
Subproblem transitions
Next action a
a1
a2
b b(w)
Figure 1: An illustration of our RI. approach for WCMDPs. Our approach takes single "full" transition (as collected by standard RL agent) and decomposes it into subprohlem transitions that passed to "subagents," which powered by single network and aim solve the easier subproblems. The results of these subagents are used collectively to guide main agent toward the optimal policy, whose actions need to satisfy linking construints. Here, we illustrate the case of a single linking constraint that requires the sum of the actions to be bounded by right-han gighthandd-side quantity b(w), where w is an exogenous state from the environment.
[59] and deep Q-networks (DQN) [43]. Our proposed method is, to our knowledge, the first to explore the use of Lagrangian relaxations to tackle general WCMDPs in fully model-free, deep RL setting. Main contributions. We make the following methodological and empirical contributions.
1. First, we propose novel deep RL algorithm, called weakly coupled deep Q-networks (WCDQN), that exploits weakly coupled structure by using a set of subagents, each attached of the subproblems, whose solutions combined to help improve the performance main DQN agent; see Figure for a high-level overview.
2. Second, we also propose and analyze a tabular version our algorithm called weakly coupled Q-learning (WCQL), which serves to conceptually motivate WCDQN. We show that WCQL converges almost surely to the optimal action-value.
3. Finally, we conduct numerical experiments on a suite realistic problems, including electric vehicle charging station optimization, multi-provd product inventory control, and online stochastic ad matching. The results show that our proposed algorithm outperform baselines by a relatively large margin in settings with many as 10 subproblems, 310 total actions, and continuous state space.
2 Related Literature
Weakly Coupled MDPs. This line of work began with [61] under the name of restless multi-armed bandits (RMAB), where there two actions ("active" "passive") for each subproblem (also known as "project" or "arm"), under a budget constraint on the number of active arms at any given time.! As will see soon, this is special case of WCMDP with two actions per subproblem and a single budget constraint. A popular solution approach to RMABs is the Whittle index policy, which was first proposed by [61] and the idea of ranking arms by their "marginal productivity." The policy has been extensively studied in the literature from both applied and theoretical perspectives (20, 41, 29, 28, 42, 64]. Whittle conjectured in [61] that the Whittle index policy is asymptotically optimal under a condition called indexability; later, [60] established that asymptotic optimality requires indexability, but also another technical condition, both of which are difficult to verify.
We note that WCMDPs should not be confused with constrained MDPs, where budget constraint is imposed the overall cost of the policy in all periods [2].

---

As discussed in detail by [64], relying on the Whittle index policy in real-world problems can be problematic due to hard-to-verify technical conditions (and if not met, computational robustness and the heuristic's s original intuitive motivation may be lost).
A number of recent papers have considered using RL in the setting of RMABs, but nearly all of them are based on Whittle indices [19, 46, 34, 35, 3, 50, 62], and are thus most useful when the indexability condition can be verified. Exceptions are [34] and [35], which propose run RL directly on the Lagrangian relaxation of the true problem to obtain a "Lagrange policy." Our paper is therefore closest in spirit to these two works, but our methods target the optimal value and policy (with the help of Lagrangian relaxation) rather than pursuing the Lagrange policy as the end goal (which does not have optimality guarantees in general). Moreover, compared the other RL approaches mentioned above, we do not require the indexability condition and our method works for any WCMDP.
Relaxations of WCMDPs can be performed in several different ways, including approximate linear programming (ALP) [1, 11], network relaxation [45], and Lagrangian relaxation [61, 53, 24, 7, 1, 54, 11J. Notably, [1] provided key results for the ALP and Lagrangian relaxation approaches. and [1I] gave theoretical justification for the closeness of the bounds obtained by the approximate linear programming and Lagrangian relaxation approaches. an empirical observation made in [1]. Our work focuses specifically on the Lagrangian relaxation approach, which relaxes the linking constraints on the action space by introducing a penalty in the objective.
DQN and Q-learning. The Q-learning algorithm [59] is perhaps the most popular value-based tabular RL. algorithm [30, 55, 6). and the DQN approach of [43] extends the fundamental ideas behind Q-learning to the case where Q-functions are approximated using deep neural networks, famously demonstrated on set of Atari games. Unfortunately, practical implementation of Q-learning, DQN, and their extensions on real-world problems can be difficult due to the large number of samples required for learning [44].
Various papers have attempted to extend and enhance the DQN algorithm. For example, to overcome the over-estimation problem and improve stability, [57] proposes double DQN, which adapts the tabular approach of double Q-learning from [22] to the deep RL setting. The main idea is to use a different network for the action selection and evaluation steps. [51] modifies the experience replay buffer sampling to prioritize certain tuples, and [58] adds a "dueling architecture" to double DQN that combines two components, estimator for the state value function and estimator for the state- dependent action advantage function. Other examples include bootstrapped DQN [48), amortized Q-learning [56), distributional RL [5), and rainbow DQN [26].
Our approach, WCDQN, is also an enhancement of DQN, but differ from the above works in that our focus is modifying DQN to exploit the structure of a class of important problems that are otherwise intractable, while the existing papers focus on improvements made to certain components of the DQN algorithm (e.g., network architecture, experience replay buffer, exploration strategy). In particular, it should be possible to integrate the main ideas of WCDQN into variations of DQN without much additional work.
Use of constraints and projections in RL. WCDQN relies on constraining the learned Q-function to satisfy learned upper bound. The work of [25] uses a similar constrained optimization approach to enforce upper and lower bounds on the optimal action value function in DQN. Their bounds are de- rived by exploiting multistep returns of general MDP, while ours are due to dynamically-compune Lagrangian relaxations. [25] also does not provide any convergence guarantees for their approach.
In addition, [16] proposed convergent variant of Q-learning that leverages upper and lower bounds derived using the information relaxation technique of [12] to improve performance of tabular Q-learning. Although our work shares the high-level idea of bounding Q-lcarning iterates, [16] focused on problems with partially known transition models (which are necessary for information relaxation) and the approach did not readily extend to the function approximation setting. Besides focusing on a different set of problems (WCMDPs), our proposed approach is model-free and naturally integrates with DQN.
Preliminaries
In this section, we give some background on WCMDPs, Q-learning, DQN, and the Lagrangian relaxation approach. All proofs throughout the rest of the paper are given in Appendix A.
3

---

3.1 Weakly Coupled MDPs
We study an infinite horizon WCMDP with state space X' is the endogenous part (i.e., affected by the agent's ' actions) and W is the exogenous part (i.e., unaffected by the agent's actions) of the full state space. We use the general setup of WCMDPs from [11]. A WCMDP can be decomposed into N subproblems. The state space of subproblem i is denoted by S. X; x W and the action space is denoted by A,, such that
SpaceS = X' W and finite action space A, where
X' ===00 = and A= =
In each period, the decision maker observes w E W, along with the endogenous states a = (21, 22,, INN), where I; E X; is associated with subproblem Note that w is shared by all of the subproblems, and this is reflected in the notation we use throughout the paper, where 8 = (æe, w) E S represents the full state and 8; = (I), w) is the state of subproblem In addition to the exogenous state w being shared across subproblems. there also exist L linking or coupling constraints that connect the subproblems: they take the form Ex d(si, a.) < b(w), where d(si, a;), b(w) R_ and a, E A, is the component of the action associated with subproblem i. The set of feasible actions for state s is given by
exogenously and independently evolving state
{a
A(s) = a 1 A: Σ a, S b(w)}
After observing state s = (ax, w), the decision maker selects a feasible action a E A(s)..
The transition probabilities for the endogenous component is denoted p(æ' I a) and we assume that transitions are conditionally independent across subproblems:
p(a' xz, a) = -1 (x (i)
where (a (,,aa, a.) the transition probabilities for subproblem i. The exogenous state transi- tions according to q(w' w). Next, let r3(5), a4) be the reward of subproblem i and let r(s, a) = {re(ss; ,.)) The reward of the overall system is additive: r(s.a) Σm (r(s.,
Given discount factor y E [0, 1) and feasible policy क S A that maps each state s a feasible action a E A(s), the value (cumulative discounted reward) of following when starting in state and taking a first action a is given by the action-value function (= a) = E - E 7"r(St, az) ग. 80
8, ag a]. Our goal is to find an optimal policy x², i.e., one that maximizes V*(() = Q" (s, T (s)). We let (* a) = max, Q" (s, a) and (*) = max,, V*((s be the optimal action-value and value functions, respectively.
well-known that the optimal policy selects actions in accordance to T (s) arg max, Q" (8, a) and that the Bellman recursion holds:
Q" (s. a) = r(s. a) + 7E eaAa" Q'(s', ('s).
where s' = (x', w') is distributed according to p(- a) and g(- w).
3.2 Q-learning and DQN
The Q-learning algorithm of [59] is a tabular approach that attempts to learn the optimal action-value function Q' using stochastic approximation on (2). Using a learning rate on, the update of the approximation On from iteration to 1 is:
Qu+1 an,) Qn.ss,, an) + a, [y) (sn; an)]]
where yo = Yn + max,' Qn (8n+ a') is the target value, computed using the observed reward rn (sn, a. the transition to 8x+1, and the current value estimate Qn.
The DQN approach of [43] approximates Q' via a neural network Q(s, a; 0) with network weights 0. The loss function used to learn 0 is directly based on minimizing the discrepancy between the two sides of (2):
I(0) F Ex,,app (u Q(s, Q(,,a;(s))) ())
where = r(s, a) + 7 [maxa Q(s', aa: {] 0 are frozen network weights from a previ- ous iteration, and p is a behavioral distribution [43]. In practice, we sample experience tuples (8n, an, Fw, 84+1) from a replay buffer and perform a stochastic gradient update:
0a+1 = On + an I3n - Q(sn: a,; 0) VoQ(s,, an; 0).
with yn rn max Q( a'; 0-). Note the resemblance of this update that of Q-learning.

---

3.3 Lagrangian Relaxation
The Lagrangian relaxation approach decomposes WCMDPs by relaxing the linking constraints to obtain separate, casier-to-solve subproblems [1]. The main idea is to dualize the linking constraints E d(s,, a4) I b(w) using penalty vector À IR. The result is an augmented objective consisting of the original objective plus additional terms that penalize constraint violations. The Bellman equation of the relaxed MDP in (2) is given by:
(~ r(s, a) + A b(w) E Eiss ai) + maaxore
(3)
With the linking constraints removed, this relaxed MDP can be decomposed across subproblems, so we are able to define the following recursion for each subproblem i:
Q a,) ri(s;. - XT((s; + E
max Q (5 a LeEA
(4)
It is well-known from classical results that any penalty vector À 2 0 produces MDP whose optimal value function is an upper bound on the (*(s) (a) [24, 1]. The upcoming proposition is small extension
of these results to the case of action-value functions, which is necessarily for Q-learning.
Proposition 1. For any X 2 O and E S, it holds that (s, a) S Q* for any a E A(s). In addition, the Lagrangian action- value function of (3) satisfies
N
Q)(s,a) = ATB(w) + Σ as)
(5)
i=1
where Q (si, (i) is defined in (4) and (ww) satisfies the recursion
B = b(w) (BB)'
(6)
with the exogenous next state w/ is distributed according to q(. (w).
The first part of the proposition often referred weak duality and the second part shows how the I Lagrangian relaxation can be solved by decomposing it across subproblems, dramatically reducing the computational burden. The tightest upper bound is the solution of the Lagrangian dual problem, QA" (s, a) min (s, a), where X is minimizer.
4 Weakly Coupled Q-learning
In this section, we introduce the tabular version of our RL algorithm, called weakly coupled Q-leurning (WCQL), which will illustrate the main concepts of the deep RL version, WCDQN.
4.1 Setup
We first state an assumption on when the linking constraint (1), which determines the feasible actions given a state, is observed.
Assumption 1 (Linking constraint observability; general setting). Suppose that upon landing in state s = (xc, w), the agent observes the possible constraint left-hand hid--dd---ide values d( d(s;,-) for every i, along with the constraint right-hand- b(w) E R..
Under Assumption 1, the agent is able to determine the feasible action set A(s) upon landing in state 8. Accordingly, it can always take a feasible action. many cases, it is known in advance that the feasible action set is of the multi- multi-action RMAB form: there is single linking constraint (i.e.,
== 1) and the left-hand-side is the sum of subproblem actions (i.c., d(s,, 0.) = az). In that case, Assumption reduces to the following simpler statement, which we state for completeness.
Assumption 1' (Linking constraint observability; multi-action RMAB setting). Suppose that we are in multi-action RMAB setting. When the agent lands in a state (æx, w), it observes the constraint right-hand-side b(w)= E R.
5

---

In the numerical example applications of Section 6, for illustrative simplicity, we choose to focus on single-constraint settings where Assumption I' is applicable. Note that the "difficulty" of WCMDPs is largely determined by the number of subproblems and the size of the feasible set compared to the full action space, not necessarily by the number of linking constraints. applications, Assumption naturally holds: for example, in the EV charging problem, there are limited number available charging stations (which is always observable).
each of our example
An important part of WCQL track estimate of Q* (s, a), the result of the Lagrangian dual problem. To approximate this value, we replace the minimization over all X 2 0 by optimization over finite set of possible multipliers A, which we consider find that it is most straightforward to use À = X/1, where 1 E R2 is the all ones vector and X E R, but from the algorithm's 's point of view, any set A of nonnegative multipliers will do.
input to our algorithm. In practice, we
We denote an experience tuple for the entire WCMDP by T = (8, a, r. b, 8'). Similarly, we let (s;, 0g, ri, s be the experience relevant subproblem i, described in (4). Note that b is excluded from 77 because it does not enter subproblem Bellman recursion.
4.2 Algorithm Description
The WCQL algorithm can be decomposed into three main steps.
Subproblems and subagents. First, for each subproblem i E {1, NN and every À E A, we attempt to learn an approximation of Q7; a;) from (4), which are the Q-values of the unconstrained subproblem associated with A. We do this by running an instance of Q-learning with learning rate Bn. Letting Q be the estimate at iteration the update is given by:
Qi (s), a.) = Qi,, a.) + a.) [MCn - Q (st, ai)],
(7)
where the target value defined as vi... rr(ss, a4) ATd(s;, + 7 maxe! Qi (s, a().
Note that although we are running several Q-learning instances, they all make use a common experience tuple split across subproblems, where subproblem i receives the portion TG- We remind the reader that each subproblem is dramatically simpler than the full MDP, since operates on smaller state and action spaces (S, and A.) instead of S and A.
We refer to the subproblem Q-learning instances as subagents. Therefore, each subagent associated with subproblem i and penalty X E A and aims to learn Q²
Learning the Lagrangian bounds. Next, the level of the "main" agent, we combine the approxi- mations 2 learned by the subagents to form an estimate of the Lagrangian action-value function
Q^, defined in (5). To do so, first estimate the quantity B ((w) of Proposition 1. This can be done using a stochastic approximation step with a learning rate Tm, as follows:
(w) B,(w) + 77, (w) [bw)) + 7 B,,("") (w)]],
(8)
where we recall that w and w' come from the experience tuple t, embedded within s and s'. Now, using Proposition 1, we approximate (* a) using
Qh (s,, a) = AT AT Bu+I + Σ 1 az).
Finally, we estimate an upper bound on Q" by taking the minimum over A:
Q a) = min XEA (8,
(10)
Q-learning guided by Lagrangian bounds. We would now like to make use of the learned upper bound 1 a) when performing Q-learning on the full problem. Denote the WCQL estimate of Q" at iteration n by Ø², We first make standard update towards an intermediate value Q,+1 using learning rate an:
= Q, a) + an, a) Un - (s,a))
(11)
where Vn = r(s, a) + y max Q2, ('). To incorporate the bounds that we previously estimated, we then project Qn+1 a) to satisfy the estimated upper bound:
(,+1 1 (8,a) A (s)
(12)

---

where a A b = fa, b). The agent now takes an action in the environment using a behavioral policy, such as the e-greedy policy on 1 a).
The motivation behind this projection is as follows: since the subproblems are significantly smaller in terms of state and action spaces compared the main problem, the subagents are expected to quickly converge. As a result, our upper bound estimates will get better, improving the the action-value estimate of the main Q-learning agent through the projection step. In addition, WCQL can enable sort of "generalization" to unseen states by leveraging the weakly-coupled structure. The following example illustrates this piece of intuition.
Example 1. Suppose a WCMDP has N 3 subproblems with S; - (1, and A, - (1, for each i. leading to 3 2 = 216 total state action pairs. For the sake of illustration, suppose that the agent has visited states s = (1, 1, 1). s = (2, 2. 2). and (3. 3, and both actions from each of these states. This means that from the perspective of every subproblem i, the agent has visited all state-action pairs in S. x A,, which enough information to produce an estimate of (ss,, 0s) for all (s,, a,) and, interestingly, an estimate of Q^ (s, a) for every (s, a). despite having visited only a small fraction (6/216) of the possible state-action pairs. This allows the main Q-learning agent to make use upper bound information at every state-action pair via the projection step (12). The main intuition is that these upper bound values are likely to be more sensible than randomly initialized value, and therefore, can aid learning.
The above example is certainly contrived, but hopefully illustrates the benefits of decomposition and subsequent projection. We note that, especially in settings where the limiting factor is the ability to collect enough experience, one can trade-off extra computation to derive these bounds and improve RL performance without the need to collect additional experience. The full pseudo-code of the WCQL algorithm is available in Appendix B.
4.3 Convergence Analysis
In this section, we show that WCQL converges Q* with probability one. First, we state a standard assumption on learning rates and state visitation.
Assumption 2. We assume the following: (i) E On an a) x. En ( < oc for all (s, a) E S x A: (ii) analogous conditions to (i) hold for (3n a;)), n and {nH [w]] and (iii) the behavioral policy is such that all state-action pairs (s, a) are visited infinitely often w.p.1.
Theorem 1. Under Assumptions and 2, the following statements hold with probability one.
(i) For each i and X E A, lim ai (st, a.) = (5 az) for all (s,,a,) E S x A.
(ii) For each X E A, limn--oo (8 a) 2 Q" a) for all (8, ESXA.
(iii) lim (n(s, = (s, for all (s, a) ESXA
Theorem I ensures that each subagent's value functions converge to the subproblem optimal value. Furthermore, it shows that asymptotically, the Lagrangian action-value function given by (9) will be an upper bound on the optimal action-vai value function Q' of the full problem and that our algorithm will converge to Q"
5 Weakly Coupled DQN
In this section, we propose our main algorithm weakly coupled DQN (WCDQN), which integrates the main idea of WCQL into function approximation setting. WCDQN guides DQN using Lagrangian relaxation bounds, implemented using a constrained optimization approach.
Networks. Analogous to WCQL, WCDQN has main network Q'(s,, a; 0) that learns the action value of the full problem. In addition to the main network. WCDQN uses a subagent network Q7(s a; 0v)) network to learn the subproblem action-value functions Q As in standard DQN, we also have 0- and 07. which are versions of 0 and Or frozen from a previous iteration and used for computing target values [43]. The inputs to this network are (i, X, 8;, 0;), meaning that we can use a single network to learn the action-value value function for all subproblems and À e A simultancously. The
7

---

Lagrangian upper bound and the best upper bound estimates are:
N
(s AT + Σ a and Q" (s, (8,0;0)) min a;) (13)
XEA
Loss functions. Before diving into the training process, we describe the loss functions used to train each network, they instructive toward understanding the main idea behind WCDQN (and how it differs from standard DQN). Consider a behavioral distribution for state-action pairs and a distribution ye over the multipliers A.
by (0v) )-
E Ex Exsamp.amp
E (2/² (x))
(14)
where the (ideal) target value is
x (=((),))s) Aa, + + [ Q7 00)].
(15)
For the main agent, we propose loss functiin that adds soft penalty for violating the upper bound:
[v Q=,, 0))² + ku (Q' a: 0) - yu w
I(0) = Ex EgaarpArpl
(16)
where (+)+ = max(:; 0), kir is a coefficient for the soft penalty, and y = r(s, a) + 1 (aaxx'EA(+)) Q' a'; yu r(s a) 7B maxa'ed Q* as', al; 07)
(17)
(18)
The penalty encourages the network to satisfy the bounds obtained from the Lagrangian relaxation.
Training process. The training process resembles DQN, with few modifications. At any iteration, we first take an action using an e-greedy policy using the main network over the feasible actions, store the obtained transition experience T in the buffer, and update the estimate of Bww) following (8).2 Each network is then updated by taking a stochastic gradient descent step on its associated loss function, where the expectations are approximated by sampling minibatches of experience tuples and X. The penalty coefficient Ky can either held constant to a positive value or annealed using a schedule throughout the training. The full details are shown in Algorithm I and some further details are given in Appendix C.
Numerical Experiments
In this section, we evaluate our algorithms on three different WCMDPs. First, we evaluate WCQL on an electric vehicle (EV) deadline scheduling problem with multiple charging spots and compare its performance with several other tabular algorithms: Q-learning (QL), Double Q-learning (Double-QL) [22], speedy Q-learning (SQL) [4], bias-corrected Q-learning (BCQL) [40], and Lagrange policy Q- learning (Lagrangian QL) [34]. We then evaluate WCDQN on two problems, multi-product inventory control and online stochastic ad matching, and compare against standard DQN, Double-DQW and the caimmallty-tghheeninn DQN (OTDQN) algorithm² of He al. [25] as baselines. Further details on environment and algorithmic parameters are in Appendix D.
EV charging deadline scheduling [63]. In this problem, decision maker is responsible for charging electric vehicles (EV) at a charging service center that consists of N = 3 charging spots. An EV enters the system when charging spot available and announces the amount of electricity it needs be charged, denoted B,, along with the time that it will leave the system, denoted D,. The decision maker also faces exogenous, random Markovian processing costs c. At each period, the action is to decide which EVs to charge in accordance with the period's capacity constraint. For each unit of power pro- vided to an EV, the service center receives a reward C. However, if the EV leaves the system with an unfulfilled charge, a penalty is assessed. The goal is to maximize the revenue minus penalty costs.
tabular representation for B(w) since example applications do necessarily have large exogenous space W. When required, WCDQN can extended use function approximation (i.e., neural networks) to learn B (wr
e Herre
We include OTDQN baseline because it also makes use of constrained optimization during training.

---

Algorithm 1 Weekly Coupled DQN
1: Input: Lagrange multiplier set A and a distribution over A, penalty coefficient kv, initialized
replay buffer D, target network update frequency Curget. initial state distribution So-
2: Initialize main Q-network 2'(,-;0) and subagent network +.:
3: Initialize target network weights 0- 0 and Og Ov.
4: for 7 = 0, 1, 2.... do
5: Take an e-greedy behavioral action a, with respect to the main network (s a;
6: Store the observed transition Tn into the replay buffer D.
7: // Update subagents and combine results to estimate upper bound
8: Sample a minibatch of transitions T from D> along with sample of À from
9:
for = 1.2..... N do Compute targets y using (15) and take an optimization step on subagent loss (14). end for
10:
11:
12:
Update right-hand-side estimate B (w.) according to (8).
13:
Using (13), combine subproblems to obtain Lagrangian upper bound Q (8, 0
14:
// Main agent update with upper bound penalty loss
15:
Compute y and yo using (17) and (18), then take an optimization step the main loss (16).
16:
Update 0 = and fT = Oy every Cuareet steps.
17:
end for
Multi-produs inventory control with an exogenous production rate [27]. Consider the problem of resource allocation for a facility that manufactures N 10 products. Each product has an independent exogenous demand given by D,, i 1, ................................ N.. To meet these demands, the products are made to stock. Limited storage R, is available for each product, and holding a unit of inventory per period incurs cost h,. Unmet demand is backordered less than the maximum number of allowable backorders M, Otherwise, it is lost with a penalty cost 4, The DM needs to allocate resource level a, E {0, 1, ... U} for product i from shared finite resource quantity U in response to changes in the stock level of each product, denoted by the number of
cost b; if the number of backorders
I; E X, (MM, M, + ,,...,R,J. A negative stock level corresponds backorders. Allocating a resource level a; yields a production rate given by a function pi pa) where p: an exogenous Markovian noise that affects the production rate. The goal is to minimize the total cost, which consists of holding, back-ordering, and lost sales costs.
Online stochastic ad matching [18]. We study the problem of matching N 6 advertisers to arriving impressions. In each period, an impression of type e; arrives according to a Markov chain. An action ar,; {0, 1} assigns impression e; to advertiser with constraint that exactly one advertiser selected: ΣNV ar,: = 1. Advertiser states represent the number of remaining ads to display and evolves according to Sc-1.1 St, a,,s. The objective is to maximize the discounted sum of expected rewards for all advertisers.
In Figure 2, we show how WCQL's projection method helps it learn a more accurate Q function more quickly than competing tabular methods. The first panel, Figure 2A, shows an example evolution of WCQL's projected value function Q', along with the evolution of the upper bound. We compare this the evolution of the action-valus value function in absence of the projection step. In the second panel, Figure 2B, we plot the relative error between the learned value functions of various algorithms compared to the optimal value function. Both plots are from the EV charging example. Detailed descriptions of the results are given in the figure's is caption.
The results of our numerical experiments are shown in Figure 3. We see that in both the tabular and the function approximation cases, our algorithms outperformed the basclines, with WCQL and WCDQN achieving the best mean episode total rewards amongst all problems. From Figure 3A, we see that although the difference between WCQL and Lagrangian QL is small towards the end of the training process, there are stark differences earlier on. In particular, the performance curve of WCQL shows significantly lower variance, suggesting more robustness across random seeds. Given that WCQL and Lagrangian QL differ only the projection step, we can attribute the improved stability to the guidance provided by the Lagrangian bounds. Figure 3B shows that for the multi-pre multi-product inventory problem, the OTDQN, DQN, and Double DQN baselines show extremely noisy performance compared to WCDQN, whose significantly better and stable performance is likely

---

QL
20
Douale-OL SQL
BOOL
WCOL
Q-allee
Reaative
1.2
0 [s.
Q OUls
-5
[s.a]
-10
10
10
10"
Sleps
Episodes (x200)
(A) WCQL learning process illustration
(B) Relative error comparison
Figure 2: Behavior of WCQL's learning process compared to other tabular methods. Figure 2A, we show an example of the evolution of quantities associated with WCQL for randomly selected state-action pair in the EV charging problem: upper bound (blue). WCQL Q-value (orange line with 'x' marks indicating the points projected by the bound), standard Q-learning (green) and the optimal action-value (red). Note that sometimes the orange line appears above the blue since WCQL's projection step is asynchronous, i.e., the projections are made only if the state is visited by the behavioral policy. Notice at the last marker, the bound moved the Q-value in orange to "good" value, relatively nearby the optimal value. WCQL's Q-value then evolves on its own and eventually converges. On the other hand, standard QL (green), which follows the same hchavior policy WCQL, still far from optimal. In Figure 2B, show the relative error, defined as |V, V [|2/|| [12, where V, and V are the state value functions derived from Q-iterate on iteration and Q", respectively. WCQL exhibits the steepest decline in relative error compared to the other algorithms. Note that since Lagrangian QL acts based on the Q-values of the subproblems, there is no Q-value for this algorithm which to compute relative error.
due to the use of faster converging subagents and better use the collected experience. Similarly, in the online stochastic ad matching problem, WCDQN significantly outperforms all the baselines.
-000
7.5
-600
Rewwers
Tosal Roward
6.0
SQL
BOCL
-1000
Doubi e DGN GTOON
Double DON OTDCN
DON
5.5
Lagmingian Ot WCOL
-1400
-1200
WCDON
WC2ON
20
(x100)
(X100)
(C100)
(A) EV charging
(B) Multi-produuct inventory control
(C) Online ad matching
Figure 3: Benchmarking results for the WCQL (EV charging) WCDQN (multi product inventory control, online ad matching) against baseline methods. The plots show mean total rewards and their 95% confidence intervals across 5 independent replications.
7 Conclusion
In this study, we propose the WCQL algorithm for learning in weakly coupled MDPs and we show that our algorithm converges to the optimal action-value function. We then propose WCDQN, which extends the idea behind the WCQL algorithm to the function approximation case. Our algorithms are model-free free and learn upper bounds the optimal action-value using a combination of Lagrangian relaxation and Q-learning. These bounds are then used within a constrained optimization approach to improve performance and make learning more efficient. Our approaches significantly outperforms competing approaches several benchmark environments.
10

---

Acknowledgments and Disclosure of Funding
This research was supported in part by the University of Pittsburgh Center for Research Computing. RRID:SCR 00233,,, through the resources provided. Specifically, this work used the H2P cluster, which is supported by NSF award number OAC-2117681.
References
[1] Daniel Adelman and Adam J Mersereau. Relaxations of weakly coupled stochastic dynamic programs. Operations Research, 56(3):712-727, 2008.
[2] Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
[3] Konstantin Avrachenkov and Vivek S Borkar. Whittle index based Q-learning for restless bandits with average reward. Automatica, 139:110188 2022.
[4] M. G. Azar, R. Munos, M. Ghavamzadaeh, and H. J. Kappen. Speedy Q-leaming. In Advances in Newral Information Processing Systems 24, 2011.
[5] Marc G Bellemare, Will Dabney, and Mark Rowland. Distributional reinforcement learning. MIT Press, 2023.
[6] D. P. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programiing volume 5. Athena Scientific Belmont, MA, 1996.
[7] Dimitris Bertsimas and Adam J Mersereau. A learning approach for interactive marketing to a customer segment. Operations Research, 55(6):1 120-112011131 133,, 2007.
[8] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint 1906:0000..1170 2019.
[9] Craig Boutilier and Tyler Lu. Budget allocation using weakly coupled, constrained Markov decision processes. 2016.
[10] Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artificial Intelligence. 121(1-2)499-077. 2000.
[11] David B Brown and Jingwei Zhang. On the strength of relaxations of weakly coupled stochastic dynamic programs. Operations Research. 2022.
[12] David B Brown, James E Smith, and Peng Sun. Information relaxations and duality in stochastic dynamic programs. Operations Research. 58(4 ():7att-))77-888000 2010.
[13] Hyeong Soo Chang, Pedram Jaefari Fard, Steven I Mareus, and Mark Shayman. Multitime scale Markov decision processes. JEEE Transactions on Automatic Control, 48(6))976 987, 2003.
[14] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1675-1674. PMLR, 2019.
[15] Gabriel Dulac-Amold, Nir Levine, Daniel J Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning, 1 1100))22499224) 2468, 2021.
[16] Ibrahim Shar and Daniel Jiang. Gookahead-bounder Q-learning. International Conference on Machine Learning, pages 6665-86775 PMLR, 2020.
[17] Eyal Even-Dar, Yishay Mansour, and Peter Bartlett. Learning rates for Q-learning. Journal of Machine Learning Research, 5(1), 2003.
[18] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan. Online stochastic matching: Beating 1-1/e, In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117-126. IEEE, 2009.

---

[19] Jing Fu. Yoni Nazarathy, Sarat Moka, and Peter G Taylor. Towards Q-leaming the Whittle index for restless bandits. In 2019 Australian & New Zealand Control Conference (ANZCC), pages 249-254. IEFE, 2019.
[20] Kevin D Glazebrook, Diego Ruiz-Hernande and Christopher Kirkbride. Some indexable familiie of restless bandit problems. Advances Applied Probability, 38(3):643-61) 672, 2006.
[21] Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual Markov decision processes. arXiv preprint arXiv:1502.022555 2015.
[22] Hado Hasselt. Double Q-learning, Advances in Neural Information Processing Systems, 23, 2010.
[23] Milos Hauskrecht, Nicolas Meuleau, Leslie Pack Kaelbling, Thomas Dean, and Craig Boutilier. Hierarchical solution of Markov decision processes using maero-actions. In Uncertainty in Artificial Intelligence, pages 220-229, 1998.
[24] Jeffrey Thomas Hawkins. A optimization problems and its applications. PhD thesis, Massachusetts Institute of Technology. 2003.
Langrangian decomposition approach to weakly coupled dynamic
[25] Frank He, Yang Liu, Alexander G Schwing, and Jian Peng. Learning to play in a day: Faster deep reinforcement learning by optimality tightening. arXiv preprint arXiv: /6/ 1.0 1.01606, 2016.
[26] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improve- ments in deep reinforcement learning. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
[27] David J Hodge and Kevin Glazebrook. Dynamic resource allocation multi-product make-to-stock production system. Queueing Systems, 67(4):333-364, 2011.
[28] Yu-Pin Hsu. Age of information: Whittle index for scheduling stochastic arrivals. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 2634-2638. IEEE, 2018
[29] Weici Hu and Peter Frazier. An asymptotically optimal index policy for finite-horizon restless bandits. arXiv preprint arXiv: arXiv: 1007.00005.505 2017.
[30] T. Jaakkola, M. I. Jordan, and S. P. Singh. Convergence of stochastic iterative dynamic programming algorithms. In Advances in Neural Information Processing Systems, pages 703-710, 1994.
[31] Daniel R Jiang and Warren B Powell. An approximate dynamic programming algorithm for monotone value functions. Operations Reseurch, 6386)1188- 2015.
[32] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[33] Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored MDPs. In IJCAI, volume 16, pages 740-747, 1999.
[34] Jackson A Killian, Arpita Biswas, Sanket Shah, and Milind Tambe. Q-learning Lagrange policies for multi-action restless bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 871 881- 2021.
[35] Jackson A Killian, Lily Xu, Arpita Biswas, and Milind Tambe. Robust restless bandits: Tackling interval uncertainty with deep reinforcement learning. arXiv preprint arXiv:2107.01689 2021.
[36] Diederík P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[37] Sumit Kunnumkal and Huseyin Topaloglu. Using stochastic approximation methods to compute optimal base-stock levels in inventory control problems. Operations Research, 5663):646-664, 2008.
12

---

[38] Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
[39] Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RL for latent MDPs: Regret guarantees and lower bound. Advances in Neural Information Processing Systems, 34:24523-24534, 2021.
[40] D. Lee and W. B. Powell. Bias-corrected Q-learning with multistate extension. IEEE Transac- tions on Automatic Control, 2019.
[41] Keqin Liu and Qing Zhao. Indexability of restless bandit problems and optimality of Whittle index for dynamic multichannel access. IEEE Transactions on Information Theory, 56(11): 5547-5567, 2010.
[42] Rahul Meshram, D Manjunath, and Aditya Gopalan. On the Whittle index for restless multi- armed hidden Markov bandits. IEEE Transactions on Automatic Control, 63(9):3046-3053 2018.
[43] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1/Xiv:13/2.5602 2013.
[44] Aditya Mohan, Amy Zhang, and Marius Lindauer. Structure in reinforcement learning: A survey and open problems. arXiv preprint arXiv:2306.66021, 2023.
[45] Selvaprabu Nadarajah and Andre Augusto Cire. Self-adapting network relaxations for weakly coupled Markov decision processes. Available at SSRN, 2021.
[46] Khaled Nakhleh, Santosh Ganji, Ping- Mhn- Hsieh, I Hou, Srinivas Shakkottai, et al. Neurwin: Neural Whittle index network for restless bandits via deep RL. Advances in Neural Information Processing Systems, 34:828-888 839, 2021.
[47] Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored MDPs. Advances in Neurul Information Processing Systems, 27, 2014.
[48] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. Advances in Neural Information Processing Systems, 29, 2016.
[49] Warren Powell, Andrzej Ruszczyúski, and Huseyin Topaloglu. Learning algorithms for separable approximations discrete stochastic optimization problems. Mathematics of Operations Research, 29(4): 841-83,, 2004.
[50] Francisco Robledo, Vivek Borkar, Urtzi Ayesta, and Konstantin Avrachenkov. QWI: Q-learning with whittle index. ACM SIGMETRICS Performance Evaluation Review, 49(2):47-50, 2022.
[51] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprini arXiv: 15l:.0159..55 2015.
[52] Lauren N Steimle, David L Kaufman, and Brian T Denton. Multi-model Markov decision processes, IISE Transactions, 53(10):1124-1139 2021.
[53] Kalyan Talluri and Garrett Van Ryzin. An analysis of bid-price controls for network revenue management. Management Science,
1998.
[54] Huseyin Topaloglu. Using Lagrangian relaxation compute depeedeet bid prices in network revenue management. Operations Research, 57(3):637-649, 2009.
[55] J. N. Tsitsiklis. Asynchronous stochastic approximation and Q-learning. Machine Learning, 16 (3):185-2000 1994.
[56] Tom Van de Wiele, David Warde-Farley, Andriy Mnih, and Volodymyr Mnih. Q-learning in enor- mous action spaces via amortized approximate maximization. arXiv preprint arXiv:2001.88/ 16, 2020.
[57] Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q-learning In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
13

---

[58] Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International Conference on Machine Learning, pages 1995-2003. PMLR, 2016.
[59] C. J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, King's College, Cambridge, UK, 1989.
[60] Richard R Weber and Gideon Weiss. On an index policy for restless bandits. Journal of Applied Probability, 27(())637-643)) 1990.
[61] Peter Whittle. Restless bandits: Activity allocation in changing world. Journal of Applied Probability, 25(A))287-298, 1988.
[62] Guojun Xiong, Shufan Wang, and Jian Li. Learning anfinit-hhorizor average-reward restless multi-action bandits via index awareness. Advances Neural Information Processing Systems, 35:17911-1783 2022.
[63] Zhe Yu, Yunjian Xu, and Lang Tong. Deadline scheduling as restless bandits. IEEE Transactions on Automatic Control, 63(8):2343-2353 2018.
[64] Xiangyu Zhang and Peter Frazier. Near-optimality for Chriie--horizon restless bandits with many arms. arXiv preprint arXiv:2203. 15853, 2022.
[65] Jiahong Zhou, Shunhui Mao, Guoliang Yang, Bo Tang, Qianlong Xie, Lebin Lin, Xingxing Wang, and Dong Wang. RL-MPCA: A reinforcement learning based multi-phase computation allocation approach for recommender systems. Proceedings of the ACM Web Conference 2023, pages 3214 3224,, 2023.
14

---

Appendix to Weakly Coupled Deep Q-Networks
A Proofs
A.1 Proof of Proposition
Proof. We prove part the first part of the proposition (weak duality) by induction. First, define
Co(s, a) = r(s, a) and a)) = -r(s, a) + +AT [(() - Ei= d(st, ai)
and suppose we run value iteration for both systems:
(s,) = r(s, a) + [[aamaa Qi a')];
(+1(8,a) r(s, a) + TT [((w) -E d(ss, ai) + + a'))
is well-known that, by the value iteration algorithm's convergence,
Q' a) = lim (7 a) and Q^(s. = lim (3, -0o
too
Consider a state s and feasible action a E A(s). We have,
Cd a) r(s, a) AT ((w) Ei d(si; a:) 2 r(), a)(
Suppose (s, a) 2 Q7 a) holds for all 8 E S and a E A(s) for some / > 0 (induction
hypothesis). Then,
(1+1(8,0) = r(),a) + k b(w) - Em= d(s;, a1) + Bmmmaaa'' (2 a')]
2 r(s + XT b(() - Emm d(s;, ai)
+ + + mma (s's', a')]
r (8) + 7 E [maxa'e_(o') (z' a')] = (8)1
Thus, it follows that (* a) 2 as)
For the proof of the second part of the proposition, define
Bo(w)= b(w) and Bu+1(w)= = b(w) + E Bc(w')]
We use an induction proof. We have for all (8, E x A.
(d(s.a)= r(s, r(s.a))=((s.)+>)))))) T b(w) - Σ d(s
N Σ [ra(st,a) a;) X (ds(s + +Abb(w)=
Σ Cd a:) + Bo(w),
where Qb, a.) = ri(s a;) - ATdss,, a.). Similarly, for all (8. ESXA.
= (((s,a)=((3.)
+ T b(w) Σ d(s ai) + +7 "'E[max''ea en Qá(s''a')
N
ri(ss, ar) ATd(s; an) + +Tb((w) +
Σ (t. +
max a'EAÀ
(ri(s,, az) ATd(s; ar) + E ld. dd]] + AT
(T((()) ((w) + E ( ((o('')))
(8, a:) + (w).
15

---

Continuing in this manner, we arrive at a) - 02 + (T). Finally, we have
()(8,a) = lim (s)
14000
N
lim
+ (b)) {
Σ (st, B())),
1=1
which follows by the convergence of value iteration.
A.2 Proof of Theorem
Proof. First, we define the Bellman operator H::
(HQ') a) r(s, a) yI [maxa' Q'(s', aa)];
which is known be y-contraction mapping. Next we define the random noise term
(s a) y max, 2 (s', a') BB max. (', a')] Analogously, for subproblem E (I, Nj. define the subproblem Bellman operator (H.Q)) a:) (s;; a.) XTd(s; 04) + +B [max;; (5(,
(19)
and random noise term
(i,((i;, a,) maxa; (5,, yI [max
(20)
The update rules of WCQL can then be written as
Quti(s, a) = (1 a, (s, Q2 a) + (s, [(H))) a) + Ent1(8,
Q a;) = (s, a,) (n ai)
+ (s;
(21)
min AT AT (w) + Σ (s,,
AEA
i=1
Qa41(8,a) = minnQnn..) (s, a), Qh+ (s,
(22)
Parts (i) and (ii). By the iteration described in (21), we know that for fixed X, are running Q-learning on an auxiliary MDP with Bellman operator H4, which encodes reward ri(s;, a.) As, a;) and the transition dynamics for subproblem i. By the standard result for asymptotic convergence of Q-learning [6], we have
lim Ci a;) Q (81, 0z). 100
(23)
We now prove the result in (ii): lim ( a) 2 Q" a). Recall that
(.(s, (B)(w)) Σ
1=1
By standard stochastic approximation theory, lim, Bn(w) (ww) for all [38]. Combining this with (23), have 1im,- () a) (* a) for all (s, a), and conclude that this limit an upper bound on Q* (s, we apply Proposition 1.
Part (iii). Assume without loss of generality that (*, a) 0 for all state-action pairs a). This can be established by shifting the origin of the coordinate system. We also assume that a, (8, a) < 1 for all (s, a) and We proceed via induction. Note that the iterates Q' a) are bounded in the sense that there exists a constant Du = Rmax/(1 -7), Ruax = max(s.a) |r(s, a)), such that IQ', (s, a)) S Do for all (s, a) and iterations [17]. Define the sequence Dx+11 (r <) De. such that 7 + < and > 0. Clearly, D2 -> 0. Suppose that there exists random variable representing an iteration threshold such that for all as,
-Dx S as min Q (s, Vn ni.
16

---

We will show that there exists some iteration 7+++1 such that
-Dx+1 S (n a) I min(D Q (s.a)) A ( nk+1. which implies that (s, a) converges to Q* a) for all (s,a). By part (ii), we know that for all 1j > 0, with probability there exists some finite iteration no such that for all n 2 no.
(s, 1 S 0 (s.
(24)
Now, we define an accumulated noise process started at ny by Wn.. (8, a) = 0, and
Wn+1. (s, a) = (1 - (s, a)) W.. (s, (s, a) + an a) En+1(s, a), V n 2 ni. where (s, a) is defined in (19). Let Fn be the entire history of the algorithm up the point where the step sizes at iteration are selected. Using Corollary 4.1 in [6] which states that under Assumption 2 on the step size (s, a), and if E. (8, a) Fi = and E[g, (s. where the random variable A, is bounded with prohability 1, the sequence W W,+1., (8, a) defined in (25) converges to zero, with probability 1. From our definition of the stochastic approximation noise (s, a)) in (19), we have
(25)
S An
(s, a) Fxl 0 0 and ES a) Frl S C(1 + max. ('' aa)).
where C' is constant. Then, it follows that
lim W (s,a)) = v (s, a), Tkk
We the following lemma from [6] to bound the accumulated noise.
Lemma A.1 (Lemma 4.2 in [6]) For every > 0, with probability one, there exists some n' such that [W W a)l S 6, for all n 2 n'.
Now, by Lemma A.1, let ni max(nu, no) such that, for all n 2 ne have [W WWnn (8, a)l yeDx < <De..
Let U 2 ny such that, for all n 2 uk. by (24) we have
>cDx DD I Q (s.
Define another sequence Yn that starts at iteration 1/-
Yr, a) D2 and Yx+1(8,a) a) = (1 an a)) (s a) + a)) Dr Note that it easy to show that the sequence (,, a) in (26) is decreasing, bounded below by yDv. and converges to Dx as co. Now we state the following lemma.
(26)
Lemma A.2. For all state-action pairs (s, a) and iterations n. 2 Vk, it holds that:
Yn (8, a) + W (n,e2
(8, a) < (s, a) S min(Q, (8, a), (, a) + W we (8, a)).
(27)
Proof. We focus on the right hand side inequality, the left hand side can be proved similarly. For the base case = Vk, the statement holds because Yu, (s, a) D& and W (8, = O. We assume true for n and show that it continues to hold for n + 1:
Qu+i (s, a) (1 a, (s, a) a)) (s, a) a, a) [(HQ)) a) (s,
< (1 am a)) m (8, a), (8, a) + (n,, a))
+ ta, a) (HQ' (s, a) + an a) (nt1(s,
$ <1 - (s, (), a) W n. (s, a)) + am (n a) Dr + a an a) E0+1 a)
< (8,)) + Wa+1, (s,
where we used (HQ,) 5 <1 _ DD Now, we have (8, a) min( (8, (n)
< min Q2 as, (n, + W Wnt1.. a)).
The inequality holds because
(s a) < Yn41 a) Wnt1,,, (s,
which completes the proof.
17

---

Since (s) - yD and W Wn,rr (s, (s,a) - 0, we have
sum 1/ S DD < Dx+1.
Therefore, there exists some time Rx+1 such that
-D++1 S (s a) min QN (s, (s, nk+1.
which completes the induction.
B Weakly Coupled Q-learning Algorithm Description
Algorithm 2 Weekly Coupled Q-learning
1: Input: Lagrange multiplier set A, initial state distribution Sg.
2: Initialize Q-table estimates Qo. (Qo,)) Set Q6 Qo-
3: for n = 0, 1, do
4: Take 6-greedy behavioral action a, with respect to Q (sn, a).
5: // Estimate upper bound by combining subagents
6: for i = 1, .,, do
7:
Update each subproblem value functions Qi according to (7).
8:
end for
9:
Update right- right-hand-side estimate Bu+1 (w+1(w,, according to (8).
10:
Using (9) and (10), combine subproblems to obtain 2 a) for all a e A(sn).
Main agent standard update, followed by projection
12: Do standard Q-learning update using (11) to obtain Qn+1-
13: Perform upper bound projection step: (s Qt a) Qu+1(s,a)
end for
C Weakly Coupled DQN Algorithm Implementation
In our implementation of WCDQN, the subproblem Q; -nttwork in Algorithm follows the standard network architecture as in [43]. where given an input state 8; the network predicts the Q-values for all actions. This mandates that all the subproblems have the same number of actions. To address different subproblem action spaces, we can change the network architecture receive the state-action pair (ss, a;) input and output the predicted Q-value. This simple change does not interfere affect WCDQN's main idea.
Our code is available at
com www.raaiimnlssarr/ooooeeeeeeee
D Numerical Experiment Details
A discount factor of 0.9 is used for the EV charging problem and 0.99 for the multi-produet inventory and online stochastic ad matching problems. In the tabular setting, that depends on the ptae-acciion pairs visitation given by an (s. a) = 1//,, (s, a)", " where 1/2 (s, a) represent the number of times (s, a) has been visited up to iteration n, and r 0.4. We also use an e-greedy exploration policy, given by e(s) 1/r(s)", where v(s) is the number of times the state & has been visited. We set policy that decays from 1 to 0.05 after 30, 000 steps. All state-action value functions are initialized randomly. Experiments were ran on a shared memory cluster with dual 12-core Skylake CPU (Intel Xeon Gold 6126 2.60 GHz) and 192 GB RAM/node.
polynomial learning rate
0.4. In the function approximation setting, we use an e-greedy
D.1 EV charging deadline scheduling [63]
In this problem, there are in total three charging spots = 3. Each spot represents subproblem with state (ce, Br Dr,), where G {0.2, 0.5, 0.8) is the exogenous electric cost, Br,s 2 is the
18

---

amount of charge required and Di,; S 4 is the remaining time until the EV leaves the system. The state space size 36 for each subproblem. At given period t. the action of each subproblem is whether to charge an EV occupying the charging spot dt,i or not dz 0. A feasible action given by Σi= dt, S b(c)), where 6(0.2) 3, b(0.5) 2, and b(0.8) The reward of each subproblem is given by
(1 - a.). if Br, > D, > 1, a)a -.00.-F(BBB3 -1,1) o1 if B 0, D1. =
Ti((et, Brii Dr,i), ar,)) =
0, otherwise,
where F dr,s) ) 0.2 -B,;) is a penalty function for failing to complete charging the EV before the deadline. The endogenous state of each subproblem evolves such that (Bt+ D++1,)) (Bu,: - atii Dr.; 1) if Dr.; > 1, and (Bt+.. Di+1,;) = (B, D) with probability q B) De,; S 1, where (0.0) = 0.3 and qBB, D) 0.7/11 for all B and D 0. The exogenous
state et evolves following the transition probabilities given by:
70.4
0.3
0.3
(C++1 | =
0.2
0.5
0.3
0.6
0.2
0.2
D.2 Multi-product inventory control with exogenous production rate [27]
We consider manufacturing N = 10 products. The exogenous demand Dr, for each product i (1,2...., 10} follows Poisson distribution with mean value 14: The maximum storage capacity and the maximum number of allowable backorders (after which lost sales costs incur) for product are given by R, and M,, respectively.
The state for subproblem given by (fr,. Pt). where Tr,i E (-M, + R& is the inventory level for product i, and Pt is exogenous and Markovian noise with support [0.8, 1]. A negative stock level corresponds to the number of backorders. For subproblem i, the action or is the number resources allocated the product The maximum number of resources available for all products is = 3, so feasible actions must satisfy >, ar, 3.
Allocating resource level a,,i yields production rate (s(,,,s;)) The cost function for product is ca ca Dt.5, Or.;) and represents the sum of the holding, backorders, and lost sales costs. We let h; b;, and I, denote the per-unit holding, backorder, and lost sale costs, respectively. The cost function Cx Pt, at,s) is given by,
(12 pt at.)) (5.9)71555911111 + at,;).
ci(Te Pt, (r,5) h4( + pi(ar,, Pt))+ bi(- bil-01,i- (i P.))+ + 4((D,,; - It.i pe(at,i, Pc))+ M,)+,
where (.)+ max(-. 0). We summarize the cost parameters and the mean demand for each product in Table 1. Finally, the transition for the inventory state of subproblem is given by
It-1, 1, max(min(xre, + (i Pt) Dr,i, R.).-M.).
where the exogenous noise evolves according to a transition matrix sampled from a Dirichlet distri- bution whose parameters are each sampled (once per replication) from Uniform(1, 5) distribution.
Table Multi colli-proodutt inventory environment parameters
Product
2
9
Storage capacity R,
20
30
10
15
10
10
25
30
15
Maximum backorders M;
5
5
5
5
Mean demand
0.3
0.7
0.5
1.0
1.4
0.9
1.1
1.2
0.3
0.6
Holding cost h;
0.1
0.2
0.05
0.3
0.2
0.5
0.3
0.4
0.15
0.12
Backorder cost
3.0
1.2
5.15
1.3
1.1
1.1
10.3
1.05
3.1
Lost sales cost
3.3
10.05
3.9
3.7
3.6
40.3
12.55
44.1
19

---

D.3 Online stochastic ad matching [18]
In this problem, platform needs match N advertisers to arriving impressions [18]. impression E E = 21. .5) arrives according to discrete time Markov chain with transition probabilities given by g(et+1 et), where each row of the transition matrix q is sampled from Dirichlet distribution whose parameters are sampled (once per replication) from Uniform(1, 20).
The action 04, {0,1) 1) is whether to assign impression 6t advertiser i or not. The platform can assign an impression to at most one advertiser: Σi=1 04,1 =.
The state of advertiser Zi, gives the number of remaining ads to display and evolves according to 1,+ It,i 0t,5- The initial state Zi = (10, 11, 12, 10, 14, 9). The reward obtained from advertiser in state št,i (Zz,i, Cx) is ra(St. 04,s) = li.,, min( (r,s), where the parameters 4,,s are sampled (once per replication) from Uniform (1, 4).
D.4 Training parameters
Each method was trained for 6,000 episodes for the EV charging problem, 5,000 for the multi multi-prooduct inventory control problem, and 10,000 episodes for the online stochastic ad matching problem. The episode lengths for the EV charging, online ad stochastic ad matching, and multi multi-produuct inventory control problems are 50, 30, and 25, respectively. We performed independent replications.
We use a neural network architecture that consists of two hidden layers, with 64 and 32 hidden units respectively, for all algorithms. A rectified linear unit (ReLU) is used as the activation function for each hidden layer. The Adam optimizer [36] with a learning rate of 1.0 x 10-4 was used. For OTDQN, we use the same parameter settings in He et al. [25].
For WCDQN, we use a Lagrangian multiplier À E [o, 10], with 0.01 discretization. We also used an experience buffer of size 100,000 and initialized it with 10,000 experience tuples that were obtained using a random policy. For the WCDQN algorithm, we set the penalty coefficient ky to 10, after performing small amount of manual hyperparameter tuning the set 21,2, 4, 10).
D.5 Sensitivity analysis of WCQL with respect to the number of subproblems
We study the performance improvement from WCQL over vanilla Q-learning as number of subproblems increases for the EV charging problem. We only vary the number of subproblems (from 2 to 5) and keep all other settings as defined in Appendix D. The results, given in Table 2, show that the benefits of WCQL become larger the number of subproblems increases. This provides some additional evidence for the practicality of our approach, especially in regimes where standard methods fail.
Table 2: Cumulative reward and percent improvement WCQL over QL on the EV-charging problem with a
different number of subproblems.
Number of Subproblems
Algorithm
2
3
4
5
QL
5.39
6.7
5.2
3.26
WCQL
5.35
7.14
6.28
4.66
Percent improvement
-0.7%
6.6%
20.8%
42.9%
E Limitations and Future Work
One interesting direction to explore for future work is to address the limitation of learning the Lagrangian upper bound using fixed and finite set A. Instead, one can imagine the ability to learn the optimal value of À and concentrate the computational effort towards learning the Lagrangian upper bound for this particular X, which could potentially lead to tighter bounds. possible approach is to apply subgradient descent on X, similar to what is done in Hawkins [24].
20


Reviews:
[{"review_id": "OD9ZHBrp4E", "reviewer": "Reviewer_aL5V", "summary": "This paper introduces novel Q-learning based approaches (WCQL and WCDQN) to solving weakly-coupled Markov decision processes. The approaches work by running Q-learning for the sub-problems of the WCMDP to construct an upper bound on the optimal Q-values of the overall problem. The WCMDP constraint is incorporated into the reward structure of the task via approximate Lagrangian relaxation. In the function approximation case, the constraint is enforced as a penalty to the loss. A theoretical analysis is performed for the tabular case and experiments are run to demonstrate the performance of both the tabular and DQN-based approaches. ", "questions": "- Does the sub-problem action-value network parameterization mean that all of the subproblem action spaces have to have the same number of actions? \n\n- Is there some intuition as to why double Q-learning performs worse than regular Q-learning? I would think the fact that double Q-learning attempts to reduce value overestimation would have a similar effect to ensuring the overall task Q-value estimate doesn’t exceed the estimated upper bound. ", "limitations": "The authors do not appear to discuss any limitations of their method (see above). I do not directly see any negative societal implications of this work, though in practice it would depend on the problem to which it is applied and any guarantees (or lack thereof) regarding constraint violations. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is generally easy to follow and clearly written, and the problem setting is well-motivated. \n\n- The proposed approaches appear to be simple and relatively original. \n\n- If this is indeed the first model-free approach to WCMDPs, it represents a significant advance for this problem setting. ", "weaknesses": "- The core weakness of both the theoretical and empirical analyses, in my opinion, is the lack of treatment of constraint violations by WCQL and WCDQN. The theoretical analyses, as far as I can tell, assume a fixed, arbitrary Lagrange multiplier and show convergence of the Q-values to the optimal Q-values for *that choice of Lagrange multiplier*. This, however, says nothing about the resulting policy’s constraint violations. Similarly, in the experiments, there are no results showing the constraint violations of each method. Indeed, the “soft constraint” formulation seems strange for problems like the EV task, for in which in practice assigning too many cars to too few charging ports would seem to be a serious problem. I think in particular it would be helpful to add plots showing constraint violations for each method and whether they find feasible policies. \n\n- Related to the above, there’s no discussion of whether even in an idealized case where $\\lambda$ was a continuous variable the proposed approach converges to a saddle point of the Lagrangian (i.e., actually solves the “true” optimization problem), even if in practice discretization is not a significant detriment to performance. \n\n- As far as I can see, there is no discussion of the limitations of the proposed approaches. \n\n- The experimental evaluation is fairly limited.\n\n- More details on the baselines in the main text would be helpful to improve clarity. I would suggest changing the citations to a numerical format to save space. \n\nMinor: \n- The stochastic gradient update at the end of Section 3.2 would ideally reflect the update of minibatch SGD rather than pure SGD. \n\n- The $\\wedge$ symbol in Eq. 11 seems unnecessary, it would be more clear to just write $\\min(\\cdot, \\cdot)$. \n\n- From a clarity perspective, it would be helpful if the initial description of a WCMDP contained an example to anchor readers’ understanding. \n\n- Figure 3A has no y-axis label. Also, I think it would be more informative to plot the upper bound on average across $(s,a)$ pairs rather than at only one point. \n\n- It would make sense to add distributional RL [1] and Rainbow [2] to the list of extensions of DQN in the introduction or related work sections. The authors should also contrast their setting to constrained MDPs [3].\n\n\nI think this is interesting work, and I am open to increasing my score based on the degree to which the above concerns are addressed. \n\n\n[1] https://arxiv.org/abs/1707.06887\n\n[2] https://arxiv.org/abs/1710.02298\n\n[3] https://www-sop.inria.fr/members/Eitan.Altman/TEMP/h.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the originality (“proposed approaches appear to be simple and relatively original”) and the importance of our work (“the problem setting is well-motivated”, “represents a significant advance for this problem setting”). We’d appreciate it if the reviewer would consider increasing their score if the comments are satisfactory. All minor comments are noted and will be fixed.\n\n*The core weakness... in my opinion, is the lack of treatment of constraint violations ...*\n\n* Constraint violation: we believe there is a little misunderstanding here. We would like to clarify that there are two types of “constraints” used in this paper (unrelated to each other):\n  1. Action-selection constraints that are central to the original problem\n  2. Q-value constraints used by WCDQN to speed up the learning process\n* These two types of constraints are two separate notions in our paper. We assume that by “policy’s constraint violations”, the reviewer is referring to the action-selection constraints (type 1). However, note that the action selection is always feasible: please see assumption 1 (observability of b(w) once the agent lands in a state, which is enough information for the agent to compute the set of feasible actions). Therefore, the action-selection constraints are never violated. In lines 183-186 in the paper, we give further context on Assumption 1: “the agent learning on the main problem will always sample a feasible action. In each of our example applications, Assumption 1 naturally holds: e.g., in the EV charging problem, there are a limited number of available charging stations b(w).”\n* Regarding the comment “soft constraint seems strange for the EV task”, we believe this is a misunderstanding, since the use of “soft constraints” is within the WCDQN algorithm and is not related to the action-selection constraints. The main idea behind WCDQN is to learn the Lagrangian Q-value (which is an upper bound on Q*) and use this upper bound to encourage our Q-estimate to be close to Q* via soft constraints.\n\n*there’s no discussion of whether even in an idealized case where \\Lambda...*\n* Thanks for your question. We have two interpretations of your comment, depending on what you mean by “true” optimization problem. If by “true optimization problem,” you are referring to the problem of minimizing over \\lambda, then yes, in the ideal situation, we are able to solve it to optimality. This is because Q^\\lambda is a piecewise linear and convex function of \\lambda (Adelman and Mersereau, 2008) and we can in principle find its minimizer using standard convex optimization techniques, such as subgradient descent.\n* If by “true optimization problem,” you are referring to the original MDP, then we believe you are asking about the duality gap between the Lagrangian formulation vs the optimal value of the MDP. One highly relevant paper is Adelman and Mersereau (2008), which provides two results in this direction (Theorems 2 and 4). The former gives (somewhat stringent) conditions for when the Lagrangian relaxation is tight and the latter gives a bound on the duality gap for more general conditions.\n  * We will add discussions of both of these results into the paper’s appendix. Note that our approach makes use of the fact that Q^\\lambda is an upper bound of Q* to speed up the learning of Q* (by encouraging the estimate of Q to be below the estimate of the upper bound), but our approach does not critically depend on the upper bound being tight. As long as the bound is somewhat good, we expect to see empirical benefits.\n\n*there is no discussion of the limitations..*\n\n* The main limitation in our opinion is that the finite set of \\lambda values needs to be specified as input to the algorithm. In future work, we would like to explore the idea of adaptively adjusting \\lambda (perhaps using a finite-difference subgradient), which would remove the need of estimating Q^\\lambda for many \\lambdas.\n\n*experimental evaluation is fairly limited.*\n\n* We’ve completed a new experiment to study the effect of the number of subproblems; please see the **global response.**\n\n*More details on the baselines in the main text...*\n\n* Noted and will update!\n\n*subproblem action spaces have to have the same number of actions?*\n\n* To address different subproblem action spaces, we can change the network architecture to receive the state-action pair (s_i, a_i) as input and output the predicted Q-value. This simple change does not interfere or affect WCDQN's main idea. Will address in paper.\n\n*intuition as to why double Q-learning performs worse than regular Q-learning?*\n\n* Great question! Note that both double Q-learning and Q-learning are both operating directly on the joint state space, making for a difficult exploration problem. Our belief is that due to Q-learning’s larger overestimation bias, this may sometimes lead to better exploration properties (if those overestimated states happen to be of high value). See the Maximin Q-learning paper of Lan et al., 2020 for discussion of this phenomenon (https://openreview.net/pdf?id=Bkg0u3Etwr).\n\n* Intuition on how WCQL and double QL handle overestimation and why WCQL works better:\n  * For double Q-learning, the overestimation is handled on a state-by-state basis.\n  * For WCQL, suppose we have 3 subproblems, each subproblem with state space (1, 2, 3), leading to 3^3 total states. Now, even if we just visit 3 of these states (1, 1 ,1), (2, 2, 2), and (3, 3, 3), then due to the properties of the decomposition, we have information for all subproblem states of all subproblems. Hence, despite only observing 3 of 27 states, we are able to apply the upper-bound to any arbitrary state in the state space. The intuition here is that WCQL enables a sort of generalization to unseen states by leveraging weakly-coupled structure. This is the main reason for WCQL’s effectiveness. We hope that this example and discussion helps to address your question."}, {"review_id": "05h2sVUJ58", "reviewer": "Reviewer_HJ3Y", "summary": "This paper considers the problem of learning optimal policies for a weakly coupled Markov decision process (WCMDP). The paper extends the classical DQN algorithm to this setting by introducing separate lagrangian relaxations. Experiments are conducted on 3 operational research testbeds.", "questions": "N/A", "limitations": "The significance of the problem for the deep learning community. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper has a very complete structure, with a detailed problem introduction, an insightful algorithm derivation, a theoretical analysis as well as solid numerical studies. The presentation is particularly clear and easy to follow. The algorithm is intuitive and convincing. You cannot really find any flow from this paper.", "weaknesses": "My biggest concern about this work is the audience. As a practitioner in deep RL, this is literally the first time for me to hear the problem of WCMDP. Although I do appreciate that this work teaches me a lot, I don't know whether this paper can attract the attention of the deep RL community, particularly considering the test domains are pretty toy. This paper looks to me more like a work that brings deep RL techniques to the OR community rather than the reverse direction. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the strengths of our paper: “This paper has a very complete structure, with a detailed problem introduction, an insightful algorithm derivation, a theoretical analysis as well as solid numerical studies. The presentation is particularly clear and easy to follow. The algorithm is intuitive and convincing. You cannot really find any flaw from this paper.” We appreciate these positive comments and they mean a lot to us. Thank you again.\n\nWe understand that the main reason for our score of 5 is due to a somewhat philosophical question of whether WCMDPs fit into the NeurIPS conference. We provide our rebuttal to this point below and hope that the reviewer is willing to consider raising the score, especially in light of the reviewer’s strong positive comments regarding the technical strengths of the paper.\n\nBelow is our response.\n\n*My biggest concern about this work is the audience. As a practitioner in deep RL, this is literally the first time for me to hear the problem of WCMDP. Although I do appreciate that this work teaches me a lot, I don't know whether this paper can attract the attention of the deep RL community, particularly considering the test domains are pretty toy. This paper looks to me more like a work that brings deep RL techniques to the OR community rather than the reverse direction.*\n\n* We would like to make two main points for why we believe WCMDPs would be valuable to the deep RL, and more generally, the NeurIPS community.\n\n  1. First, the NeurIPS community has recently shown a strong interest in moving beyond the traditional domains (Atari, board games, MuJoCo, etc) into arguably more practical settings. For example, the RL4RealLife Workshop at NeurIPS 2022 featured talks on inventory management, manufacturing, finance, energy demand response, traffic signal control, data center optimization, commercial cooling systems, power grid optimization, healthcare, and more. Most of these topics were originally studied in the OR community. Leading AI labs like Deepmind have also shown an interest in data center cooling optimization (another OR problem).\n  2. Second, weakly coupled MDPs are highly relevant to problems in online advertising, which is a domain that is of interest to the NeurIPS community. The paper Boutilier and Lu (2006), published in UAI and authored by Google researchers, makes use of a weakly coupled MDP for the problem of budget optimization in online advertising. In addition, many papers on restless bandits (which are very closely related to weakly coupled MDPs) have been published in AI conferences; two such examples are Mate et al., 2020 (NeurIPS) and Killian et al., 2022 (UAI), suggesting that there is existing interest in these models from AI researchers.\n\n* We hope that the reviewer agrees that the problems we study in this paper are real-world problems with huge state (continuous and up to 10 dimensions) and action spaces (3^10), each with significant practical interest. We believe this work will have a positive impact on the deep RL community and hopefully leads to or encourages a shift toward solving practical, real-world problems.\n\n\n\n\n\n"}, {"review_id": "Eulp2GJ7xx", "reviewer": "Reviewer_da8o", "summary": "The authors present a new algorithm, \"WCDQN\" for solving structured problems know as weakly coupled MDPs. The method dynamically estimates upper bounds via Lagrangian relaxation essentially to improve the value of collected experience across the structured subproblems. The authors present a (re)formulation of the problem via the dual bound of the linking constraints and numerically demonstrate the effectiveness of the method on a set of WCMDP problems.", "questions": "1. It would seem to be the case that this method should scale significantly better for problems with specific substructure. Why not demonstrate this explicitly with a custom problem / domain to validate the extreme case?\n2. [note] I think Fig3 is missing a y-axis?\n3. [note] your compilation resulted in non-clickable links,", "limitations": "NA - nothing in addition to what is present in the actual mathematics.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Nicely written, enjoyable reading\n2. Relatively simple and clear problem formulation\n", "weaknesses": "1. moderate ablation. the proposed method allows for a decomposition based on the number of \"subproblems\" but the relative effect to this key variable is not explicitly tested", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind comments (“Nicely written, enjoyable reading\", \"relatively simple and clear problem formulation”). It seems that the main concern that the reviewer had is due to the lack of an experiment showing the effect of the number of subproblems on the solution quality. We have now performed this experiment (details below) and hope that we addressed the reviewer’s concern. If so, we’d appreciate it if the reviewer could consider raising their score.\n\n*Moderate ablation. the proposed method allows for a decomposition based on the number of \"subproblems\" but the relative effect to this key variable is not explicitly tested*\n\n* Regarding the reviewer’s concern about the relative effect of the algorithm with respect to the number of subproblems, this is a great point. We’ve just completed a new experiment that studies the performance improvement from WCQL over vanilla QL as the number of subproblems increases. The **results are in the attached PDF of the global response** and validate our hypothesis that the benefits of WCQL become larger as the number of subproblems increases. This provides some additional evidence for the practicality of this approach, especially in regimes where standard methods fail. \n\n*It would seem to be the case that this method should scale significantly better for problems with specific substructure. Why not demonstrate this explicitly with a custom problem / domain to validate the extreme case?*\n\n* We have created a new figure to visualize the type of weakly-coupled structure for which our method is designed; **please see the attached PDF of the global response**. The visualization shows that a primary agent needs to make decisions for $N$ **nearly independent subproblems** (represented by red, blue, and yellow), except that the decisions must satisfy a global resource constraint. In our view, all of the numerical examples we provided (EV charging, multi-product inventory, and online ad-matching), are already specifically selected because they enjoy such structure: \n  * In the EV charging problem, each charging spot is a subproblem, but the EV charging manager needs to make sure the overall electricity cost at any given time does not exceed a certain amount.\n  * In the multi-product inventory problem, each type of product being manufactured is its own subproblem, but the decision maker needs to make sure that the manufacturing resources used at each time period does not exceed a particular budget.\n  * In the online ad-matching problem, each advertiser is a subproblem, but the ad company can only assign each impression to only one advertiser.\n* Therefore, we are not sure what kind of custom problem we can add. Did the reviewer have something specific in mind? Please let us know if we misunderstood the question.\n\n*I think Fig3 is missing a y-axis?*\n\n* In Fig 3, the y-axis are the Q-values. Sorry that this was mistakenly removed. We will add the y-label to the figure to make it clear.\n\n*Your compilation resulted in non-clickable links.*\n\n* Noted, thanks! We will fix this in the final paper."}, {"review_id": "n5Rw3FxvY7", "reviewer": "Reviewer_QmyG", "summary": "The paper studies value-based control agents for Weakly Coupled MDPs (WCMDPs), which comprise independent subproblems linked by an action constraint. The authors generalize an existing Lagrangian relaxation approach to action-value methods learned by stochastic approximation to obtain Weakly Coupled Q-Learning (WCQL). Essentially, a Lagrange multiplier is used to create an overestimate of $Q^*$ called $Q^{\\lambda*}$; taking the minimum of these two value functions can lead to faster convergence without changing the fixed point. A deep-learning extension of this method relying on a soft constraint added to the DQN loss yields the titular method Weakly Coupled Deep Q-Network (WCDQN). The proposed methods are tested against several well-known baselines (such as DQN and Double DQN) and compare favorably on three WCMDPs: electric vehicle charging (tabular only), multi-product inventory control, and ad matching problems.", "questions": "- Why is $\\lambda$ called the penalty vector? Is it not a scalar, i.e., the Lagrange multiplier?\n- How long (in timesteps) were the agents trained in each of the experiments? Since the figure x-axes use episodes, did agents receive unequal training time?\n- How was the penalty coefficient $\\kappa_U=10$ chosen?", "limitations": "- Need to choose the set $\\Lambda$\n- Added computational expense\n- Upper bound potentially violated with function approximation and soft constraint", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Self-contained descriptions of Weakly Coupled MDPs and Lagrangian relaxation, as well as a complete related works discussion, make the paper accessible to people (like me) who do not normally work in this setting. The explanations are clear and well written. \n- Interesting theoretical results in the tabular setting. The convergence results look correct and intuitive to me. I checked the proofs in the appendix.\n- Interesting, realistic experiment domains and strong empirical results.", "weaknesses": "- WCQL relies on discretizing $\\lambda \\geq 0$ into a finite set of values $\\Lambda$ to approximate the upper bound $\\min_{\\lambda} Q^{\\lambda}$. Although this does not affect the ultimate convergence to $Q^*$ in the tabular case, I would imagine that this choice has a significant impact on empirical performance, yet the authors do not discuss this or how to choose the set (that I was able to find at least).\n- The computational requirements of the proposed methods are downplayed. The authors state, “We note that, especially in settings where the limiting factor is the ability to collect enough experience, these bounds come nearly for free in that they only require computing a few additional quantities and importantly, they do not require additional experience.” I think this is a strong claim; compared to Q-Learning, at least $N$ additional Q-functions are needed to form the upper bound $Q^{\\lambda*}$. In the deep RL setting, only one extra network appears to be needed, in order to generalize over these $N$ functions, but that still doubles the overall computation. Thus, I do not think it is fair to say that the method comes for free; however, the strong empirical results do justify the extra expense.\n- Although the tabular theory is sound, the implications of porting it to deep function approximation are unclear and not fully appreciated by the paper in my opinion. The authors say, “the [loss] penalty softly ensures that learned network satisfies the bounds obtained from the Lagrangian relaxation.” However, because the constraint is soft, it does not ensure anything. If the approximated upper bound ever dips below Q*, then the wrong value will be bootstrapped by the network and the learned returns will be suboptimal. Of course, this is inevitable with function approximation (a hard constraint cannot be enforced), but it is worthwhile to clarify in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort spent providing a thorough review of the paper and for the positive comment on the writing (“Self-contained descriptions of Weakly Coupled MDPs and Lagrangian relaxation, as well as a complete related works discussion, make the paper accessible... The explanations are clear and well written”) and the contributions (“Interesting theoretical results in the tabular setting. The convergence results look correct and intuitive to me. I checked the proofs in the appendix. Interesting, realistic experiment domains and strong empirical results.”). \n\nWe address the reviewer’s concerns below. We would highly appreciate it if the reviewer can increase their score if our responses are able to address the reviewer’s concerns.\n\n*WCQL relies on discretizing  into a finite set of values to approximate the upper bound. Although this does not affect the ultimate convergence in the tabular case, I would imagine that this choice has a significant impact on empirical performance, yet the authors do not discuss this or how to choose the set (that I was able to find at least).*\n\n* This is a good point. Under a mild condition, there is way to determine a range [0, \\lambda_max], such that the \\lambda*, the minimizer of the Lagrangian, falls within this range.\n  * Mild condition: Suppose that for each subproblem i, there is a “zero action” a_i^0 = 0 that contributes zero cost and that all actions contribute non-negative cost (and therefore B(w) >=0 in order for the problem to make sense). Note that in all three of our examples, a zero action exists (the interpretations are “do not charge EV”, “allocate zero resources to the product”, and “do not assign the impression to an advertiser” for the EV charging, multi-product inventory, and online ad-matching problems, respectively), so we believe this is indeed a mild condition for most WCMDPs.\n  * For ease of presentation (not necessary), all subproblem action spaces are {a^0, a^1, …, a^|A|}, where a^k are sorted such that a^k <= a^{k+1}. Also, suppose WLOG that rewards are within [0, R_max].\n  * We claim that we can set \\lambda_max = R_max / [(1-\\gamma) * a^1]. Here is a sketch of the argument.\n    * Consider the Lagrangian MDP given in equation (3) and consider a particular subproblem i, represented by equation (4).\n    * If we take the “zero-action policy”, i.e., always select a^0 for any state, then the value of this policy is non-negative and independent of \\lambda by equation (4): Q_i^{\\lambda, \\pi_0}(s_i, a^0) >=0.\n    * Next, note that r_i(s_i, a_i) + \\gamma E[max Q_i^\\lambda(s’_i, a’_i)] <= R_max / (1-\\gamma) for any \\lambda, s_i, and a_i due to the nonnegativity of both \\lambda and a. Therefore, for any action a^k where k >= 1 (i.e., all actions except the zero action), we have that Q_i^\\lambda(s_i, a^k) < 0 whenever \\lambda > \\lambda_max.\n    * However, we know the “zero-action policy” achieves non-negative value for each subproblem and that this value is independent of lambda. Hence, looking at equation (5), we see that Q^\\lambda(s, a) must be increasing in \\lambda for all \\lambda > \\lambda_max. This means that we only need to consider [0, \\lambda_max] to find the minimizer of the Lagrangian.\n\n* We would be happy to include a discussion and this result in the paper / appendix.\n\n*The computational requirements of the proposed methods are downplayed. The authors state, “... these bounds come nearly for free in that they only require computing a few additional quantities and importantly, they do not require additional experience.” I think this is a strong claim; compared to Q-Learning, at least additional Q-functions are needed to form the upper bound. In the deep RL setting, only one extra network appears to be needed, in order to generalize over these functions, but that still doubles the overall computation. Thus, I do not think it is fair to say that the method comes for free; however, the strong empirical results do justify the extra expense.*\n\n* Thanks for your comment. We agree with you -- our intention was to primarily communicate that our method does not require additional experience, but we now see that this was unclear. We will fix the wording as follows: “We note that, especially in settings where the limiting factor is the ability to collect enough experience, one can trade-off extra computation to derive these bounds and improve RL performance without the need to collect additional experience.”\n\n*Although the tabular theory is sound, the implications of porting it to deep function approximation are unclear and not fully appreciated by the paper in my opinion... The authors say, “the [loss] penalty softly ensures that learned network satisfies the bounds obtained from the Lagrangian relaxation.” However, because the constraint is soft, it does not ensure anything...worthwhile to clarify in the paper.*\n\n* Noted and we agree. Our intent was to acknowledge this using the wording \"softly ensures\", but now realize that this wording is confusing. We will edit this as you suggested.\n\n*Why is $\\lambda$ called the penalty vector? Is it not a scalar, i.e., the Lagrange multiplier?*\n\n* Yes, you are correct $\\lambda$ is a scalar, not a vector. We will correct this typo in the paper.\n\n*How long (in timesteps) were the agents trained in each of the experiments? Since the figure x-axes use episodes, did agents receive unequal training time?*\n\n* Please note that all agents were trained for the same number of time-steps (EV charging 300,000; multi-product inventory control problem 125,000; online-stochastic ad matching 300,000 steps)\n\n*How was the penalty coefficient $\\kappa_U$ chosen?*\n\n* We performed a small amount of manual hyperparameter tuning, trying a few coefficients {1,2,4,10}, and 10 seemed to have the best performance. In general, because this penalty coefficient is over a one-dimensional space, our recommendation is to conduct a simple grid search. We will add this recommendation to the paper."}]

Author rebuttal:
We thank all reviewers for their thoughtful comments and suggestions. Since receiving the reviews, we have completed a new experiment that studies the performance improvement from WCQL over vanilla QL as the number of subproblems increases, as suggested by Reviewer da8o. This is a great suggestion and validates our hypothesis that the benefits of WCQL become larger as the number of subproblems increases. The new results provide further evidence regarding the practicality of WCQL/WCDQN, especially in regimes where standard methods fail. The results are shown in the attached PDF.

We also included a visualization of a weakly-coupled problem in the attached PDF as a response to a question by Reviewer da8o. However, we hope that the visualization can also be useful to all readers to give them a better understanding of weakly-coupled problem structure.

Meta-review: After discussion with the authors, all the reviewers are recommending to accept the paper. This is also my recommendation.
Decision: Accept (poster)