Efficient Reinforcement Learning in Resource Allocation Problems Through Permutation Invariant Multi-task Learning
Authors: Desmond Cai
Shiau Hong Lim
Laura Wynter
Venue:  (2021)

Abstract: One of the main challenges in real-world reinforcement learning is to learn successfully from limited training samples. We show that in certain settings, the available data can be dramatically increased through a form of multi-task learning, by exploiting an invariance property in the tasks. We provide a theoretical performance bound for the gain in sample efficiency under this setting. This motivates a new approach to multi-task learning, which involves the design of an appropriate neural network architecture and a prioritized task-sampling strategy. We demonstrate empirically the effectiveness of the proposed approach on two real-world sequential resource allocation tasks where this invariance property occurs: financial portfolio optimization and meta federated learning.

Under review as a conference paper at ICLR 2021
EFFICIENT REINFORCEMENT LEARNING IN RESOURCE ALLOCATION PROBLEMS THROUGH PERMUTATION INVARIANT MULTI-TASK LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
One of the main challenges in real-world reinforcement learning is to learn success- fully from limited training samples. We show that in certain settings, the available data can be dramatically increased through a form of multi-task learning, by ex- ploiting an invariance property in the tasks. We provide theoretical performance bound for the gain in sample efficiency under this setting. This motivates a new approach to multi-task learning, which involves the design of appropriate neural network architecture and a prioritized lask-sampling strategy. We demonstrate empirically the effectiveness of the proposed approach resource allocation tasks where this invariance property occurs: financial portfolio optimization and meta federated learning.
real-world sequential
INTRODUCTION
Sample efficiency in reinforcement learning (RL) is an elusive goal. Recent attempts at increasing the sample efficiency of RL implementations have focused to large extent incorporating models into the training process: Xu et al. (2019); Clavera et al. (2018); Zhang et al. (2018) 8 Berkenkamp et al. (2017): Ke al. (2019); Yarats al. 2019): Huang al. 2019); Chua et al. (2118) [Serban et al. (2018). The models encapsulate knowledge explicitly, complementing the experiences that are gained by sampling from the RL environment. Another means towards increasing the availability of samples for a reinforcement learner is by tilting the training towards one that will better transfer to related tasks: if the training process sufficiently well adapted to more than one task, then the training of a particular task should be able to benefit from samples from the other related tasks. This idea was explored a decade ago in Lazaric & Ghavamzadeh (2010) and has been gaining traction ever since, as researchers try to increase the reach of deep reinforcement learning from its comfortable footing in solving games outrageously well to solving other important problems. Yu 2018) discusses a number of methods for increasing sample efficiency in RL and includes experience transfer one important avenue, covering the transfer of samples, as we do here, transfer of representation or skills, and jumpstarting models which are then ready to be quickly, i.e. with few samples, updated to different tasks. D'Eramo et al. (2020) address the same idea, noting that multi-task learning can improve the learning of each individual task, motivated by robotics-type tasks with underlying commonality, such as balancing a single vs. a double pendulum, or hopping vs. walking.
We are interested in exploiting the ability of multi-task learning solve the sample efficiency problem of RL. Our setting does not apply to all problem classes nor does it seek to exploit the kind of physical similarities found in robotics tasks that form the motivation Lazaric & Ghavamzadeh (2010); D'Eramo et al. (2020). Rather, we show that there are number of reinforcement learning tasks with a particular fundamental property that makes them ideal candidates for multi-task learning with the goal of increasing the availability of samples for their training. We refer to this property as permutation invariance. It is present in very diverse tasks: we illustrate it on a financial portfolio optimization problem, whereby trades are executed sequentially over a given time horizon, and on the problem of meta-learning in a federated supervised learning setting.
Permutation invariance in the financial portfolio problem exhibits itself follows: consider the task of allocating a portion of wealth to each of a number of financial instruments using a trading policy. If the trading policy is permutation invariant, one can change the order of the instruments without

---

Under review as a conference paper at ICLR 2021
changing the policy. This allows one to generate multiple portfolio optimization tasks from a given set of financial instruments. A commonality between applications that have this property is that they concern sequential resource allocation: at each time step, the resource allocation scores the quality of each available candidate entity (for example a financial instrument in the above example), then based on those scores, apportions out the resource (the total wealth to invest, in the above example) among the entities at that time step, so that over the horizon of interest, the reward is maximized.
Sequential resource allocation problems include applications such as sequential allocation of budget, sequential allocation of space, e.g. in IT systems, hotels, delivery vehicles, sequential allocation of people to work slots or appointments, etc. Many such applications possess permutation invariance in that the ordering of the entities, i.e. where the resources are allocated, can change without changing the resulting optimal allocation. We show that under this form of permutation invariance, it is possible to derive a bound on the performance of the policy. The bound is an extension of that of Lazaric Ghavamzadeh (2010), and while similar to, provides additional information beyond the bound D'Eramo et al. (2020). We use the bound to motivate an algorithm that allows for substantially improved results as compared with solving each task on its own. The bound and the algorithm are first analyzed synthetic problem that validates the bound in our theorem and confirms the multi-ta gain that the theory predicts. Hessel et al. (2018); Bram et al. (2019) have cautioned against degrading of the performance each task when some tasks bias the updates to the detriment of others in multi-task learning. They claim that some tasks have a greater density or magnitude of in-task rewards and hence a disproportionate impact on the learning process. In our setting, deleterious effects of some tasks on others could also arise. The algorithm we propose handles this through form of prioritized sampling, where priorities are put on the tasks themselves, and acts like a prioritized experience replay buffer, applied to a multi-task learning problem. We show empirically that the priorities thus defined protect the overall learning problem from the deleterious effects that unrelated or unhelpful tasks could otherwise have on the policy.
The contributions of this work are as follows: (1) we identify the permutation invariance property of the class of reinforcement learning problems involving sequential resource allocation, (2) we define method to increase sample efficiency in these reinforcement learning problems by leveraging this property of permutation invariance; (3) we provide theoretical performance bound for the class of problems; (4) we validate experimentally the utility of permutation variance on sample efficiency as well as the validity of the bound on synthetic problem; and (5) we illustrate two real-world RL resource allocation tasks for which this property holds and demonstrate the benefits of the proposed method sample efficiency and thus also the overall performance of the models.
2 RELATED WORK
A notable first stream of work on leveraging multi-task learning for enhancing RL performance on single tasks can be found in Wilson et al. (2007); Lazaric & Ghavamzadehi (2010) which consider, as we do, that there is an underlying MDP from which the multiple tasks can be thought to derive. They use however a Bayesian approach and propose a different algorithmic method than ours. Our results extend performance bounds by Lazaric al. (0022) on single-task RI. As noted by Yu 2018). jumpstarting, or distilling experiences and representations of relevant policies is another means to increasing sample efficiency in solving a new but related problem. Rusu al. (2016) uses this idea in so-called progressive neural networks and Parisotto et al. (2015) leverage multiple experts to guide the derivation of a general policy. With a similar objective, Teh et al. (2017) define a policy centroid, that is, shared distilled policy, that captures the commonalities across the behaviors in the tasks. In all of these distillation-type methods, the tasks considered are simple or complex games.
Teh et al. (017)) note that their policy centroid method, distral, is likely to be affected by task interference, in that differences across tasks may degrade the performance of the resulting policy of any of the constituent tasks. This topic was studied by Hessel et al.) (2018); Bram et al. (2019). Hessel et al. (2018) proposed solution to this by extending the so-called PopArt normalization van Hasselt et al. (2016) to re-scale the updates of each task so that the different characteristics of the task-specific reward do not skew the learning process. Bram et al. (2019) use a different approach that learns attention weights of the sub-networks of each task and discards those that are not relevant or helpful. Vuong et al. (2019): D Erammo et al. (2020) are, like our work, concerned with sharing of experiences to facilitate a more sample-efficient learning process. Vuong et al. (019) suggest
2

