Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping

Since this work focuses on MDPs with large action spaces that exhibit group-wise similarity, so its application could be narrow. I am not sure when we need the proposed method. In which RL tasks do we specific need the proposed method to perform well?

We respectfully disagree with the statement that the MDPs that exhibit group-wise similarity are narrow. Our action group method is relevant in numerous practical settings. For instance, actions that correspond to proximate directions can be aggregated into a group in autonomous driving. Another example is congestion control in communication networks, where the actions that send the same (or similar) number of packets are placed in the same group. Further, note that for applications in which grouping functions are not explicitly given by domain knowledge, we can also employ supervised learning to learn the action groups. For example, we can use more easily accessible offline datasets to classify actions into multiple groups based on the similarity of transition kernels and rewards.

The current experiments are only conducted on toy tasks. So it's not unclear how would the proposed method perform in more complex tasks.

Thank you. We have now added an experiment under the downlink transmission scenario in Appendix F.1 to show the applicability of the grouping method when the action space is large ($A=10^5$). These simulations also illustrate that in scenarios where sampling and computational resources are abundant, a non-grouping framework might offer superior performance. However, in situations where such resources are constrained, our grouping framework demonstrates better efficiency and effectiveness.

Typos: "of each sate-group pair" ==> state.

Thanks for your comment. We have corrected this typo.

How would the proposed method perform when compared with other kinds of action abstraction methods?

We compare our methods with other action abstractions in the following. One well-researched action abstraction type is temporally related actions from an initial state and terminal state [1]. However, these are specifically targeting the temporally extended action trajectories instead of actions, therefore they are significantly different from our works.

Another line of action abstractions is about factored action space. [2] represents the action space as the binary sequence based on prior knowledge, and learns the value function related to each bit. [3] further uses deep RL to learn the compositional structure of discrete action space to learn better policies and value functions. There are also works that learn the action representations based on prior knowledge that is extracted from expert demonstrations [4]. Without using prior knowledge, [5] learns the underlying structure of actions. However, our work diverges from these methods on applications where domain knowledge of the RL task is available but not yet fully leveraged to effectively balance the complexity and performance loss. Our research targets these applications, demonstrating that an appropriately designed grouping function can effectively reduce complexity with minimal impact on performance.

[1] Riemer, M., Liu, M. and Tesauro, G., 2018. Learning abstract options. Advances in neural information processing systems, 31.

[2] Pazis, J. and Parr, R. Generalized value functions for large action sets. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pp. 1185– 1192, 2011.

[3] Sharma, S., Suresh, A., Ramesh, R. and Ravindran, B., 2017. Learning to factor policies and action-value functions: Factored action space representations for deep reinforcement learning. arXiv preprint arXiv:1705.07269.

[4] Tennenholtz, G. and Mannor, S., 2019, May. The natural language of actions. In International Conference on Machine Learning (pp. 6196-6205). PMLR.

[5] Chandak, Y., Theocharous, G., Kostas, J., Jordan, S. and Thomas, P., 2019, May. Learning action representations for reinforcement learning. In International conference on machine learning (pp. 941-950). PMLR.

There is no empirical demonstration of the practical viability of the practical method to estimate the performance-complexity trade-off. Since this is proposed as a "practical" approximation to the original joint optimization objective, it should be shown how this enables one to select a better action grouping strategy in an RL environment.

Thanks for your suggestion on the empirical demonstration of the proposed practical method. To address this, we applied the grouping selection method in the downlink transmission setting (See figure in Appendix F. 2). In this particular setting, solving the approximated optimization problem (P2) allows us to identify the most effective grouping function to balance the tradeoff between the sample complexity and performance loss. For instance, with a large sample size, the optimization process tends to select a more refined grouping function ($G=20$). On the other hand, in scenarios where the sample size is constrained, the method gives a coaster grouping function.

Extension to practical domains: How do the insights and theorems built on tabular value and policy iteration apply to deep RL? This is an important concern because, at the scale of large action spaces, such as those involved in recommender systems, deep RL is the only viable solution.

There are scenarios where deep RL is not an appropriate tool for solving problems. Deep RL uses samples to simultaneously learn the relationships between state-action pairs and a good policy. However, when the domain knowledge of the RL task is given, how to use domain knowledge to reduce the sample complexity is not known in deep RL. We target these applications and show that the grouping function can effectively reduce the complexity while inducing little performance loss.

Our methodology is quite general. So, we could use domain knowledge and apply action grouping as the preprocessing step to reduce the dimensionality of the action space, thus making deep neural network training more feasible and efficient. Thank you for the suggestion, this is a good problem to investigate further as a future direction.

If doing the action abstraction online with RL, how important is the concern about the sample and computational complexity of estimating the abstractions? Wouldn't the sample efficiency be subsumed within the sample complexity of RL itself?

We agree that the sample efficiency could be dominated by RL algorithms instead of estimating the abstractions. But note that our solution is indeed focused on reducing the complexity of the RL itself. Our framework is built upon the assumption that action grouping functions are predetermined based on specific domain knowledge. This allows us to concentrate on the efficiency and performance of the RL algorithms, rather than the complexities involved in estimating these abstractions. In Theorem 1, we investigated the performance degradation caused by limited samples as well as action grouping. Also, the proposed grouping-selection method in Section 5 also aims to balance the performance degradation and computational/sample complexity.

If the groupings are learned, how can the lower-level policy be feasibly obtained using domain knowledge? With the group compositions potentially changing non-stationary, the lower level policy might itself be very challenging to learn or provide with domain knowledge.

Note that from Theorem 1, we show that when actions in the same group are similar, the approximation error is small. Hence, when the transition kernel and rewards within a group are closely aligned, variations in lower-level policies do not significantly impact overall performance.

