DATA-DRIVEN EVALUATION  OF TRAINING ACTION SPACE FOR REINFORCEMENT LEARNING
Authors: Rajat Ghosh
Debojyoti Dutta
Aroosh Sohi
Akshay Khole
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Action Selection
Cost Optimization
Shapely

Abstract: Training action space selection for reinforcement learning (RL) is conflict-prone due to complex state-action relationships. To address this challenge, this paper proposes a Shapely-inspired methodology for training action space categorization and ranking. To reduce exponential-time Shapely computations, the methodology includes a Monte Carlo simulation to avoid unnecessary explorations. The effectiveness of the methodology is illustrated using a cloud infrastructure resource tuning case study. It reduces the search space by 80% and categorizes the training action sets into dispensable and indispensable groups. Additionally, it ranks different training actions to facilitate superior RL model performance and lower cost. The proposed data-driven methodology is extensible to different domains, use cases, and machine learning algorithms.

Under review as a conference paper at ICLR 2022
DATA-DRIVEN EVALUATION OF TRAINING ACTION SPACE FOR REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Training action space selection for reinforcement learning (RL) is conflict-prone due to complex state-action relationships. To address this challenge, this paper proposes a Shapley-inspired methodology for training action space categorization and ranking. To reduce exponential-time shapley computations, the methodology includes Monte Carlo simulation to avoid unnecessary explorations. The effec- tiveness of the methodology is illustrated using a cloud infrastructure resource tuning case study. It reduces the search space by 80% and categorizes the training action sets into dispensable and indispensable groups. Additionally, it ranks dif- ferent training actions to facilitate high-performance yet cost-efficient RL model design. The proposed data-driven methodology is extensible to different domains, use cases, and reinforcement learning algorithms.
INTRODUCTION
reinforcement learning (RL) agent learns how to map states to actions in order to maximize a long-term cumulative award signal in a given environment. Figure I shows the various artifacts of an RL algorithm. An RL problem is defined by a quartet of (S, Pa Ra), where S is a set of states the state space; A is a set of actions or the action space available to influence S; (s, s¹) = Pr($t+1 = s'|s, = s, 0 = a) is the transition probability which is the probability that action a in state time will lead to state s' at time ++ 1; and finally, Rı (s, 6') is the immediate reward signal received after transitioning from state to state s', due to action a. An RL agent training involves recognizing an optimal policy function, ' < s. from a corpus of {(s, a.)) to maximize the long-term cumulative reward, Σ Ra. The reward function, Ra, is defined ab initio for an efficient goal accomplishment. The transition probability or state-action mapping is defined by the environment dynamics. In many real-life use cases, the agent cannot directly sense the effect of its actions on the environment. This particularly true when the state-action relationship cannot be modeled by either closed-form analytical expressions [26] 29 58) explicit rules in the popular games such as Chess [28], Go [47 46), and Atari [34). This challenge well documented in the literature [51 [7). To address this challenge for RL model training (52,33). simulation- based action
models 50) play a pivotal role. The optimal choice of simulation parameters such as the training
action space is non-trivial challenge because of the curse of dimensionality [17 non-linearity
and non-uniform action set [25).
Training data valuation 22 10 and associated artisanal software engineering efforts constitute large part of the machine learning (ML) life cycle (or MLOps). Yet, most research and development efforts (36) focus on algorithms and infrastructure. Production-grade MLOps needs to handle data lifecycle management (DLM) (40) challenges including: fairness and bias in labeled datasets [16), data quality (9. limitations of benchmarks [42), and reprodueibility concerns [39). For RL, the DLM challenges are further compounded due to complexities arising from non-linear state-action interactions, partially- observable processes, non-isometric action spaces (32). and strong domain specificity (2T) of action models. With the recent emphasis on ML explainability. traditional supervised learning and deep learning research communities are actively working on systematic data-driven frameworks [14] (3) for training data valuation. We need equivalent frameworks for RL to streamline conflict-prone training action selection 88
37 18 Depending on the agent-environmenn training actions have different relative contributions to the RL agent performance. Some training actions are indispensable because of their unique positions in the parametric space. Other dispensable actions have different relative contributions to the reward function. Remarkably, high-cardinality
interactions, different

---

Under review as a conference paper at ICLR 2022
Environment
S
A
A <- <--- π (S)
max
P
Z
Agent
R
Figure 1: The schematic diagram for a typical reinforcement learning algorithm
training action space in many cases leads to lower cumulative reward than a well-designed training action space. To the best of authors' knowledge, there is hardly any data-driven tool for the evaluation of training action space for RL. Such tool leads to superior RL agent performance, lower model training and maintenance cost, and strong multi-disciplinary collaboration 35
This paper proposes a shapley-inspired (54] algorithm to categorize and rank training action sets. also assists in recognizing cut-off cardinality for the training action space to reduce unnecessary exploration and ensure polynomial time complexity. While Section 2 describes the algorithms for RL training action space evaluation, Section 3 illustrates the effectiveness of the algorithms specific case study. Section 4 discusses the relevant work. Finally, Section presents summary with possible future directions.
ALGORITHM
The proposed framework provides a shapley-inspired methodology 49 to efficiently filter out unnecessary training actions and discover near-optimal action set. Figure shows the framework consists of two algorithms and how these two algorithms interact with each other to design a near- optimal RL model by training action space filtering and evaluation. The first algorithm computes cut- off cardinality for the training action space. The cut-off' cardinality is defined as the minimium number enable high-fidelity predictions within an acceptable
of action points needed in training action computational complexity and an eтror bound. The second algorithm takes action points only above the cut-off cardinality and categorize action points into two classes: {dispensablle indispensable and ranking dispensable training action points based on the corresponding cumulative rewards. Indispensable action points are absolute essential action points for the RL training to achieve the desired goal. On the other hand, dispensable action points non-essential action points that can be discarded. However, the RL agent might perform sub-optimally without disposable action point. By ranking disposable training action points based on the corresponding cumulative rewards, the relative contributions different training action points are estimated.
2.1 CUT-OFF CARDINALITY COMPUTATION FOR TRAINING ACTION POINTS
RL deals with compilation of quartet (S, A, Pa. RR) and computation of an optimal policy, " which maximizes the long-term cumulative reward. The search space for shapley-inspired technique needs to span across the power set for the training action space which has exponential complexity with training action points. To circumvent this problem, the proposed algorithm, discussed in Algorithm[[ [ uses Monte Carlo method to compute the cut-off cardinality. The inputs to this algorithm include RI. algorithm, the power set for the training action space, the corresponding state space,
2

---

Under review as a conference paper at ICLR 2022
Algorithm 2
Indispensable Action Points
Algorithm
Training Action Space
Cut-Off Cardinality Computation
Training Action Categorization
Optimal RL Model
Dispensable Action Point Ranking
Dispensable Action Points
Figure 2: The proposed training action selection framework for reinforcement learning
the transition probability, acceptable performance margin, and acceptable number of iterations. The output is the cut-off' cardinality. The algorithm uses an iterative procedure to train the RL agent with different numbers of training actions, starting from all available training actions only one training action. If for certain cardinality, all the cumulative rewards do not improve by within n iterations, then set the status failure, and assign the cut-off cardinality that cardinality plus one. The cut-off cardinality signifies computational efficiency a larger cut-off cadinality means lower computational overhead and vice versa.
Algorithm 1 Monte Carlo method for cut-off cardinality computation for the training action space
Input: The RL algorithm, R, the power set for the training action space, P(A), the corresponding state space, P(SIA) transition probability P, acceptable performance margin, e, and acceptable number of iterations, n.
Output: Cut-off cardinality, [Aleutof for k + |A| to do
repeat
x² t R, Ra) if the cumulative reward improves by with iterations then status success
else
status failure
end if
until all necessary training action sets for given cardinality is exhausted. all statuses for given cardinality, k; are failures then
A leutoff +- +1
end if
end for
2.2 CATEGORIZATION AND RANKING TRAINING ACTIONS
Algorithm 2 offers principled procedure for training action selection. As for inputs, it takes the combinations of training state-action pairs above the cut-off cardinality, determined by Algorithm [] the RL algorithm, the reward function, the threshold condition, and the acceptable number of iterations. As for outputs, it predicts a categorization vector which classifies training action points into two classes: (dispensable, indispensable) and ranks dispensable training actions based on the corresponding cumulative reward. At its core, Algorithm|21 determines whether the policy determined from the given acteon pairs achieves the threshold condition within the acceptable number of iterations. The algorithm uncovers the indispensability of some training action sets for a given RL task. A training action set is deemed to be indispensable: iff upon removal of that training action

---

Under review as a conference paper at ICLR 2022
point, the RL agent fails to accomplish the goal within finite number of iterations 24 56
23
All other action points are dispensable. The dispensable action points are rank listed in L based on the corresponding cumulative reward. Essentially, L informs the performance impact of different disposable action points on the RI. agent.
Algorithm 2 Data-driven categorization and ranking for training action space evaluation
Input: All combinations of training state-action pairs upto cut-off cardinality: {(s; a:) the RL algorithm, R. the reward function, the threshold condition, and the acceptable number of iterations. Output: Categorization vector, V, which classifies training action points into two classes: (dispens- able, indispensable). Rank order list of dispensable training actions based on the corresponding cumulative reward. repeat
for S4, a, do лt" < R(S, A, Pa. Ra)
if Threshold condition is never satisfied within the acceptable number of iterations then V(A a;) &- indispensable
else
V(A a:) + dispensable end if
end for
until all necessary training action sets are evaluated.
Rank List, L f- dispensable actions sorted in order of the corresponding cumulative rewards
2.3 ACTION SHAPLEY
The proposed framework adopts Action Shapley which introduces formulation for the problem of equitable training action valuation in reinforcement learning. Reinforcement learning has three key building blocks. The first building block is the training action space, A, the corresponding state space S, and a pre-assigned reward function, Rg The second building block is a reinforcement learning algorithm, R, which is treated as black box. It takes (S, A, P., R.,) and computes optimal policy function, π². The third building block is the performance measure or the cumulative sum of reward, > Rg. The goal of the framework is compute the valuation for each training action point, di A, R. > RR) as a function of three building blocks. A shapley technique is useful for action valuation because it satisfies nullity, symmetry, and linearity [45 From game theory, can be expressed as shown in Equation !
Φ C Σ (SU - Σ RR(SS) SCA-(6)
[S]
where, the sum is over all subsets of A not containing and C' is an arbitrary constant. We call é, the Action Shapley value of action ag. Equation suggests Action Shapley computation is with exponential time complexity w.r.t. the training action points. This exponential computational complexity warrants the need for the cut-off cardinality discussed in Algorithm I
CASE STUDY
In this section, we design a resource tuning example (in the cloud) to illustrate the effectiveness of the proposed algorithm for the training action space evaluation. We evaluate the performance of an MDP [20]-based RI. agent, as shown in Figure The state-action mapping and transition probability are modeled using time-series auto-regression (38] after PCA-based dimensionality reduction [41 with time complexity (klogk), where the number of principal components. The choice of the algorithms is purely driven by the nature of the training dataset. A more complex non-linear dataset warrants more complex sequential models such as long short-term memory (LSTM) 44 or attention
based models (30). For action updates, WLOG, an RL-based PID controller [1 to time-series modeling, action update can be conducted by other policy learning algorithms such as
[ used. Similar
SARSA 19
4

---

Under review as a conference paper at ICLR 2022
Table 1: Relevant case study for cloud resource tuning
RL Artifact
Description
State
CPU utilization metrics
State Statistics
Median value of CPU utilization
Threshold
90% of CPU utilization
Action
Resource configuration set points: (# of vCPUs, Memory Size (GB)
Reward
Negative total time steps required to satisfy the threshold condition Polygon defined by the parametric endpoints
Parametric Boundary
Iniiall Action
(6, 14): Arbitrarily assigned WLOG
Error Margin
5%
Acceptable Steps
400
Computational Complexity
Polynomial time
Table 2: Five different AWS EC2 resource pairs used in training action space
EC2 Type
of vCPUs
Memory Size (GB)
small 13a
2
2
medium 13a
2
large 13a
2
8
xlarge 13a
4
16
2xlarge 13a
8
32
As shown in Table [ the objective of the RL agent for this study is to quickly reduce high CPU utilization below a pre-assigned threshold for a given workload. In most infrastructure/cllud resource tuning technologies [55]. CPU utilization represents key metric. Therefore, the state space for this RL case study consists of virtual machine CPU utilization (%) metrics and the action space is defined by the VM resource set points, i.e., (# of vCPUs. Memory Size (GB)). The RL agent uses AWS boto3 SDK (2) to manipulate actions and AWS CloudWatch 33 for state space monitoring. The reward is defined as the number of time steps required by the agent to accomplish the objective multiplied by
-1 The negative reward per time step was meant to push the agent to accomplish the task as fast as possible.
The training data for this case study was generated internally 4 with open source library, stress (https://linux. (https:/linux.die.nell) www.iiieeemaa///stttttet the stress command: sudo stress -io 4 -vm 2 -vm-bytes 1024M -timeout 500s. Essentially, the peak running 4 I/O stressors and 2 VM workers spinning on malloc with 1024 MB per worker for 500 The simulated rectangular workload has time period of 600 high-stress phase of 500 is followed by an inactive phase of 100 s. The RL. training action space is spanned by the power set drawn from the five pairs of EC2 configuration we notice that the power set below the cut-off cardinality of 4 produces trivial and unstable results. Therefore, WLOG, the analysis in this paper has been focused on six training action sets as shown in T That amounts to 81 11.25% reduction in the search space. For each EC2 instance in the training action space, the corresponding state metries, i.e., CPU utilization (%) are shown in Figure The training data was collected for 24 hour period with 1 minute sampling interval. Using Algorithm ??, the optimal sizp for action update is identified to be 0.1 both # of vCPUs and Memory Size (GB) dimensions.
It uses a rectangular workload. The peak of the workload uses
points as shown in Table Using Algorithm [
With this set up. different RL models are developed with different training action sets and the corresponding rewards and ranks are noted in Table Remarkably, high cardinality training action set does not guarantee the best reward: the agent with all training actions, <small 13a, medium 13a, large 13a, xlarge 13a, 2xlarge 13a>, does not yield the highest reward. In fact. the action set with <medium t3a, large t3a, xlarge t3a, 2xlarge 13a> yields the highest reward. This pattern could be attributed to the state-action interaction in this particular case study. First, the parametric distances
5

---

Under review as a conference paper at ICLR 2022
Table 3: Training action categorization based on the valuation vector
Training Action
Category
small 13a
dispensable
medium 13a
dispensable
large 13a
indispensable
xlarge 13a 2xlarge 13a
indispensable
indispensable
Table 4: Rewards and ranks for different training actions. Some training action sets fail satisfy the objective. Therefore, the rewards and ranks for them are noted as none
Training Action Set
Reward
Rank
<mmall 13a, medium t3a, large 13a, xlarge 13a, 2xlarge t3a>
-21
3
<medium t3a, large 13a, xlarge 13a, 2xlarge 13a>
-13
1
<small 13a, large 13a, xlarge 13a, 2xlarge 13a>
-16
2
<small 13a, medium 13a, xlarge 13a, 2xlarge 13a>
none
none
<small 13a, medium 13a, large 13a, 2xlarge 13a>
none
none
<small 13a, medium t3a, large 13a, xlarge 13a>
none
none
between different EC2 instance pairs are not uniform. While the Euclidean distance between small 13 and medium 13a is equal to 2, that between xlarge 13a and 2xlarge 13a is 16.5. The non-uniform spacing for training action space is a considerable deterrent (31 for RL adoption. Second, in this case study. the transient CPU utilization (%) patterns have undergone a material change from xlarge 13a (max 100%) to 2xlarge 13a (max 73%). This indicates the strong influence of 2xlarge 13a for the given RL task. Indeed, we noticed 2xlarge 13a to be an indispensable training action. As shown in Table 3 categorization of training actions be inferred based on the valuation vector, V, as described in Algorithm 2] two dispensable training actions are uncovered to be small 13a, medium 13a and three indispensable training actions be large 13a, xlarge 13a, 2xlarge 13a.
Figure 4 shows the RL loop action with three training actions: <small 13a, medium 13a, large 13a, xlarge 13a, 2xlarge 13a>, <medium 13a, large 13a, xlarge 13a, 2xlarge Bax, and <small 13a, large 13a xlarge t3a, 2xlarge t3a>.
For the first training action set of <small 13a, medium 13a, large 13a, xlarge 13a, 2xlarge 13a>, the reward is 22. The left subplot in Figure [a) shows how the recommended action is evolving with time from an arbitrary initial point of (6, 14). The recommended points are superimposed on the training action parameter space to illustrate their relative position with respect to the parametric boundary which defined by the trapezium with vertices: ((2,2), (2,8), (8,32), (8,2)/ in the (# of vCPUs, Memory Size (GB)) space. The right subplot in Figure 4(a) shows how the median CPU utilization (%) comes below the 90% threshold in 21 steps leading to -21 in reward. The blue dots represent the median CPU utilizations for different training set points.
For the second training action set of <medium 13a, large 13a, xlarge 13a, 2xlarge 13a>, the reward is -13 as shown in Figure (b)
For the third training action set of <small 13a, large 13a, xlarge 13u, 2xlarge 13a>, the reward is 16 as shown in Figure Cc).
As shown in Table 4 the reward scores can indeed be used for ranking different training action sets leading to a data-driven approach for training action selection. As shown in Figure large 13a is an indispensable element in the training action space for the given RL agent. Without this training action, the RL agent fails to accomplish the goal of bringing the CPU utilization below the critical threshold. Similar observations can be made about xlarge 13a and 2xlarge 13a.

---

Under review as a conference paper at ICLR 2022
18g1
2003 00 00
2022 66 02 1159000-00
medium the CRU Unilzation (s)
Utiization
100
2023-00901 14:00/000 DOL00
2011-0042 155900 10.00
slarge tee CnU unitzotion es
Zxlarge CRU Uniteation
2023 01 18.00000
2021 69 02 009000-0000
Figure 3: CPU utilization (%) responses on five different EC2 instances (Table 2) from 2PM-UTC W1/2021-2PMMUUS 9/2/2021 minute granularity. This training data generated internally (4) The median CPU utilization values (%) are noted to be equal to (95%, 95.5%, 99.5%, 100%, 72.5%)
RELATED WORK
Shapley value was postulated in classic paper game theory [15] and influences the field of economics significantly [43]. Various shapley-inspired techniques have been applied to model diverse problems including voting 12]. resource allocation (48) and bargaining (27). Recent years saw increased application of shapley-inspired methodologies in machine learning feature importance evaluation and training data valuation [14] TO). To the best of our knowledge, Shapley value has not been used to quantify training action valuation in reinforcement learning context. The application of shapley-insping technique for reinforcement learning is challenging problem. First, the relationship between state-action pairs and transition probabilities are expensive model. Also, often the RL training action points are not uniformly positioned. Finally, we have purposefully focused on a small sample cloud infrastructure use case instead of cliched RL use cases (5). That because the problem of optimal action selection has relatively more expensive in the cloud infrastructure space where the state-action relationship is only partially observable.
CONCLUSION
This paper proposes a data-driven methodology for training action space evaluation for RL. The methodology offers principled framework for training action space categorization and ranking within a finite computational time. unleashes a strategy for superior model performance and lower modeling cost. Additionally, the proposed methodology is completely agnostic of use cases and machine learning algorithms. Therefore, it is general- purpose methodology extensible to different domains including distributed computing, network traffic control, healtheare, automatic locomotion, building management system, and industrial controls, and different machine learning algorithms such PCA, Autoencoder, ARIMA, LSTM, Transformer, PID) SARSA, DQN, and many others. For the next phase of the development for this data-agnostic methodology, we are planning to contribute general RL design library relevant open source projects 5
7

---

Under review as a conference paper at ICLR 2022
Median CPU Utilization (56) for Different Set Points
Different Set Points
100
Marrocy Siow (080
small
medium
large
2zlarge
Median CPU Utilization (9)) for Different Set Points
Different Set Points
100
Mamory Siza (GB)
65
70
medium
Zolenge
(b)
of VCPUs
Median CPU Utilization (%) Different Set Points
Different Set Points
100
25
Hermory Sam (Ca))
85
(c)
VCPUs
Figure 4: Examples of dispensable actions. RL loop with all training actions, <small 13a, medium
13a, large 13a, xlarge 13a, 2xlarge 13a>. The reward is noted to be 21. (b) RL loop with a training action set of <medium t3a, large 13a, xlarge 13a, 2xlarge 13a>. The reward is noted be -13. (c) RL loop with training action set of <small 13a, large 13a, xlarge 13a, 2xlarge 13a>. The reward is noted be 16. Both small 13a and medium 13a are noted to be dispensable actions.
Utilization
Different Points
100
Hemory
1.5
75
70
VCPUs
Figure 5: RL loop with <small 13a, medium 13a, xlarge 13a, 2xlarge 13a> action space. The agent could never accomplish the goal, therefore, large 13a is indispensable element in the training action space. Similarly, xlarge 13a and 2xlarge 13a are two indispensable elements in the training action space.
8

---

Under review as a conference paper at ICLR 2022
REFERENCES
[I]
https://wwy www com - un-us/innovations ht www.whteiaeeeeeeeeeeee pawesspapppaaaaee /06 pid
tleory--xxplaine..hha. [Online; accessed 30-September-202111
[2]
hctras//instannes..aaaagggg.gg [Online; accessed D0-Septemmbe-22221)
[3]
[Online, accessed 30-September-20211
[Online;
[4]
com wommrrgheee www.shgoohhh//ee ec2 x1 dataset
[Online; accessed 30-
September-20211.
[5]
[Online; accessed 30-Septeebeer-20211.
[6]
htttps://githus com http:////eeaaaaoooooe/raraa//eee
ray
[Online: accessed 30-eeptember--22021111
[7]
https://github www/kubeelwww//eeccccooo
[Online; accessed 30-Septemberr20211
[8]
James F Cavanagh et al. "Conflict acts as an implicit cost in reinforcement learning". In:
Nature communications 5.1 (2014), pp. 1-10.
[9] Kate Crawford and Trevor Paglen. Excavating ai. 2019.
[10] Daniel Fryer, Inga Strümke, and Hien Nguyen. "Shapley values for feature selection: the good, the bad, and the axioms". In: arXiv preprint arXiv:2102.109: (2021).
[11] Paul Garnier al. "A review on deep reinforcement learning for fluid mechanics". In: Com-
puters & Fluids 225 (2021), p. 104973.
[12] Andrew Gelman, Jonathan N Katz, and Joseph Bafumi. "Standard voting power indexes do not work: an empirical analysis". British Journal of Political Science 34.4 (2004), pp. 657-674.
[13] Meysam Gheisarnejad and Mohammad Hassan Khooban. "An intelligent non-integer PID) controller-based deep reinforcement learning: Implementation and experimental results". In: IEEE Transactions on Industrial Electronics 68.4 (2020), 3609-3618.
[14] Amirata Ghorbani and James Zou. "Data shapley: Equitable valuation of data for machine learning". In: International Conference on Machine Leurning. PMI.R 2019, pp. 2242-2251. Donald Bruce Gillies. Some theorems on n-person games. Princeton University. 1953.
[15]
[16] Naman Goel and Boi Faltings. "Deep bayesian trust: A dominant and fair incentive mechanism for crowd". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 01. 2019, pp. 1996-2003.
[17] Jiequn Han, Arnulf Jentzen, and E Weinan. "Overcoming the curse of dimensionality: Solv- ing high-dimensional partial differential equations using deep learning". In: arXiv preprint arXiv: 777702256888 (2017), pp. 1-13.
[18] Yousuf Hashmy al. "Wide-area measurement system-based low frequency oscillation damp- ing control through reinforcement learning". . In: IEEE Transactions on Smart Grid 11.6 (2020), pp. 5072-5083.
[19] Fernando Bernandez-Garchi and Richard S Sutton. "Understanding multi-step deep reinforce- ment learning: systematic study of the DON target". In: arXiv preprint arXiv: (901: 00 (2019).
[20] Mark N Howell and Matt C Best. "On-line PID tuning for engine idle-speed control using continuous action reinforcement learning automata". Control Engineering Practice 8.2 (2000), pp. 147-154.
[21] Vladimir Ilievski al. "Goal-oriented chatbot dialog management bootstrapping with transfer learning". In: arXiv preprint arXiv: //XXvv/8002000 /802000500 (2018).
[22] Ruoxi Jia et al. "Towards efficient data valuation based on the shapley value". In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 1167-1176 [23] Nan Jiang and Alekh Agarwal. "Open problem: The dependence of sample complexity lower bounds on planning horizon".. In: Conference On Learning Theory. PMLR. 2018, pp. 3395- 3398.
[24] Nan Jiang et al. "Contextual decision processes with low Bellman rank are PAC-leamaale". In: International Conference on Machine Leurning. PMLR. 2017, pp. 1704-1713.
(25) Yujia Jin and Aaron Sidford. "Towards Tight Bounds on the Sample Complexity of Average- reward MDPs". In: arXiv preprint arXiv:2106.07046 (2021).

---

Under review as a conference paper at ICLR 2022
[26] Nate Kohl and Peter Stone. "Policy gradient reinforcement learning for fast quadrupedal loco- motion". In: IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004. Vol. 3. IEEE. 2004, pp. 2619-2624,
[27] David A Kravitz and John Iwaniszek. "Number of coalitions and resources as sources of power in coalition bargaining." In: Journal of Personality and Social Psychology 47.3 (1984), p. 534.
[28] Matthew Lai. "Giraffe: Using deep reinforcement learning to play chess". In: arXiv preprint 0rXiv:1509.01544 (2015).
[29] Jacky Liang et al. "GPU-accelerated robotic simulation for distributed reinforcement learning". In: Conference on Robot Learning. PMLR. 2018, pp. 270-282.
[30] Yuxuan Liang et al. "Geoman: Multi-level attention networks for geo-sensory time series prediction." In: IJCAI. Vol. 2018. 2018, pp. 3428-3434.
[31] Sandeep Manjanna, Herke van Hoof, and Gregory Dudek. "Reinforcement learning with non- uniform state representations for adaptive search". In: 2018 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR). IEEE. 2018, pp. 1-7.
[32] Riccardo Marin et al. "Correspondence learning via linearly-ivvarinnt embedding". In: (2020).
[33] Volodymyr Mnih et al. "Human-level control through deep reinforcement learning". Inc nature
518.7540 (2015), pp- 529-533.
[34] Volodymyr Mnih al. "Playing atari with deep reinforcement learning". In: arXiv preprint arXiv: (2013).
[35] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. " "Agnostic federated learning". In: International Conference on Machine Learning. PMLR. 2019, pp. 4615-4625.
[36] Christoph Molnar, Giuseppe Casalicchio, and Bernd Bischl. "Interpretable machine learning-a brief history, state-of-the-an and challenges". In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer. 2020, pp. 417-431.
[37] Blažej Osiński al. "Simulation- reinforcement learning for real-world autonomous driving". In: 2020 IEEE International Conference on Robotics and Automation (ICRA). IEEE 2020, pp. 6411-6418
[38]
Charles W Ostrom. Time series analysis: Regression techniques. 9. Sage, 1990.
[39] Joelle Pineau et al. "Improving Reproducibility in Machine Learning Research". In: Journal of
Machine Learning Research 22 (2021). pp. 1-20.
[40] Neoklis Polyzotis et al. "Data lifecycle challenges in production machine learning: a survey".
In: ACM SIGMOD Record 47.2 (2018), pp. 17-28.
[41] Vikas Raunak, Vivek Gupta, and Florian Metze. "Effective dimensionality reduction for word embeddings". In: Proceedings of the 4th Workshop on Representation Learning for NLP (RepL4NLP-2019) 2019, pp. 235-243.
[42] Roberta Rocca and Tal Yarkoni. "Putting psychology to the test: Rethinking model evaluation through benchmarking and prediction". In: (2020).
[43] Alvin E Roth. The Shupley value: essays in honor of Lloyd S. Shupley. Cambridge University Press, 1988.
[44] Alaa Sagheer and Mostafa Kotb. "Time series forecasting of petroleum production using deep LSTM recurrent networks". In: Neurocomputing 323 (2019), pp. 203-213,
[45] Anthony F Shorrocks. Decomposition procedures for distributional analysis: a unified frame- work based on the Shupley value. Tech. rep. mimeo, University of Essex, 1999.
[46] David Silver et al. "Mastering the game of Go with deep neural networks and tree search". In: nature 529.7587 (2016), pp. 484-489.
[47] Satinder Singh, Andy Okun, and Andrew Jackson. "Leearnig to play Go from scratch". In: Nature 550.7676 (2017), pp. 336-337.
[48] Peibing Song et al. 'Comprehensive Benefit Allocation for Joint Operation of Multiple Reser- voirs in the Ningbo Based on Shapely- Value Method and Benefit-Incremental Method". In: MATEC Web of Conferences. Vol. 246. EDP Sciences. 2018, p. 01080.
[49] Mukund Sundararajan and Amir Najmi. "The many Shapley values for model explanation". In: International Conference on Machine Learning. PMLR. 2020, pp. 9269-9278.
[50] Richard S Sutton. "Dyna, an integrated architecture for learning, planning, and reacting". In: ACM Sigart Bulletin 2.4 (1991), pp. 160-163.
10

---

Under review as a conference paper at ICLR 2022
[51] Sebastian Thrun and Anton Schwartz. "Issues in using function approximation for reinforce- ment learning". In: Proceedings of the Fourth Connectionist Models Summer School. Hillsdale, NJ. 1993, pp. 255-263.
[52] Hado Van Hasselt. "Reinforcement learning in continuous state and action spaces". In: Rein- forcement learning. Springer, 2012, pp. 207-251.
[53] Hilde JP Weerts, Werner Ipenburg, and Mykola Pechenizkiy. "A human-grounden evalua- tion of shap for alert processing". In: arXiv preprint urXiv:1907.033 (2019).
[54] Eyal Winter. "The shapley value". In: Handbook of game theory with economic applications (2002). pp. 2025-2054.
[55] Yu Zhang, Jianguo Yao, and Haibing Guan. "Intelligent cloud resource management with deep reinforcement learning". In: JEEE Cloud Computing 4.6 (2017), pp. 60-69.
[56] Dongruo Zhou, Jiafan He, and Quanquan Gu. "Provably efficient reinforcement learning for discounted mdps with feature mapping". In: International Conference on Machine Learning.
PMLR. 2021, pp. 12793-12802.
[57] Hao Zhu al. "Deep reinforcement learning for mobile edge caching: Review, new features, and open issues". In: IEEE Network 32.6 (2018), pp. 50-57.
(58) Henry Zhu al. "Dexterous manipulation with deep reinforcement learning: Efficient, general, and low-cost". In: 2019 International Conference on Robotics and Automation (ICRA). IEEE.
2019, pp. 3651-3657.
NOTATION
S
Space Space
A
Action Space
Pa
Transition Probability
R
Reward Signal
P
Power Set
Policy
Optimal Policy
T
Optimal Policy
Categorization Vector
Rank List of Dispensable Actions


Reviews:
[{"review_id": "uCDdvDeQOnA", "reviewer": "Reviewer_5emL", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "While understanding the impact of training action space is certainly a valid and important problem, the investigation of this topic is far from satisfactory in the paper.\n\nFirst, the design of the new algorithm is mainly presented in the pseudo-code form without further explanation. It is not easy to follow the new algorithm design and understand why the new algorithm can address the optimal training action selection problem. The authors mentioned that their algorithm is shapely-inspired. However, there is no further discussion regarding how this idea is actually utilized in the algorithm design and why the new algorithm is novel.\n\nSecond, many key concepts explored in the paper are not well defined. For example, it is quite confusing to me what the dispensable action set and indispensable action set truly mean. The corresponding discussion in the paper is brief. The authors also stated that \"the possible action space grows exponentially with the number of training actions\". I can hardly understand why the action space grows exponentially with the number of actions. This does not make any sense.\n\nThird, I am not sure why the authors choose to evaluate their methods on a specific case study related to cloud computing. Why is this case study particularly important for understanding the impact of training action space on reinforcement learning performance? Why didn't the authors consider some of the most commonly used benchmark reinforcement learning problems?\n\nFinally, the experiment results are quite limited and flawed. No solid conclusions can be derived from the experiment results. Hence the overall technical contributions of this paper are highly questionable. The clarity and quality of this paper should also be substantially improved.", "summary_of_the_paper": "This paper empirically considered the impact of training action space for reinforcement learning in a case study. Understanding the impact of training action space is a valid and important problem. An empirical study of this problem appears to be the main contribution of this paper.", "summary_of_the_review": "This paper has major weakness in several aspects, including both the algorithm design and experimental analysis. The paper is not ready for publication with its current shape.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "njqBggY3Nnz", "reviewer": "Reviewer_TWbe", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "My understanding of the problem is such that it is tried to learn from data (rather than domain experts) which actions can be neglected for the design of the RL agent, i.e. a form of fixed action masking is learned. This can reduce the complexity of the agent and it can allow to remove undesired actions for probabilistic or online learning scenarios.\n\nThe contribution of the paper is the used of a monte carlo method to find the size of the action set, which is claimed as a Shapely-inspired algorithm, which is correctly spelled Shapley. Besides this mentioning of the Shapley inspiration there is no strong link or motivation for this connection.\n\nRegarding the case study, I'm not sure we are actually solving a MDP here, the problem could similarly be addressed by a contextual bandit, if I understand it correctly. I'm also wondering what the incentive is to not always select the highest configuration, which should reduce the CPU utilization most and as costs seem not to be considered.\n\nThe paper is also missing a comparison with other techniques as baselines and a more thorough evaluation than the small case study experiment shown.\n\nFinally, I found the writing style of the paper to be very hard to follow and confusing at times. The algorithms should be introduced more clearly in the text and there should be a focus on the novel contribution and its intuition, as well as some formal justification and analysis of the method.", "summary_of_the_paper": "The paper addresses the problem of action set selection, i.e. identifying which actions should be available to a RL agent, during training. The set of available actions can influence the RL agent's performance or even hinder it to reach its goal.\nA method to evaluate action sets is introduced and a case study is performed on a resource tuning example on cloud infrastructure.", "summary_of_the_review": "The paper is confusing at some points and the actual contribution is only small.\nThere is no theoretical justification of the method.\nThe experimental evaluation has some shortcomings.\nThe paper is not ready to be published and needs a thorough revision.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "DyEo8Kv-Nnv", "reviewer": "Reviewer_LXKk", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper solves an interesting and challenging problem in RL space that can have significant impact in overcoming one of the major challenges in RL which is to identify the optimal action space. The set of proposed algorithms provides a principled method to efficiently filter out unnecessary actions and discover a near optimal action set. Having said that I think paper in its current format is very hard to follow. The presentation needs to be improved significantly. It is challenging to understand the core of the technical contributions without a proper explanation. Algorithm 1-3 are explained in few sentences only. The list of unexplained variables or statements is exhaustive. To give a few examples: how state update function F is defined in algorithm 1? How the error margin and computational complexity is computed from state update function in algorithm 2? What is $a_i, b_i, c_i$ (note that c is used twice in same equation with different context) in algorithm 3? The empirical evaluation is performed in a real-world but new test environment. It does suggest a set of action recommendations with their cumulative reward value, but how to evaluate the performance of such actions in an RL setting is not clear to me. I also had a hard time in understanding Figure 3 and 4.  ", "summary_of_the_paper": "The paper proposed a data-driven method for optimal action space selection in a reinforcement learning problem. Given a set of training state, action pair, the proposed approach first filters out the set of indispensable action set and then rank the other action set according to their cumulative reward values. To further improve the efficiency, a Monte Carlo sampling method is proposed for cut-off cardinality computation for action space. An action update rule is devised by computing optimal step size. Finally, a case study on a cloud environment is illustrated to select the optimal set of resources (#vCPUs and Memory size) to optimize the CPU utilization rate. The case study demonstrates that the Monte Carlo sampling based algorithm reduces action search space by 81% and then it creates a list of ranked action set. It is shown that a large action space does not necessarily lead to better performance for an RL agent. ", "summary_of_the_review": "The key idea of the paper is very interesting. Access to a data-driven methodology for selecting near-optimal action set in a generic and principled way would be very helpful in developing an RL based solution for a real-world challenging problem. However, I am afraid that the presentation of the paper is not up to mark at this moment; I failed to understand the key technical contributions and empirical evaluation methodology. Several important technical details and experimental settings are also missing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7N2ypB5hgr", "reviewer": "Reviewer_ASBS", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "While the paper is well motivated, the current state of this work is unsatisfactory. In fact, this paper appears to be severely incomplete (the manuscript is 7 pages long, with no dedicated related work section). \n\nFirstly, the method consists of 3 algorithms which are not thoroughly explained. Indeed, while the authors introduce the method with a good overview in Section 2, the technical discussion of the framework is lacking. For example, the authors say their method is “Shapely inspired”, yet they do not say why and in what sense. Although the algorithms appear simple and are provided in full with pseudo-code, they should be explained in detail in a Machine Learning paper.\n\nSecondly, the evaluation of the method is rather limited. The framework is evaluated on a single case study, where the dataset was generated internally on purpose for this work, i.e. the method was not evaluated on a standard benchmark already available to the community (besides, a GitHub link to such data is provided, which potentially breaks anonymity). The action space of such case study is also fairly limited, where the number of actions is 2: number of CPUS and RAM size in GB. While results show the method is effective, such evaluation hardly challenges the premise of the paper where complex and large action spaces are concerned. \n\nImportant results analysis is missing too. For example, what is the computational cost of the method? Since the aim of this work is to reduce action space search in order to achieve a better policy and save computing resources, the additional overhead of the framework should be assessed. This point is missing altogether.\n\nFinally, no other baselines are provided at all, thus it is impossible to properly judge the performance of the method. ", "summary_of_the_paper": "This paper focuses on Reinforcement Learning (RL). RL methods often entail a potentially large action space exploration to find a good policy. This work proposes a method to reduce such action space exploration. The method separates actions into two categories: dispensable (the action can be ignored) and indispensable (the action must be taken). Dispensable actions are also ranked according to their importance with respect to the final policy. The method is data driven and operates by looking at the global reward returns obtained when a certain action is removed from the action space. The method is evaluated on a case study simulating cloud infrastructure workload optimisation, i.e. the task of reducing high CPU utilisation by allocating more resources.", "summary_of_the_review": "This is an incomplete work. The method is not explained in detail and is not evaluated in a sufficient manner.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for finding the action space in reinforcement learning problems, characterizing the search space into dispensable and indispensable actions through a Monte Carlo approximation.

Reviewers are unanimous that the paper is not fit for publication at this stage. While it tackles an interesting problem and seems to be novel, the presentation leaves much to be desired; this area chair also had a hard time figuring out how the different parts of the paper fit together. Additionally, the use of a unique problem makes it hard to judge the contribution of the algorithm.
Decision: Reject