---

Under review as a conference paper at ICLR 2021
identifying the shared portions of tasks to allow sharing of samples in those portions. The work of D' Eraamo et al. (2020) is in some ways quite similar to ours: the authors' goal is the same and they do the performance in this setting. However, their setting is different in that their tasks have both shared and task-specific components, and their bound becomes tighter only as the number of tasks increases. In setting, we do not require task-specific component, and we are able to show how the distance between the MDPs of each task, in addition to the number of tasks, affects the strength of the bound. Recently, permutation invariance has been exploited in deep multi-agent reinforcement learning (Liu et al., (019) where the invariance properties arise naturally in homogeneous multi-agent setting. TThiir work employs permutation invariance in learning the critic whereas in our case the entire learned policy employs permutation invariance.
derive a bound
3 PRELIMINARIES
We begin by defining notation. For a measurable space with domain X. let S(X) denote the set of probability measures over X, and ((2; L) the space of bounded measurable functions with domain X' and bound 0 < I. < co. For a measure p E S(2') and a measurable function ʃ X - IR, the
12 (p) (p)-nrrm of f is Ilfflpp and for a set of n points X1, Xx, E X, the empirical norm, [l. 1l2 is
n
11f1 p(x)) and Il = Σ f(x,)²
Let Il. = supzex [x(x be the supremum norm of f. Consider a set of MDPs indexed by Each MDP is denoted by tuple M, = A, Rt, P), where X, bounded closed subset of the s-dimensional Euclidean space, is a common state space; A is a common action space, R. : X' A E8 is task specific reward function uniformly bounded by Rmax- Pt is task specific transition kernel such that Pr(-ka, a) is a distribution over X' for all x E X' and E A, and E (0, 1) common discount factor. Deterministic policies are denoted by π X' - A. For given policy ग, the MDP Me is reduced to a Markov chain M = (X, R PT. .7) with reward function R. (a)) = Rx( x (ar), transition kernel (-(x)) = Pr(-|ar, (x)), and stationary distribution P The value function V for MDP / is defined as the unique fixed-point of the Bellman operator T, : B(x; Vmax = Rmax/(1 ())) + (X;; Vima), given by
(T (2 (x) + f PT(dyl=)V()).
Let ..." denote the optimal policy for M, The optimal value function V, for M, is defined as the unique fxxed-poitt of its optimal Bellman operator T which is defined by
V) = max R1 a) + P.(dylz. a)V a
To approximate the value function V. we use a linear approximation architecture with parameters IRd and basis functions ip; B(X; L) for = -, ,d. Let p()) (.)))))... " Rd be the feature vector and F the linear function space spanned by basis functions 9ú: Thus, F = {ffa a E Rd and fa(-) Ta)..
Consider a learning task to dynamically allocate a common resource across entities U4 C Ut Each t corresponds task, but for now take t to be an arbitrary fixed index. At each time step n, the decision maker observes states 2n = (Ii,))EE,, of the entities, where Zi,n is the state of entity i, and takes action a,, (ai,))seu,, where ai,x is the share of the resource allocated entity The total resource capacity is normalized to 1 for convenience. Therefore, allocations satisfy 0 S ai,n < 1 and Eieu, úi,n = 1. We consider policy (x.))) parameterized by 0. Assume that we have access to the reward function R, as well as simulator that generates trajectory of length N given any arbitrary policy ne. The objective of the learning task is to maximize
(.(0)= = E Σ m- - Re(an, an) (x+1 mo(#n), Unt1 ~ P.(./an, an), 21 P(O)
In many settings, N is small and simulators are inaccurate; therefore, trajectories generated by the simulator are poor representations of the actual transition dynamics. This occurs in batch RL where trajectories rollouts from dataset. In these cases, policies overfit and generalize poorly.
3

---

Under review as a conference paper at ICLR 2021
4 THEORETICAL RESULTS
We introduce first a property that we term connuutttioninvvriinnt for the policy network that can be shown to help significantly reduce overfitting.
Definition (Permutation Invariant Policy Network) A policy network mg is permutation invari- ant if satisfies (x()(x)) = a (TT (2)) for any permutation a.
Permutation invariant policy networks have significant advantages over completely integrated policy networks. While the latter are likely to fit correlations between different entities, this is not possible with permutation invariant policy networks as they are agnostic identities of entities. Therefore, permutation invariant policy networks are better able to leverage experience across time and entities, leading to greater efficiency in data usage. Moreover, observe that the transition kernels can be factored into independent and identical transition kernels across entities, then the optimal policy is indeed permutation invariant.
Our main theoretical contributions start with an extension of results from Lazaric et al. (2012), where a simite-sample error bound was derived for the least squares policy iteration (LSPI) algorithm on single task. Lazaric et al. (2022) provided high-probability bound the performance difference between the final learned policy and the optimal policy, of the form G1 02/ /N, where с₁ and 22 are constants that depend on the task and the chosen feature space, and N is the number of training examples. We extend their result by showing that, long tasks e-close to each other (with respect to a similarity measure we define later), the error bound of solving each task using our multi-task approach has the form C1 + c2/v + C36, where I' is the number of tasks and c3 task-dependent constant. Specifically, our theorem provides a general result and performance guarantee with respect to using data from different but similar MDP. Definition I provides basis for generating many such MDPs. Finally, the benefit of doing so shall be provided by Corollary [2] Thus, provided is small, a given task can benefit from a much larger set of NT training examples.
In addition to the assumptions of Lazaric al. (2012), we extend the definition of second-order aiscoue concentrability, proposed in Antos et al. (2008), and define the notion of first-order bescounted-average concentrability. The latter will be used in our main result, Theorem |
Assumption There exists a distribution E S(X) such that for any policy that is greedy with respect to a function in the truncated space F, S Cp. for all t, where C < co is a constant. Given the target distribution a E S(X) and an urbitrary sequence of policies {Tm [mm)m2 let
d(pPm
pmm
Ca
sup
do
TI Tly....
We assume that Coayo C" < 3o, and define first and second order discounted- concentrabil- ity of future-state distributions as follows:
C² (1-
Σ Tmhh " (m),
m²0
CH = (1 (1-10 7)2 my m Co.
Theorem (Multi-Tash Finite-Sample Error Bound) Let M== = A, be an MDP with reward function R and transition kernel P. Assume A finite. Denote its Bellman operator by
(T*V)()) (x) +
(=(d))=))V())
Given a policy n. define the Bellman difference operator between M, and M to be D.V T.V -V Apply the LSPI algorithm M, by generating, at each iteration of size N, where N satisfies Lemma 4 in Lazaric al. (2012). Let V-1 E F be an arbitrary initial )11) be the sequence of value functions (truncated value functions) generated by the LSPI after K iterations, and na be the greedy policy wat. the truncated value function V4-1. Suppose also that
path from M
value function. Vo.... VK-1 (Vo.... VK-1)
DD 1|, S cV n, and 1D,'Ve ScV K.
4

---

Under review as a conference paper at ICLR 2021
Then. for constants C1 C2. C3. Ct that are dependent on M. with probability 8 (with respect the random samples): IIVe - V 1l. S c1
1
+ oze / Co + eay CO m
+ c4.
VN
The proof is deferred to the Appendix. Theorem T formalizes the trade off between drawing fewer samples from the exact MDP M₁, versus drawing more samples from different MDP M. Importantly, it shows how to benefit from solving a different MDP, .M, when: (a) additional samples can be obtained from M, and (b) M is not too different from MM. In particular, the distance measure simply the distance between the Bellman operators the MDPs, which can be bounded the difference in both the transition and reward functions bounded.
In recent work, a performance bound for multi-task learning was given in Theorem and 3 of Framo et al. 2020). However, the authors used different setup containing both shared and task-specific representations, and their focus was on showing that the cost of learning the shared representation decreases with more tasks. They did not show how the similarity or difference across tasks affects performance. In contrast, our setup does not contain task-specific representations, and our focus is on how differences across MDPs impact the benefit of having more tasks (and consequently more samples). We show this in Corollary [ and Corollary 2
Remark 1 While our theoretical results are based on LSTD and LSPI and assume finite action space, our approach is applicable to a wide range of reinforcement learning algorithms, including policy gradient methods and MDPs with continuous action spaces. Deriving similar results for a larger family of models and algorithms remains an interesting, albeit challenging, future work.
Permutation invariant policy networks allow using data from the global set of entities U. Since the policy network is agnostic the identities of the entities, one can learn a single policy for all tasks, where each task E [7] is resource allocation problem over a subset of entities 24, For notational simplicity, assume that all tasks have the same number of entities, and all trajectories are of equal length N. Our approach can, however. be readily extended to tasks with different numbers of entities and different trajectory lengths. Permutation invariance allows a large set of MDPs to leverage the result of Theorem In the next section we shall provide algorithm, motivated by the following corollaries, and prioritized sampling strategy for this setting that drives significantly greater sample efficiency for the original task. The sampling strategy also helps stabilize the learning process, reducing the risk of deleterious effects of the multi-task setting, as discussed by Teh et al. (2017) and addressed in works such as Hessel al. (2018); Bram et al. (2019).
Corollary Let [T] be a set of similar tasks such that their distance from the average MDP, given by
T -1
1 E
R (x) + S Σ Pf (dylo)V
(T"V)(=)
is bounded by as defined in Theorem 7 Let N be the number of samples available in each task. Let ग be the policy obtained the T iteration when applying LSPI to the average MDP. Then, the suboptimality of the policy on each task is O(1/VNT) + O(e) + c some constant e (where suboptimality is defined according to Theorem
Recall that each task is formed by selecting a subset U, entities from the global set set We thus have the following sample gain that can be attributed to the permutation invariance of the policy network.
Corollary (Gain in Sample Efficiency from Permutation Invariance) Let M [2 and m [4g]. Given fixed M and m, there are T = (M) 2 (M different tasks. Then, by Cor I assuming all pairs of tasks are weakly correlated, the potential gain in sample efficiency is exponential in m.
Disregarding correlation between samples from tasks with overlapping entities Corollary and Corollary 2 together suggest that the (up to) exponential increase in the number of available tasks can significantly improve sample efficiency compared to learning each task separately.
5

---

Under review as a conference paper at ICLR 2021
5 EXPLOITING PERMUTATION INVARIANCE THROUGH MULTI-TASK REINFORCEMENT LEARNING
Our approach to exploiting permutation invariance is via multi-task reinforcement learning, where each "task" corresponds to particular choice of subset U4 C U. Furthermore, for each task, enforce permutation invariance among the entities i by forcing the neural network to apply the same sequence of operations to the state input 2; of each instrument through parameter sharing.
The proposed method, shown in Algorithm I learns a single policy by sampling subsequences of trajectories from the different MDPs. At each step. sample a task according to distribution defined by task selection policy p. Then, a minibatch sample B3 is drawn from the replay buffer for task f, and gradient descent is performed using the sampled transitions B, (altemnttively, samples can be generated using policy rollouts for the specific task), Separate replay buffers maintained for each task are updated only when the corresponding task being used.
In contrast with other active sampling approaches in multi-task learning, our approach maintains an estimate of the difficulty of each task as a score, st. After each training step. we update the score for only the sampled task based on minibatch B, avoiding evaluation over all the tasks. The scoring functions depend on the sampled minibatch; to reduce fluctuations scores for each task, exponential smoothing is applied 8, f 788 (1 - 7) scorer(B,) We propose a stochastic prioritization method that interpolates between pure greedy prioritization and uniform random sampling. Our approach is similar to prioritized experience replay (PER) by |Schaul et al. (0066), but while classical PER prioritizes samples, we prioritize tasks. The probability of sampling task & is Pt = s/ E. syr where the exponent determines the degree of prioritization, with seaerttnnce--aliinggggi (IS) weights wi = 1/(TP,)* that compensate
0 corresponding to the uniform
case. We correct for bias with for non-uniform probabilities if 1. We normalize weights by 1/ max, Wt. Tasks on which the reward variance is high can be interpreted as having more challenging samples, hence reward variance can be used scoring function.
Algorithm Prioritized Multi Task Reinforcement Learning for Increasing Sample Efficiency
Initialize policy network ne
Initialize replay buffers RI..... RT
Initialize time steps n, +- 1,..., nr +-
loop
Select a task ~ p to train on
Sample a random minibatch B, of transitions (Jin, On T'y Tn+1) from Rg
Update policy 0 using B; and chosen RI. approach (correcting for bias using IS weights w))
Update score 8t - 78; + (1 7) scorer(B:)
Update ALL selection probabilities p and IS weights
for n = ..g...., min + N.
N do
For task t, select action a, according to current policy and exploration noise Execute action an, and observe reward rn and new state In+1 Store transition (In, On; Fn+1) in Rs end for
If < N. update n, t- n + 1, otherwise, update n4 end loop
6 EXPERIMENTS
6.1 SYNTHETIC DATA
With the aim of validating the theory presented in Section 4 we define synthetic example to explore the efficiency gain afforded by permutation invariance. To do so, we control of the deviation c between any two tasks, thereby empirically validating the main theoretical results.
Consider a resource allocation problem where the observed state I; for each entity i E (1... m) is single scalar i; [0. 1]. The action space is the probability simplex, where each action

---

Under review as a conference paper at ICLR 2021
13
1.7
1225
1.6
1.000
Aveingge reonnn
Average roward
1.755
1.700
244
1,675
1450
1.0
1750
1,255
berber examples
Number examples
Figure Performance for c 0.8 (left), (middle), and at N 2000 with varying (right).
(a1 am indicates the fraction of resource allocated to each entity. The reward function is
R(x, a) = Σ T;00 Bra; log
where 8; is a weight parameter for each entity. Note that when 3 = for all i, the reward function becomes R(x,a) a) = #;a:) (a) where H the Shannon entropy. This implies that maximizing the reward involves a tradeoff between focusing resources on high 2; or distributing them uniformly across all i. Note that the reward function is permutation invariant, but that when we allow a varying 3 over the entities, the function deviates from being perfectly permutation invariant. We use the range max, 33 min; 3, as a stand-in for 6. Let m 10. For each 6, we run two experiments. The first examines the performance of policies trained by T.ST using N real examples drawn i.idd from the state-action space, for N 20... 2000. A small Gaussian noise added each reward make learning harder. The second experiment uses only 20 real examples, but augments the training set (up to N) through random permutation the real examples. The first two figures in Fig. T show the results for 0.8 and = respectively. Performance improves with N, as predicted by the I/VN term in error bound. Note that in the experiment using only 20 real examples, a performance gain is achieved by using permuted examples; this corresponds precisely to the multi-task gain predicted by the 1/VNT term. When is large, there a significant gap between the results of the two experiments, predicted by the c-term in the error bound. The last plot in Fig. [ shows this gap at N = 2000 when varies from 0 to 0.8.
6.2 REAL-WORD DATA
We consider two weal-world resource allocation settings: financial portfolio optimization and meta federated learning. Financial portfolio optimization is discussed below while meta federated learning in the Appendix. Given historical prices for a universe of financial assets, U, the goal of task / is allocate investments across subset of assets Ue C U. The multiple tasks thus correspond to multiple portfolios instruments. Permutation invariance will be of use in this setting since, from a given universe of instruments (e.g. the 500 instruments in the S&P 500), an exponential number of tasks can be generated, each with its own portfolio. Consider now one such task.
At the beginning of time period n. the action ag,n represents the fraction wealth the decision maker allocates to asset é. The allocations evolve over the time period due to changes in asset prices. Let Win denote the allocation of asset the end of time period n. We model the state of an asset using its current allocation and window of its H most recent prices. In particular, let v;,. denote the close price of asset over time period n, and Vi.n = Ui.n/ / denote the ratio of close prices between adjacent time periods] Then, the allocation asset at the end of time period n is given by
Wiin ΣiEu, Qi,nYim
and the state of asset at the beginning of time period n is given by
Din = (Wi Vi -i,n-1 H/ 00,- Vi Vi,n-2/ 1))
Daily high and low prices are also used in the state but omitted here for brevity.
7

---

Under review as a conference paper at ICLR 2021
STarc Prontsdd
0.0
-
Figure 2: Scatter plots of the maximum absolute deviation from Equal CRP vs. the change in re- wards every 50 steps (Ieft) and the max. norm of the gradient for the minibatch (right).
Figure 3: Mean performance gain over Equal CRP
of the learned policies when tested on 10 tasks us- ing out-of-sample instruments. Error bars denote the standard deviation over 10 experiments.
The change in portfolio value over period n depends on the asset prices and transaction costs incurred in rebalancing the portfolio from (wi,n- 1i)eu, to (ai,n)iett, The reward period is defined as the log rate of return:
(T an) = In 3 ((win-1)ie (As.))Eu))
Σ ni,n iEMe
where can be evaluated using an iterative procedure (see Jiang et al. (017)) Defining the reward this way is appealing because maximizing average total reward over consecutive periods is equivalent to maximizing the total rate return over the periods. To leverage this, we approximate (((wi,-11) (di,a)iEM,) R "iien, [Win-1 0i,n/. where is a commission rate to obtain
closed-form expression for (Z,, On) (see Jiang et al. (2017)). We optimize using direct policy gradient on minibatches consecutive samples
m-+B-1
0+0+
Σ
wi WeRa mo(un))
B
where ny the first time index in the minibatch, B the size of minibatch, and wi the IS weight for task t. As in Jiang et al.) (2017), we sample from a geometric distribution that prioritises recent samples and implement replay buffers for each task. benchmark trading strategy equal constantly-rebalanced portfolio (CRP) that rebalances maintain equal weights. As noted earlier, ideally one would prefer for the scoring function to depend only on the minibatch B, A deviation from Equal CRP can be viewed as learning to exploit price movements, and is thus here we use this as the goal of the policy, Prioritised MTL thus prioritises tasks which deviate from Equal CRP. Note that the policy deviates from CRP only when profitable. Let
scorer mE
max R.
To TT()n)
be the scoring tasks in Prioritised MTL using mean absolute deviation the minibatch allocation from Equal CRP. Figure 2 (left) shows scatter plot of the maximum score seen every 50 steps and the change in episode rewards in a single-task learning experiment, and (right) of the minibatch score and the maximum gradient norm for the minibatch. Higher scores imply higher variance in the episode rewards and hence more challenging and useful samples. The correlation between scores and gradient norms shows that approach is performing gradient-based prioritisation, (see Katharopoulos & Fleuret (2018); Loshchilov & Hutter (2015); Alain et al. (2013)) but in a computationally efficient manner. The details of the dataset and parameter settings can be found in the Appendix. Figure shows the performance of the learned policies tested on 10 tasks drawn from out-of-sample instruments. The policy network with weights initialized close to zero behaves like an Equal CRP policy. As noted, any profitable deviation from Equal CRP implies learning useful trading strategies. The plots show that the MTL policies perform well on instruments never seen during training, offering remarkable benefit for using RL in the design of trading policies. Fig. 4 shows the performance of prioritised multi-task learning (MTL) versus single-task learning (STL) (1.e. learning policy for each task independently the instruments in the task). We also show results for MTL without prioritised sampling, i.c., with a = We consider 5 tasks and 30 tasks. The plots show that prioritised MTL performs significantly better than STL in both convergence time and final achieved
8