Our current focus on utilizing a domain knowledge-based grouping function is an initial step in our research. The exploration of learning the lower-level policy, particularly in dynamic MDP environments, can be an exciting direction for future work.

In section 3.1 it is not explained if the state space and action are discrete, finite or bounded. Because of that is also unclear if |g| defined in section 3.2 can be infinite.

Thanks for pointing out the need for clarity in Section 3.1. We confirm that in our current framework, both the state and action spaces are assumed to be discrete and finite. This assumption aligns with our grouped model, where $|g|$, the size of each action group, is also considered as a discrete and finite function. We have revised the paper accordingly.

We also acknowledge the potential of extending our model to continuous action spaces. In such scenarios, we propose to utilize domain knowledge to segment the continuous action space into multiple discrete and finite groups. This adaptation would allow us to apply our current algorithms to the lifted MDP, effectively reducing the sample complexity inherent in continuous action space.

It would also be helpful to properly define the input of $\mathbb{P}_1$ and $\mathbb{P}_2$ to highlight that one applies to the original action space and the other applies to the lifted action space.

Thank you for your suggestions on definitions of $\mathbb{P}_1$ and $\mathbb{P}_2$. $\mathbb{P}_1:\mathcal{S}\times \mathcal{G}\rightarrow \mathcal{S}$ is the transition probability from the state and group pair belonging to the state space and the lifted actions space to the next state. $\mathbb{P}_2:\mathcal{S}\times \mathcal{A}\rightarrow \mathcal{S}$ is the transition probability from the state and action pair belonging to the state space and the primitive actions space to the next state. We have revised the paper accordingly.

How is K defined in section 3.3? I don't understand the notation used.

$K$ is the number of samples to evaluate the transition kernel of all state-group pairs. Essentially, $K$ can be regarded as the total required samples for estimating the lifted MDP.

My big issue with this paper is that I do not understand how Algorithm 1 can lead to an almost optimal policy. It seems like an exploration term is missing to ensure good coverage of the action/state space. Right now the algorithm could be stuck in a local minima while being able to model the lifted MDP accurately. Please let me know if I missed something.

Note that once we have modeled the lifted MDP accurately, we do not need to use exploration. We can simply use value iteration to converge to the nearly optimal solution (which is exactly what Algorithm 1 does). Our approach of grouping provides a tradeoff between sub-optimality and complexity. The sub-optimality occurs because of (i) grouping, (ii) the estimation error of the lifted MDP, and (iii) the algorithmic error. For the approximation error caused by grouping, we show that when actions in the same group have similar transition probability and rewards (i.e., $\beta_P$ and $\beta_R$ are small), the performance loss due to different lower-level policies within groups is small. The estimation error of the lifted MDP is only proportional to the group size and inversely proportional to the number of samples. The algorithmic error decreases exponentially w.r.t. the iteration number.

The paper can be improved (and the reviewer is happy to raise the score if these points are met) if the authors would provide some empirical results. It is yet not apparent if the ideas of the presented approach ramifies in practical advances. As applications, the authors already mention control systems with potentially millions of actions available at each step or recommender systems with large number of potential items. Another possibility would be to test on muscular systems [1], since action space grouping would be quite effective for tasks involving such systems.

We conducted an experiment under the wireless transmission system with a larger action space. We set $S=5$, $A=10^5$, and the number of groups is $G=10$. As shown in the figure in Appendix F.1, when the number of samples is limited, the grouping-based algorithm performs significantly better than the non-grouping method, while the computational complexity is greatly reduced. This simulation implies that the grouping method is applicable to a practical setting with a large action space.

Our approach lends itself to many practical applications, especially in scenarios where the groups can be constructed such that the number of groups is much smaller than the number of actions. The focus of this paper is to solve the problem given a set of groups. However, the framework can be extended to the case when the groups themselves need to be determined by leveraging domain knowledge and empirical works in this area. In this case, we can construct an initial rough grouping function based on domain knowledge, and iteratively update the lower-level policy and grouping function to learn a refined grouping function under acceptable complexity. This is an interesting direction in the future.

In general, it would also help to understand the ramifications of the assumptions of this paper for potential applications. Can this method solve all possible RL tasks, or is a set of tasks excluded? In the paper, the authors write: “We specifically focus on MDPs with large action spaces that exhibit group-wise similarity, where only approximate grouping strategies of the action space are available”. Which particular tasks are meant in this sentence?

Assumption 1 requires the rewards to be bounded, which is a commonly used assumption and is satisfied in a broad set of practical settings. Assumption 2 requires the utility function to be monotonically decreasing with all variables. These assumptions are reasonable because we prefer the grouping function that causes lower performance loss and lower sample/computational complexity. Assumption 3 requires the utility function to be Lipschitz continuous with respect to the first variable, that is the utility function changes slightly when the performance loss changes.

We can apply this work to applications as long as we can divide actions into multiple groups where actions within the same group exhibit similar transition probabilities and rewards, as indicated by small values of $\beta_P$ and $\beta_R$ in Eqs. (1) and (2). To illustrate, consider the congestion control of wireless access systems [1]. Here all actions that send the same number of packets are in the same group. Additionally, in downlink transmission scenarios where the base station sends packets to multiple users, actions can be grouped based on users' characteristics. In such settings, actions that involve sending packets to users with similar profiles can be considered as parts of the same group.

We admit there are some tasks for which the action grouping is not applicable. For example, when all actions are distinctly different, it is impossible to find a valid grouping function that can reduce the “effective” action space without inducing significant performance loss.

[1] Ghaffari, Ali. "Congestion control mechanisms in wireless sensor networks: A survey." Journal of network and computer applications 52 (2015): 101-115.