---

Under review as a conference paper at ICLR 2021
Tasks
30 Tasks
30 Tasks
Pioriiied
Partamance
ouddon Toako
38
14
Prioitzedd MTL
MTL
Pricctione MTL
STL
MILL
20
50 100
40
60
50
120
-20
Epochs
# Epochs
Porformance Gain
Figure 4: The left plots show mean annualized return in the testing period over 10 experiments (different instruments) each with and 30 tasks. X-axes are scaled to make the curves comparable: each epoch has 1500 (5-tasks) and 9000 steps (30-tasks) and an evaluation. Shaded regions denote the interquartile range. The rightmost figure shows, for each fraction of tasks, the gain over Single Task Learning (STL.. A curve further to the right shows higher gain over STL. From 30% on the y y-axis, the P-MTL gain is higher (more towards the right) than the MTL gain. As expected, when few tasks are used, prioritizing tasks doesn't help much (y-axis from 0.2).
Portfolio Value
1.0
Prorllsed MTL
STL
Pris llar MTL
XS1
MS
Equail CRP
Aloution Fiudion
NTAP
NIAP
STL
CMBSA
CMCSA
30
IPG.
0.8
84
0.4
0./
0.2
EM
100
200
250
0.00
50
100
250
0.0
Days
150
200
C1121
Days
Days
Figure 5: Comparison of multi-task policy single-task policy the testing period for specific task. The leftmost plot shows the percentage gain in portfolio value over time for both policies against that from the baseline Equal CRP policy. The right two plots show the asset allocations.
performance. The performance with 30 tasks is significantly better than the performance with 5 tasks, showing that our approach leverages the samples the additional tasks.
Fig. 5 illustrates the typical behavior of multi-task learning (MTL) and single-task learning (STL) policy on the test period for tasks where multi-task policy performed significantly better. The single-task policy kept constant equal allocations while the multi-tasi policy was able learn more complex allocations. In financial data, strongly trending prices do not occur often and are inherently noisy. Multi-task learning with permutation invariance helps with both challenges, allowing the algorithm to learn more complex patterns in given training period.
7 CONCLUSIONS
We introduce an approach for increasing the sample efficiency of reinforcement learning in setting with widespread applicability within the class of sequential resource allocation problems. This property is permutation invariance: resources are allocated to entities according to a score, and the order can change without modifying the optimal allocation. Under this property, we show that bound exists on the policy performance. This bound motívates highly effective algorithm for improving the policy through multi-task approach. Using prioritized task-sampling. the method not only improves the reward of the final policy but also renders it more robust. We illustrate the property and the method on two important problems: sequential financial portfolio optimization and meta federated learning, where the latter is provided in the Appendix.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling, 2015.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning. 71 (1):89-129, 2008.
Felix Berkenkamp, Matteo Turchetta, Angela P. Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. In NIPS, 2017.
Timo Bram, Gino Brunner, Oliver Richter, and Roger Wattenhofer. Attentive multi-task deep reinforcement learning. In ECML/PKDD, 2019.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Data-efficient model-based reinforcement learning with deep probabilistic dynamics models. In NIPS 2018, 2018.
Ignasi Clavera, Jonas Rothfuss, John Schulman, Yasuhiro Fujita, Tamim Asfour, and Pieter Abbeel. Model-based reinforcement learning via meta-policy optimization. ArXiv, abs/1809.00 809.052144 4, 2018.
Carlo D' D'Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Sharing knowledge in multi-task deep reinforcement learning. In International Conference on Learning Representa- fions, 2020. Utttttts:///ppemt wwwp:erwwwweeeeeeeerrrreeeeeeeee dir.rruo/vii.d.roorvv/vvvv
Mattco Hessel, Hubert Soyer, Lasse Espeholt, Wojeiech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In AAAI, 2018.
Wenzhen Huang, Junge Zhang, and Kaiqi Huang. Bootstrap estimated uncertainty of the environment model for model-based reinforcement learning, In AAAI, 2019.
Zhengyao Jiang, Dixing Xu, and Jinjun Liang. deep reinforcement learning framework for the financial portfolio management problem, 2017.
Angelos Katharopoulos and Francois Fleuret. Not all samples are created equal: Deep learning with importance sampling. In ICML,, 2018.
Nan Rosemary Ke, Amanpreet Singh, Ahmed Touati, Anirudh Goyal, Yoshua Bengio, D. Parikh, and Dhruv Batra. Modeling the long term future in model-based reinforcement learning. In ICLR, 2019.
Alessandro Lazaric and Mohammad Ghavamzadeh. Bayesian multi-task tasti-task reinforcement learning. In ICMI., 2010.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Finite-sample analysis of least- squares policy iteration. Journal of Machine Learning Research, 13(0ct):304133774 2012.
Iou-Jen Liu, Raymond A. Yeh, and Alexander G. Schwing. PIC: permutation invariant critic for multi-agen agett deep reinforcement learning. In 3rd Annual Conference on Robot Learning. CoRL 2019, Osaka, Japan, October 30 November 1, 2019, Proceedings, pp. 590-602, 2019, URL http::/proceediini ngs mlmm wwt.:mmww........eeemee paress/vl00/e u20a html
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks, 2015.
Emilio Parisotto, Jimmy Ba, and Ruslan Salakhutdinov. Actor-mimic: Deep multitask and transfer reinforcement learning. CoRR, 00///511.00344 2015.
Andrei A. Rusu, Neil C. Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. ArXiv, abs/1606.04671, 2016.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference Learning Representations, 2016.
10

---

Under review as a conference paper at ICLR 2021
Iulian Serban, Chinnadhurai Sankar, Michael Pieper. Joelle Pineau, and Yoshua Bengio. The bottle- neck simulator: A model-basee deep reinforcement learning approach. ArXiv, abs/1807 Ne//100777.2.. 2018.
Yee Whye Tch, Victor Bapst, Wojeiech Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Manfred Otto Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In NIPS, 2017.
Hado van Hasselt, Arthur Guez, Matteo Hessel, Volodymyr Mnih, and David Silver. Learning values across many orders of magnitude. NIPS, 2016.
Tung-Long Vuong, Do Van Nguyen, Tai- Tai-Long Nguyen, Cong- Bui, Hai- Hai-Dang Kieu, Viet-Cuong Ta, Quoc-Long Tran, and Thanh Ha Lå. Sharing experience in multitask reinforcement learning. In IJCAI, 2019.
Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli. Multi-task reinforcement learning: hierarchical bayesian approach. In ICMI. '07, 2007.
Huazhe Xu, Yuanzhi Li. Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for
model-based reinforcement learning with theoretical guarantees. ArXiv, abs/l807 800.0/887,,,88, 2019.
Denis Yarats, Amy Zhang, Ilya Kostrikov, Brandon Amos, Joelle Pineau, and Rob Fergus. Improving sample efficiency in model-free reinforcement learning from images. ArXiv, abs/1910.01744 2019.
Yang Yu. Towards sample efficient reinforcement learning. In I/CAI, 2018.
Marvin Zhang, Sharad Vikram, Laura Smith, Pieter Abbeel, Matthew J. Johnson, and Sergey Levine. Solar: Deep structured latent representations for model-based reinforcement learning. ArXiv, abs/1808.0911 2018.
A APPENDIX
Theorem Let Let M= P, be an MDP with reward function R and transition kernel P. Denote its Bellman operator by
(T*V)<) R2 (x) + +7 pT (dyll)))(())
Given policy n, define the Bellman difference operator between M,, and M be DFV T.V TVV. Apply the LSPI algorithm to M. by generating, at each iteration k, path from M of size N, where satisfies Lemma 4 in Antos et al. (2008). Let V-1 E F be an arbitrary initial value function, vo... VK- .V..... Vx-1) be the sequence of value functions (truncated value functions) generated by the LSPI after K iterations, and T. be the greedy policy w.r.t. the truncated value function Vz-1- Suppose also that
|DD 11, SeVn, and ||D." VP.""i-illl S A.
Then, with probability 1 (with respect the random samples), we have
| V.Th la - (1 7)2
(1 (1+7) CC.,
(2V2F + Ez
2
8 8log (og(S/K/8))
11 + E
+ 1 1-
(V LV V1y (1
N
+ K-1
Rmax + 3E 20%
11

---

Under review as a conference paper at ICLR 2021
For convenience, we will simply remove the task subscript whenever we refer to variables associated with M. Define
Proof:
di D.V*,
d kk D Vk-1:
ex = VA= - -T*x Vis
Eい pTtt1 (1 7PP=nt1) -1 p (1 p
Fg pm (I p + pm (I - p
From the proof of Lemma 12 in Antos et al.
20088. we get
K-1
V V*x 22
FRee + (7 "K(V=' (7p=')"(("* V=0). Σ paprij-kkPPaee
By applying the above inequality, and taking the absolute value on both sides point-wise, we get
VV=
V
11,
( Fxlenl + (Y "Rpp")RiV" | -Va0| - IV 1**1+ I | Voa |+ + - V + | V,T*
K-1
< 7
V
K-1
Romxx K + |V, V= + V V
S
(yp=*)
-K Fxlexl + --7
k=
where we used the fact that V V S (2 7))1. Next, we derive upper bounds for IV, - v* and V V
(a) Observe that
V V
T V. V=
$ Vi - Vi
= V - VT + (V."
The first inequality follows from the fact that x² is optimal with respect to V=" The second inequality follows from the taylor expansion of the inverse term. By closely following the same steps, we also get
V V
Ti/ Vi T Vx"
2 THe Vi - -T=V= V*
= TT V= --'V= + +T. (V. - V=a
2 (1 - 21-
By splitting into positive and negative components and applying the above bounds, we get
= 1(V - V* (V. V=)=_
- 1(v V** ) + (V V" )-
$ [[ 7..i)- + [[I -7Pp")
< (T - - )-1(
12

---

Under review as a conference paper at ICLR 2021
(b) Observe that V
ViTK STKKVTK + +T TTEVR-I T,T FFKV V
=TIVAK + V T, FK- - TEN + T (Vax TT Vrtk)
-- d).
The first inequality follows from the fact that TTK is optimal with respect to VK-I. The second inequality follows from the taylor expansion of the inverse term. By closely following the same steps, we also get
VAR- - ViKK 2 TT* - TTK VK 1 + VK -
+ T,"x VK-' = T - T -
T,"
(VTK - ~VT
2 - PPT
+ d.,)).
By splitting into positive and negative components and applying the above bounds, we get V,Tx| = 1V V,mK), )+ - (V V,T*)-
|
S 1V -V, )+ + 1(V - v,T*)=
= ((T (
-(r,x)l + 1(T - ( dit + dr,x)l
S (I PP.K)
dit dc, k| + (1 --Pp")~ d.. + de
2 - - ) ((dTk] + (dr,
By applying the upper bounds from (a) and (b), we get
V VTT S 2(1 221
K-1
an laal a ((Bmxx/))
(1 7)
(8/6)B* b|d, + (3/6) G/d,'1
+ (B/3)BTK 6|d,*| (3/3) G|dckl
where we introduced the positive coefficients
(1 7)
0g 1 1- 1-2
K-h
0 K,
(1 7)
a 1 - gk+2 ? K+1
(1 1 7)
8 2(1 - - x2²
and the operators
A 1 7 ( Fr. for 0 kk K,
2
B" (1 7)(1 - -P.-)-1
2( 212 Note that the coefficients og a, and 3, sum to 1, and the operators are positive linear operators that satisfy A₁ = 1 and B=1 = 1. Therefore, by taking the pth power on both sides, applying Jensen't 's inequality twice, and then integrating both sides with respect to o (z),
Let Ax-
(1-7)*²
we get
1 ViTK Ip.0 - f o((d))lv -VTTK
V
< AKO
Σ AnAAleat lex + a(Rmx//))
+ (1/6))=((( (3/6) (6)47') 1)P
+ + (8/3))= (6)ār,
13

---

Under review as a conference paper at ICLR 2021
From the definition of the coefficients Co,, (m), we get
A $ (1 - 7)
Σ
2"h Ca (m+ K k))
m20
aB < -) ?
Σ
>mh (m.
m20
Therefore, follows that
K
K-1
a Asleel
$ Σ k=0
0kk
y Ca.u (m + K - -k)peexlP
k==
m20
711 7)
K-1
m Co (m K k)lles 12
1 - 7 +2
R=0
m20
$
C
c
K+2
where e maxoskeK |exl1E The terms involving 1 satisfy
(B"(6dd))))) - 69
Σ Y
co (m))dd71 S G,C,, 1paa
m20
Putting all these together, and choosing
2, we get
e2 + (1 -1-7// k
36(1 - -7)
V - Vinx 1la S x
- xk+2 (Rmux/
(Rma//>) /22
Cr
Comee
K+2
2(1 kt+2)
2
(rC + (1- (1-7)n
36(1 - 7)
$
k+)(+1( ())aa+((mma/)))) +
2 Co
(1 - 7)
2
[C e2 + (Reax//)) 180%,ue?
(1
7)2
2
CC
+y x21 Rmax + 3ev vee 222
7
The desired result can then be obtained by applying the same steps in the proof of Theorem 8 Lazaric et al. (2012).
A.1 FINANCIAL PORTFOLIO OPTIMIZATION: ADDITIONAL DETAILS
The dataset consists of daily prices for 68 instruments in the technology and communication sectors from 2009 2019. We use 2009-2018 for training and 2019 for testing. To validate that our approach learns common features across instruments, and thus can transfer, we reserve 18 instruments not seen during training for further testing. The global asset universe 4 used for training contains 50 instruments.
We construct tasks by randomly choosing a portfolio of [4,1 10 instruments for each task. We create a permutation invariant policy network by applying the same sequence of operations to every instrument state. That is, for each instrument, the flattened input prices are passed through a common RNN with 25 hidden units and tanh activation, this output is concatenated with the latest allocation fraction of the instrument, and passed through a common dense layer to produce score. Instrument scores are passed to a softmax function to produce allocations that sum to one. The smoothing parameter for the scores 7 0.2, a 0.5 for the task prioritisation parameter and B = 1.0 fully compensate for the prioritized sampling bias.
A.2 META FEDERATED LEARNING
Suppose we have a universe of federated learning clients U. The goal of task t is to aggregate models in federated learning experiment over subset of clients U4 U4 At each step n, the action di,z
14

---

Under review as a conference paper at ICLR 2021
MTL
STL
0.3
Wwkgght
Weigh
0.0
0.5
0.1
01
Festwg
0.0
Figure 6: These plots compare the behavior of multi-task policy and single-task policy during testing. FedAvg denotes the accuracy of federated learning with uniform averaging. The left plot shows the accuracy of the aggregate model during federated learning. The right two plots show the weights produced by the policy for different clients. Note that clients 8 and 9 possess 40% of the unique labels.
represents the weight assigned to the supervised learning model of client in the averaging procedure. Let Us,n denote the model of the client (i.e. the tensor of model parameters). We model the state of the client as some function of its H most recent models 2i.n f that the aggregator has access
Us.n). Assume small evaluation dataset that it can use to approximately assess the quality of models. We define the reward at each step to be the accuracy of the aggregate model, Rg (Ir; (n) = (Eieu, Vi,n where C(e) is function that provides the accuracy of model on the evaluation dataset. Therefore, by maximizing the total return over all time periods, seek to maximize both the accuracy at the final time step as well as the time to convergence. We optimize the policy using Proximal Policy Optimization (PPO).
We use the MNIST digit recognition problem. Each client observes 600 samples from the train dataset and trains a classifier composed of one 5x5 convolutional layer (with 32 channels and ReLu activation) and a softmax output layer. We use the same permutation invariant policy network architecture as before with 10 hidden units in the RNN. We randomly select [24 10 clients for each task. We learn using an evaluation dataset comprised of 1000 random samples from the test dataset and test using all 10000 samples in the test dataset. We fix the number of federated learning iterations 50.
We explore the benefit of MTL in identifying useful clients in scenarios with skewed data distribution. We partition the dataset such that 8 of the clients in each task observe random digits between 0 to and the remaining 2 clients observe random digits between 6 to 9. Therefore, for each task, 20% of the clients possess 40% of the unique labels. The state of each client are the accuracies of its H most recent models on the evaluation dataset.
Figure 6 shows the potential benefits of multi-task learning when simulators are inaccurate. In particular, we obtain two aggregation policies, one trained using single-task learning (STL), and another trained using multi-task learning (MTL), both trained using the same number steps, and we observe their behavior during testing. The plots show that multi-task learning is able to learn non-uniform averaging policies that improve the convergence and performance of federated learning runs. More importantly, it can perform better than single-task learning even with the same number of samples. This may be attributed to the wider variety of client configurations (and consequently experiences) in the multi-task approach.
15


Reviews:
[{"review_id": "nkXlOA8d2Y-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the problem of reinforcement learning using limited training samples. They propose a solution by exploiting the invariance property in the tasks. In particular, they present an algorithm that exploits permutation invariance, study its theoretical properties, and propose examples where this property holds and their algorithm can be leveraged.\n\nI feel the paper could have been better presented by starting with a motivating example where the permutation invariance property holds - for example the portfolio optimization example studied in the experiments. This will make it easy to follow the multiple terminologies of tasks, entities, resources, introduced in Sec 3. \n\nThe setting considered in the paper is one where the state is a concatenation of various entities, while the actions are the fraction of resources allocated to each entity. The permutation invariance property is defined in Def. 1. \n\nI didi not understand how a network trained using gradient descent alone would satisfy permutation invariance. There is no part of the pseudo code in Alg 1 explicitly making sure that the algorithm is permutation invariant.", "extra_scores": {}, "extra_text": {}}, {"review_id": "jf4lhi1ePSl", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses sequential resource allocation problem using reinforcement learning, where sample efficiency is the focus of the paper. The authors identify a key property in the targeted resource allocation problems -- the permutation invariance -- which intrinsically implies the independency of samples at different time steps. From this property the paper extends the work of D’Eramo et al. (2020) and derives a potentially tighter bound for the gap between the optimal policy and the policy learned from multiple tasks. The paper also designs a new algorithms that prioritizes sampling in multi-task learning that addresses the bias between training and target tasks. Empirical evaluations on financial portfolio allocation and meta federated learning demonstrate the effectiveness of the proposed approach.\n\nStrengths:\n1) Using RL to solve sequential resource allocation problems is interesting and well-motivated, it can promote the impact of RL approaches when deployed\n2) The paper has technical depth, and provides a theoretical guarantee of their approach\n3) The paper gives a good discussion of existing works and where the paper lies in the line; \n4) The empirical evaluations show two interesting case studies of sequential resource allocation problems. The paper contributes non-trivial efforts in designing experiment strategies for the two cases. The results demonstrate the effectiveness of the proposed approach.\n\nWeakness:\nA major weakness in my opinion is that the theorem is derived assuming the action space is finite, while in experiments and mathematical formulations the actions are denoted as continuous (thus infinite). This is however already clearly pointed out in the paper and placed as future work, so this is somewhat fine to me. \n\nSome comments:\n1) The paper gives a good discussion of existing works and where the paper lies in the line; it would be better if the authors can briefly discuss meta-RL which is close to the problem being studied in this paper\n2) The significance of the theorem is well-discussed. However it is hard to understand what does Assumption 1 imply -- Is it a strong or weak assumption? At what circumstances does this assumption hold?\n3) In the proof of the theorem, it is not clear -- what is the high-level intuition of the proof? How is permutation invariance property used?\n4) Figure 1 is placed before 2-4 but referenced only in the end of the experiment section\n5) Figure 2, the annotations left and right in the brackets are reversed.\n\nQuestions: please refer to Some comments points 2) and 3)\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "N2bkqX1L0Mq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an RL algorithm for multi-task learning. Under certain assumptions, the paper proves a sample complexity result for this setting. The paper presents a new algorithm based on this approach. The empirical results on the task of sequential portfolio optimization shows that this approach performs better than the policy of constantly rebalanced portfolio. \n\nI dont understand the aim of this paper and unfortunately, the paper did not help me either. It seems that the paper focuses on multi-task learning using RL. The main assumption the paper makes is permutation invariance (PI). However, the way paper defines it is not clear to me. \n\nDef 1: \"A policy network is PI if it satisfies pi(sigma(a), sigma(x)) = sigma(pi(a,x))\" for any permutation sigma. \nSo sigma is a permutation of items in a set? \nIn this case it seems the set is the output of policy network. What is the output of policy network: action? But the action is not defined as a set of items. It seems that one must guess that the actions are division of 1 resource among t entities. Lets say t = 2 and resulting action is [0.2, 0.8]\nIf this is true the the two permutation of a are [0.2, 0.8] and [0.8, 0.2]. But then the definition says the left-hand side should be equal to both these permutations. So [0.2, 0.8] == [0.8, 0.2]?\nI dont understand this. \n\nBy the defintion do you mean: pi(sigma(a), sigma(x)) = pi(a,x). This would mean that the rearrangement of state or actions do not change the output of the policy network. I can understand this but not the def in the paper. \n\nFinally, what does this PI means in real-life? Since the paper talks about resource allocation, does the PI mean that it does not matter which entity the resource is being allocated to as long as the share of resource does not change? For what kind of problems does such an assumption/property hold? What is one entity is better at utilizing resources than others?\n\nAfter going about the definition/assumption for quite some time, the main theorem of the paper does not even use the definition/assumption. So why was it introduced?\n\nFrom related work \"Lazaric et.al. provide a performance bound that bears similarity to ours, which one can consider an extension for our particular PI setting\". So which approach is more general, the one in Lazaric et. al or yours. Seems yours since Lazaric et.al. is an extension to your PI setting. But then the same sentence says yours is a particular setting? \n\nCorollary 2: \" the gain in sample efficiency can be exponential in m\". What is the meaning of 'can be'. Is it exponential or not? If yes, then under what condition? \n\nHow is portfolio optimization a multi-task RL problem? It can be formulated as a resource allocation problem but apart from maximizing long-term returns what are the other task the agent must perform for this problem. \n\nSorry to say that I tried quite hard but I could not make sense of either the text or mathematics of the paper.  It seems the paper presents an interesting attempt at resource allocation using RL but I found the writing highly confusing. \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "I5K8trbUGo", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an approach to reducing the sample complexity in multi-task reinforcement learning using permutation invariant policies. The main premise of the paper is that certain families of tasks exhibit approximate forms of symmetry, i.e., applying a permutation to the state/action variables would make all tasks similar in some metric sense. Then, the proposal is to learn a single permutation-invariant policy which will perform well on all of them simultaneously. An reinforcement learning algorithm to learn a permutation invariant policy is derived.\n\nTo get the technicalities out of the way, I think the paper is fairly well written and the related work is sufficiently well summarized (to my understanding). The authors are very open about the similarities to previous work and sources of inspiration. I checked the theory superficially and the results generally have the form I would expect (in terms of the involved quantities and their proportions), however, if there were more subtle issues, I certainly missed them. \nA few minor nits: in the statement of theorem 1, the authors present important quantities in the bound as if they were universal constants (c1, c2, c3). These quantities are not problem independent, they involve features of the problem so the statement of thm 1 creates the wrong impression. Moreover the appendix refers to theorem 1 as \"theorem 2\", which was initially confusing to me. Also it seems that the symbol pi switches semantics a few times - first, it denotes a deterministic policy, then a stochastic policy, and finally a policy network. It may be good to disambiguate them somehow for the sake of readability.\n\nI generally agree with the story, however, there are two major issues. First, the presentation is structured in a way that does not sell this work very strongly. A lot of effort is spent on setting up Theorem 1 in a completely detached way, and then it's actual relevance to the problem at hand is summarized in a hand-wavy corollary. From a paper claiming to solve resource allocation problems efficiently, I would expect at least the following: clearly articulate the problem. Argue convincingly that this particular problem class is hard (the arguments that N may be small and the simulator may be inaccurate are true for many problem classes). Explain the solution and how it exploits the structure of the problem. Finally present theory verifying the soundness of the solution. \n\nThe second issue concerns the application. While it's nice that the portfolio problem is somewhat grounded in reality, it's far from obvious that the theory explains what's going on in this problem. This problem is technically a POMDP, which is also suggested by the choice of on RNN as a policy network. The policy is then trained by policy gradient, which might be expected to behave differently on these problems. This gives us very little information about how good the proposed bound is. I believe this paper would benefit from a synthetic application where the difference in Bellman operators can be controlled precisely to see that the problem behaves as predicted by the theory. \n\nOverall, I think that the general direction is good, and significant progress has been made, however, the current state of the paper does not present a convincing story.\n ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles a problem of resource allocation using reinforcement learning. An important invariant - permutation invariant - is identified as an important characteristic of this problem. Then it is shown that taking advantage of such an invariant should  dramatically improve the sample efficiency.

On behalf of the reviewers, I would like to thank the authors for addressing many concerns raised in the initial reviews. Unfortunately, a further examination revealed several other potential issues that require further clarification:

1. It seems that real-data experiments do not really demonstrate whether the benefits of the approach come from multi-task learning or from permutation invariance. It would make sense to run an ablation study. In particular, if the benefit is really coming from multi-task learning, then the theory part of the paper becomes less relevant.

2. The metric used for finance application appear to be in-adequate. It is typical in finance academic literature to look some form of risk-adjusted returns. Is the MTL strategy just taking more risk? How statistically significant are the results?

Given these concerns the paper can not be accepted in its current form but we encourage authors to address these and resubmit. 
Decision: Reject