Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping
Authors: Yining Li
Peizhong Ju
Ness Shroff
Venue: ICLR 2024 poster (2024)
Keywords: reinforcement learning
abstraction
Primary area: reinforcement learning

Abstract: Reinforcement learning often needs to deal with the exponential growth of states and actions when exploring optimal control in high-dimensional spaces (often known as the curse of dimensionality). In this work, we address this issue by learning the inherent structure of action-wise similar MDP to appropriately balance the performance degradation versus sample/computational complexity.  In particular, we partition the action spaces into multiple groups based on the similarity in transition distribution and reward function, and build a linear decomposition model to capture the difference between the intra-group transition kernel and the intra-group rewards. Both our theoretical analysis and experiments reveal a *surprising and counter-intuitive result*: while a more refined grouping strategy can reduce the approximation error caused by treating actions in the same group as identical, it also leads to increased estimation error when the size of samples or the computation resources is limited. This finding highlights the grouping strategy as a new degree of freedom that can be optimized to minimize the overall performance loss. To address this issue, we formulate a general optimization problem for determining the optimal grouping strategy, which strikes a balance between performance loss and sample/computational complexity. We further propose a computationally efficient method for selecting a nearly-optimal grouping strategy, which maintains its computational complexity independent of the size of the action space.

Published as a conference paper at ICLR 2024
ACHIEVING SAMPLE AND COMPUTATIONAL EFFICIENT REINFORCEMENT LEARNING BY ACTION SPACE RE-
DUCTION VIA GROUPING
Yining Li ", Peizhong Ju ,& Ness Shroff'
"Deparmment of Electrical and Computer Engineering
"Deparmment of Computer Science and Engineering The Ohio State University Columbus, OH 43210, USA
2ii.1232,, ju.171, shroff. 11 Bosu. edu
ABSTRACT
Reinforcement learning often needs deal with the exponential growth of states and actions when exploring optimal control in high-dimensional spaces (often known the curse of dimensionalityy. In this work, we address this issue by learn- ing the inherent structure of action-wist similar MDP to appropriately balance the performance degradation versus sample/computational complexity. In particular, partition the action spaces into multiple groups based on the similarity in transi- tion distribution and reward function, and build a linear decomposition model to capture the difference between the intra-group transition kernel and the mntra-group rewards. Both our theoretical analysis and experiments reveal a surprising and reduce the
counter-intuitive result: while more refined grouping strategy approximation error caused by treating actions in the same group as identical, it also leads to increased estimation error when the size of samples the computation resources is limited. This finding highlights the grouping strategy as new degree freedom that can be optimized to minimize the overall performance loss. To address this issue, we formulate general optimization problem for determining the optimal grouping strategy, which strikes balance between performance loss and sample/computationaa complexity. We further propose computationally effi- cient method for selecting a nearly-optimal grouping strategy, which maintains its computational complexity independent of the size of the action space.
INTRODUCTION
Reinforcement learning (RL), a field dedicated to finding the optimal policy that maximizes the long-term return through interactions with the environment, suffers from "the curse of dimensional- ity" (Barto and Mahadevan, 2003). In other words, in high-dimensional scenarios, the state-action space of RL grows exponentially with the number of degrees of freedom. For instance, in con- trol system, there could be millions of potential actions available at each step. Similarly, within large system, a recommender system might have consider millions of items (Dulac-Arold et al., 2015). This exponential growth poses significant complexity barrier to discovering optimal policies, especially in large-scale systems (Azar al., 2012; Agarwal al., 2020b).
To overcome the challenges associated with the explosion of the state-action space. a common approach use a low-rank representation of the Markov Decision Process (MDP). low-rank MDP settings that allow for polynomial sample complexity relative to the horizon length and feature dimension, some works investigate simultaneous learning of representations and the optimal policy (Agarwal et al., 2020a; Modi et al., 2020). However, the existing literature often assumes the attainability of an exact low-rank representation of the state-action space, wherein the representation accurately reflects the MDP's characteristics. In practical scenarios, low-rank structures often corrupted by noise, but the literature does not consider the errors resulting from the mismatch between the low-rank representation and the MDP itself.

---

Published as a conference paper at ICLR 2024
In order to address the aforementioned limitations, researchers have explored the of abstractions, which involves learning the di-eeemnsional latent state/action space that throws away some irrelevant state/action features. Previous literature has investigated various similarity metrics to identify suitable abstractions aligned with the original MDP, such as model similarity (Jiang et al., 2015; Gelada et al., 2019) and the similarity of the optimal value function (Abel al., 2016; 2020). Some studies have investigated the performance degradation resulting from inaccurate abstractions (Abel et al., 2020). To our knowledge, existing literature does not address the both sample complexity and computational complexity associated with estimating abstractions.
Our work falls within the realm of learning abstractions preserve the performance of the optimal policy. 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. Leveraging abstractions of the underlying MDP offers the advantage of reduced complexity, albeit at the cost of worse performance due to the approximation. This raises fundamental question: How does the trade-off between complexity reduction benefits and performance loss manifest in the context of an MDP and its corresponding grouping strategy?
Interestingly, our analysis yields counter-intuitive result: while finer grouping stralegy minimizes model approximation errors, the utilization of sample-based estimation also contributes to the performance shortfall, especially when faced with limited samples and computational resources. This further prompts the question of how to select a grouping strategy that strikes a balance between approximation error and estimation error to minimize the performance loss.
Our main contributions are as follows.
We propose an action-grouping method that clusters actions based on the similarity between intra-groo group transition kernels and rewards. This grouping approach allows to effectively reduce the size of the action space. Furthermore, we ensure that the performance degradation remains within acceptable bounds by carefully selecting the grouping strategy.
We analyze the performance loss, taking into account both approximation errors caused by information loss of grouping and estimation errors caused by limited sampling and computational resources. We compare our result with a known lower bound on the estimation error to show that it is tight. We then provide an example for which the approximation error is also relatively tight. We further give some insights into understanding the relationship between the grouping function and performance loss.
We build general optimization problem over the grouping function, sample size, and iteration number, enabling us to achieve a balance between performance degradation and sumple/computationaal complexity. The complexity of finding the optimal grouping is proportional to the number of feasible groups.
RELATED WORK
To avoid the curse of dimensionality in tabular MDP, there have been several works on learning and exploring the inherent structure of large MDP.
Representation Learning in Low-rank MDP One line of work is to consider reducing sample efficiency by exploring MDP structures. Several studies have explored the sufficient and necessary conditions for learning nearly-optimal policies with polynomial sample efficiency, relative to the horizon length and feature dimension (Jiang et al., 2017; Sun et al., 2019; Du et al., 2021: Weisz et al., 2021). In MDP settings that allow for polynomial sample complexity. such as low Bellman rank (Jiang et al., 2017; Wang et al., 2021; Ayoub et al., 2020: Zhou al., 2021; Du et al., 2019; Agarwal et al., 2020a), low witness rank (Sun et al., 2019), and bilinear structure (Du et al., 2021), some works assume that the agent possesses knowledge of a low-rank representation and focus on exploration algorithms (Jiang et al., 2017; Wang et al., 2021: Li et al., 2023). A more practical approach is to MDPs through rich observations (Du et al.,
learn a good latent representation of apecially-structure 2019; Agarwal et al., 2020a; Modi et al., 2020; Uchara al., 2021; Zhang et al., 2022). However, the above- mentionnd feature selection algorithms are based on the realizability assumption, which assumes there exists an exact mapping function from the latent state space to observations. In contrast,
2

---

Published as a conference paper at ICLR 2024
setting does not assume that this exact mapping exists, and we allow optimizing the grouping function which belongs to the given feasible set.
State/action Abstractions Another line of work learns abstractions, which do not hold assumptions on the specific structures of latent state/action space. The abstractions can be categorized into state, action, and joint state/action abstractions. For the state abstractions, Li et al. (2006) build uniform model of state abstraction to preserve enough information to find good policies. It generalizes different types of state abstractions, such as bisimulation (Givan al., 2003), and homomorphisms (Ravindran and Barto, 2002). Ravindran and Barto (2004) emphasize the performance loss by the MDP approxi- mation. et al. (2006) also provide the convergence performance of the resulting abstract policy in the ground MDP. Abel et al. (2016) further investigate the performance guarantee of approximate state abstractions which treats ncarly-identical states as equivalent. Several algorithms have been proposed to select good state abstraction from a given set of feasible abstractions (Jiang et al., 2015; Ortner et al., 2019).
A well-researched action abstraction type is options which are temporally related actions from an initial state and terminal state (Sutton et al., 1999). A trend of joint state-action abstraction is the hierarchical abstraction design, in which higher-level policies communicate between goals (subspace of state spaces) and lower-level policies aim to achieve goals from initial states (Nachum et al., 2019; Abel al., 2020; Jothimurugan et al., 2021). Specifically, Abel al. (2020) learns the performance loss associated by pairing the options with state abstractions and presents the sufficient and necessary conditions for options preserve information for nearly-optimal policy. There are also works on learning latent state space models end-to-end using neural networks (Hafner et al., 2019; Ha and Schmidhuber, 2018; Gelada al., 2019).
However, previous literature on abstraction learning primarily focuses on the performance loss resulting from approximate abstractions, while ignoring the complexity including both sample complexity and computational complexity. In our work, we address this gap by considering both the performance loss and the sample/computational complexity when determining the optimal grouping function.
3
SYSTEM MODEL
3.1 MDP PRELIMINARIES
This paper focuses on infinite-horizon discounted Markov Decision Processes (MDP) M := AS P. R, 7). Both S and A are discrete and finite. Here, S and A represent the state and action space, with sizes denoted as S and A, respectively. F S A + ((S) is the transition kernel, where ((S) is the collection of probability distributions over state space S. IP(s' [s, a) represents the probability of transiting to state s' when the agent plays action a at state 8. R(s, a) is the instant reward with state-action pair being (s, a). We have the following assumption on the rewards, which is commonly used in RL (Antos et al., 2008; Wang et al., 2021).
Assumption (Bounded rewards) Assume that the reward satisfies S R(s, a) S 1 for any state-action pair (s, a).
The policy on M is defined as a mapping from S to the probability distributions over the action space, i.e., S - ((A). Let (M, a) and (s) denote the value function based on the policy from the initial state-action pair (s, a) and 8, respectively. There exists an optimal policy TM that maximizes the value function simultaneously for each state, and the state-action value function based on policy TM is the fixed point of the Bellman optimality operator (Puterman, 2014). For notational simplicity, we write the value function based on the optimal policy as QiM and Va in the following.
3.2 ACTION GROUPING
To capture the similarity characteristics, we assume actions can be classified into multiple groups based on prior knowledge of M. By grouping the actions, we are able to find the nearly-optimal policy over peduced-dimensee Define the surjective mapping function g A + G, where g(a) g(a') for any actions a and a' in the same group. The set of actions that belong to group h is denoted An. Define [g] [ as
state-action space, which significantly reduces the complexity.
3

---

as Published as a conference paper at ICLR 2024
the number of groups mapped by the grouping function g, and D as the set of all feasible grouping functions.
For each step, we consider a combined policy, where the higher-level policy n² S + S2(G) selects the group and the lower-level policy x (-|ss h)) S x h + ((A,), h E 9 selects an action belonging to that group. The joint policy is composed of the higher- and lower-level policies, denoted as TG = π T²| The lower-level policy can be obtained using domain knowledge. In the case where actions within the same group exhibit similar transition kernels and reward functions, we can also employ the uniform distribution as the lower-level policy.
To assess the effectiveness of the grouping operation, we introduce linear decomposition model that quantifies the similarity between actions within the same group based on their transition kernels and rewards. This model allows us to evaluate the extent of the performance degradation, which will be thoroughly discussed in the following sections.
Grouped transition probability
Define the linear decomposition of PP by the tuple (3p, Pi, IP2)
PPs' a)
a) (1- p1-8p(s a) P) (s g(a)) +
(1)
where Bp S x A 10, PI x g S is the transition probability from the state and group
pair belonging to the state space and the group space to the next state, and P2 S x A + S is the transition probability from the state and action pair belonging the state space and the actions space to the next state. Any P has at least one linear decomposition solution (B,.P1, P2, of Eq. (1) since there exist naive linear decomposition solution (s, a) L, = 0, = P).. Define the probability deviation factor 3p == max,.a Br(s, a), thus 0 I Bp S 1.
Grouped rewards Similar to the transition probability distribution, we write actual rewards R(s, a) as the linear combination of < (1 < and S R2(s, a) S 1 with factor (s, a), which shown as
R(s, (1 Bx(s, Rs, g(a)) + Bn(s, R2)
8, a) and S 3R S 1. Rí can be viewed as the reward function corresponding to state-group space, and R2 represents the deviated reward function of the primitive state-action space.
Define the rewards deviation parameter as 3n == max g
Remark 1. (Obtaining D) Intuitively, actions that have similar transition probability distributions and reward functions can be clustered into the same group. We can expert knowledge of specific applications to obtain the feasible grouping function set 'D before the learning process. Note that do not make any assumptions DD e.g., do not need the finer grouping function to be the refinement of coarser grouping functions as in [Assumption 1, (Jiang et al., 2015)]-
Remark 2. (Calculation of P and P2)) P, is the common transition kernel for all actions in the same group, and P2 reflects each individual action's 's transition characteristics. We can get (IP 12)) by either directly solving Eq. (1) or ulilizing the domain knowledge. We provide an example of getting (I1,, P2) in the wireless access scenario in Appendix B.
Remark (Meaning of 3p and 3R) The deviation factors 3p and 3R reflect how well the common transition probability distribution and reward can represent each action's 's actual transition kernel and reward. If 3r and 3R are small, then the transition kernel and rewards of joint actions the same group are almost identical. Specifically, when Bp .n = 0, (((|s, a) IP1(-1s, g(a)) and R(s, a) = R2 (s, g(a)). When 3p = 1, (()ss. P2(- 8, a) and there is no common pattern for all actions in the same group.
3.3 MODEL-BASED RL WITH GENERATIVE MODEL
The model-based dynamic programming algorithm with the generative model is shown in Algo-
rithm 1. Assume we can access generative model that generates independent quadruples (s. h, r, s') following Mg. We generate K' quadruples for each state-group pair, where F Ro(s, h). 8 ~ (=) ht). The total sample complexity is K K". We can have an empirical estimation
AAssme f S A. S G. th h + An, and v Line- We define f = Φ iff f(ass) ((h))))x(aaa)..
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Model-based RL with generative model
1: Input: state value function initialization (8, h) = 0 for all 8 E S, h g.
2: Output: policy ,p..
3: for hs E S x 9 do
4: Draw sample (s, h, rh, 8/ s where RR(s, Pa(ls,,))
5: end for
6: Estimate PG and RG by Eq. (3).
7: Execute the dynamic programming algorithm for 7 iterations and generate the policy nt.-
of M as
(o(('(s,)) Ei count (s,, h')
K' Rc(s,h)= K' Erx(s,))
(3)
K'
We can construct an empirical MDP as Ma = (S, A, Pa. Ro: 7) by sampling over each state-group pair and use the oracle dynamic programming algorithms such value iteration and policy iteration to get a nearly-optimal policy under the estimated MDP.
Here we consider the sample and computational complexity induced by Algorithm 1. Sample complexity. denoted as Csamp, represents the number of samples needed to obtain the opar-ottimal policy. On the other hand, computational complexity denoted Coamp. refers to the computational operations required to achieve the same goal.
4 MAIN RESULTS ON PERFORMANCE EVALUATION
We now present the main theorem that establishes the upper bound on the performance gap between the optimal policy and the output policy of Algorithm 1. Let TG. = T. o n', where x... is the output policy of Algorithm after T iterations.
Theorem 1. Assume the reward is deterministic.. Given M and grouping function g. when the value function difference between the optimal policy and the output policy T under the estimated
S Copts and the sample size K 648S|al log 8Siml.
MDP MG denoted as V -V
with
Ma
probability exceeding 1 one has
I1V2 V S Epeif:
where
88|gl Sigl log ((1-)))
71pp (1 7)2
R
4
Epery
20%
(4)
K(1 7)3
approximation error Expper
estimation error Car.
B6 min NES
Σ min P(s'(s,a), acAn
(5)
max B a (((a)))(((a
(R(s,a1) H(s, a2)).
(6)
As shown in Eq. (4), the performance gap between #² and TG.T contains two part: approximation enror and estimation error. We now explain the two error terms as follows.
Approximation error arises when the dynamic programming algorithm operates at the group level and ignores the disparities in transition probability distributions and rewards among actions within the same group. Specifically, 3 and 3 are the minimal áp and An. where (3p,Pr (5p,P,. P2) and (Bn, R1, R2) are the solutions to Eqs. (1) and (2), respectively. It is important to note that 88. and B are solely determined by the grouping function and do not depend on any other factors.
"Tii assumption implies Ro in Eq. (3) is accurate.

---

Published as a conference paper at ICLR 2024
As the number of groups increases, the approximation error generally decreases. The underlying intuition is that a finer grouping function has the potential to improve performance by minimizing grouping errors and capturing subtle distinctions within groups. We illustrate this concept by providing an example, where a finer grouping function in the feasible grouping function set is a refinement of a coarser grouping function. This structure has also been considered in prior work such as Jiang et al. (2015). As the grouping function becomes coarser, the differences in probability transition distribution and rewards within each group become larger, resulting in monotonic increase in the approximation error.
Estimation error can be further decomposed into two terms: Examp (the first term of Cest) and falg (the second term of Cest). Specifically. ésamp and Ealg reflect the performance loss caused by transition kernel estimation with finite samples and limited iteration numbers, respectively. When using policy iteration (Antos et al., 2008) or value iteration (Munos, 2005; Munos and Szepesvári, 2008) as the planning algorithm in Algorithm 1, Ealg decreases at a linear rate the number of iterations T. To provide comprehensive understanding, we present the detailed derivations of Ealg specifically for the case of value iteration in Appendix D.
The detailed analysis of the tightness of Theorem 1 in special cases and the proof sketch are presented in Section 6.
Comparison with Wang et al. (2021) We compare results with [(Wang et al., 2021). Theorem 3]. Wang et al. (2021) also considers the model-based method utilizing the generative model and investigates the performance loss caused by inaceurate feature extraction in [(Wang al., 2021), Theorem 3]. We summarize our main differences as follows. Compared with Theorem 1, our result characterizes the performance gap caused by the rewards model deviating from the grouping model, which was not considered in previous work. Furthermore, our result improves the approximation error of transition kernel difference by a factor of 22, We demonstrate the tightness of our approximation error with constant difference when deviation factors are small enough. Notably, our approach optimizes over (Pi, P2) and (R1, R2) to find the minimum S8 and RR--
Theorem reveals that the performance loss [V - V I| can be mitigated through tuning the sample size. iteration number, and the grouping function. Increasing the sample size K or the number of computational operations I" can reduce the performance loss since K and T are inversely related to Copt. This coincides with the intuition that larger sample dataset and larger available computational complexity leads to better-performet policy. However, the relationship between the performance loss and the grouping function is surprising.
A grouping function with a larger number of groups can sometimes achieve better performance. When the sample size and the number of computation operations are extremely large, the estimation error becomes significantly smaller compared to the approximation error, making the performance loss predominantly determined by the approximation error. In such cases, we can choose a grouping function with larger number of groups to achieve better performance.
As demonstrated in Fig. I(a), comparing the grouping and non-grouping settings with K' = 500 (red and blue lines with marker O), the non-grouping setting has smaller estimation error. The number of samples for each action is sufficient for accurate estimation, leading to better performance in the non-grouping setting than in the grouping setting. This observation aligns with analysis, which suggests the performance loss decrease as the number of groups increases.
Adjusting grouping function can sometimes enable trade-off between approximation and estimation errors. When the sampling size and the computation operations are limited, the estimation error cannot be disregarded. According Theorem Esmp decreases sublinearly as the number of groups decreases. This can be intuitively understood: when the sample size is fixed, having fewer groups allows for more samples to estimate the transition probability of each state-group pair, which consequently leads to a smaller estimation error. Similarly. when the computational complexity is limited, a smaller number of groups indicates a larger iteration number T, therefore reducing <alg-
As demonstrated in Fig. 1(a), comparing the grouping and non- non-grouping settings with K" = 10 (red and blue lines with marker D) the non-grou setting has a higher estimation error than the grouping setting. However, even though the approximation error is smaller in the non-grouping case, setting small deviation factors ensures that the grouping error remains small. Therefore, the

---

Published as a conference paper at ICLR 2024
08
+
(refieraaen 1o
= +D=
gooping
norggragingg x 540
Detientanee
G-10
grogping N7-
G=
motegraniing 8" 10
G=
1074
Irenatin Ntmbbr
brrssin Nambor
Figure I: Performance loss with grouping and non-grouping Figure Performance loss versus structure under the downlink transmission scenario (details sample size. Each point is averaged are in Appendix B.2). Each point is averaged over 20 rounds. over 1000 rounds. = 1000, and G 10.
A 1000.
overall performance loss of the non-grouping case is still significantly larger than the grouping setting. Fig. 1(b) implies the grouping can decrease the computational complexity drastically.
This surprising result also be verified Fig. 2. When only have limited sampling resources, coarser grouping functions are preferred. For example, when the total sample size is K = 10 the grouping function with group number G 20 (yellow line) preferred over other settings. However, in scenarios where the sample resources are unlimited (e.g., sample size K = 10'), the non-grouping function becomes the preferred option.
The above analysis based on Theorem reveals that optimizing the grouping function is a key factor in reducing performance loss. In Section 5, we propose a general optimization problem considering the trade-off between performance loss and complexity.
5 PERFORMANCE-COMPLLIN
TRADE-OFF
Theorem highlights the possibility of optimizing the grouping function to reduce performance loss when all available sample and computational resources are utilized. However, practical applications often involve additional costs for acquiring samples and computational operations, which may not scale proportionally with the size of these resources (Luo et al., 2021). To address this, we aim find the optimal sample size, iteration number, and grouping function that strike balance between complexity and performance loss. This trade-off allows us to achieve an acceptable level of performance degradation while keeping the sample and computational complexity manageable.
To capture this trade-off, we introduce utility function f R - IR that characterizes the preferences for performance loss and complexity. We make the following assumption.
Assumption 2. is monotone decreasing w.r.t each variable, i.e.. f(11.1,2) s f (, 2)2) iff I1 > I2, and same applies to y and z.
Assumption 2 guarantees that the utility function decreases when either the performance loss or the sumple/computaatinnal complexity increases while holding other terms constant. According to Assumption 2, the minimization of f((pert Csamp. Coump) reflects preference for lower performance loss and complexity. An example of f is weighted-sun -umhted--sumda function: (z, 2) a₁ + a2y + 0za, where a a vector of weighting coefficients and og < 0, 1,,,, 2,
The utility-mann maximiztaxiiiziiioon problem can be written as
max f (Cperr(g K.T)) (K). Coomp (1g), T)). gED,K.T T
(PI)
Specifically, if we set (Eper(g K,T)) Epent K, I",, and (Csamp: Coomp) are infinite when exceed- ing some threshold, the grouping function reduces the performance loss minimization with fixed sampling complexity and computational complexity. For a given feasible grouping function g, the optimization over K and T can be performed independently. Specifically. if f is convex function of K and T, we can directly use convex optimization methods to get the optimal K K* ([gl) and T ((g)). The optimization problem can be rewritten
max (gper(o g. K* K* ((9)), T*((g))) Cramp (K (K' (1ol)), Coomp (1g), T (Tg))) IED
7

---

Published as a conference paper at ICLR 2024
By solving the above optimization problem, achieve a balance between minimizing perfor- mance loss and managing complexity. However, solving the above optimization problem involves several challenges. Firstly, the feasible grouping function set D is discrete, and Gpert is implicitly related to the grouping function, therefore the optimization objective is not easily solvable. Addi- tionally, Eq. (5) shows the exact calculation of (per(9, K" ([9]), T ((gl)), which requires traversing over all coefficients of IP the R, and results in computational complexity that grows with the size of the action space. Moreover, the exact probability transition kernel is usually not known by the agent. Hence, we next devise a practical approach to handle this problem and analyze its performance.
5.1 PRACTICAL METHOD
To mitigate the computational demands of solving (PI), we propose (P2) as its approximated counter- part. Since the computational complexity of solving (PI) is dominated by the calculation of 3p and 3h in its objective, we approximate these terms in (P2). Instead of iterating through all the actions within the same group and applying Eqs. (5) and (6) to calculate accurate values of 3% and gg. we propose an approximation of (p K (Ig)). T (19))) based on randomly selected actions. Specifi- cally, we utilize samples obtained from the generative model to estimate the transition probabilities of selected state-action pairs, and then substitute these estimated probabilities into Eq. (4) to obtain the estimation épert. This approach significantly reduces the computational complexity, as the complexity of the calculation of approximate deviation factors is only related to the group size, which is much smaller than the entire action space. (PI) can be approximated as
max f (Cper( (g. K (19)). T" (19))) D), Cram (K (Igl)), (T),) 9ED
(P2)
where the calculation of (per((g. K (1g)), T' (Igl)) only uses actions belonging to A = An. and A is the randomly selected actions of the group E G. Subsequently, we can iterate through D to determine the optimal grouping function.
5.2 PERFORMANCE ANALYSIS OF THE PRACTICAL METHOD
We show that the above approximation in (P2) is reasonable, Intuitively, since actions within group have comparable transition kernels and reward functions in the grouped action space setting, we can capture intra- group dissimilarity by only selecting a subset from each group. Now We formalize this intuition.
We impose the condition that the rate of change of the utility function remains bounded in response to variations in the performance loss. The following assumptions are presented to capture these requirements.
Assumption 3. (f(x, 2) is Lipschitz continuous w.n. x.) There exists >> O such that [f y, 2) f02, y, =) L //2/
We define 7pp and πe as
7p max
[[P(||s, a.) - -P(- a2)l
7R a,
max (R(s, a1) - -R(s, az)))
In particular, Eq. (7) represents the proximity of the transition probability distributions and the reward functions in the same group. Note that 8p E Sup and f S Tjn-
Denote the optimal grouping function of (P1) g" and of (P2) as g", respectively. Correspondingly. the utility functions under g and g" are denoted as ʃ* and f*, respectively. Let Ki be the number of total samples required by the estimation of Epect- We have the following lemma to quantify the gap between f and fr.
Proposition 1. Assume the reward is deterministic. With probability exceeding 1 - 5, we have
4LAR + 4L7Syp 1->
4L7S
S log 25|
f
21
(1-7}² 2K1
(1-7)
action samphing evror
probubility estimation
8

---

Published as a conference paper at ICLR 2024
The performance gap between the optimal utility function obtained by solving (P1) and (P2) can be decomposed into two components: the action sampling error and the probability estimation error. In certain MDPs where the actions in the same group are close enough (small Tp and m7) and the utility function shows limited variation with respect to changes in 'per'' (small L), the action sampling error is low. Note that the probability estimation error is associated with the accuracy of estimating the transition probability distribution. The good news is that the required number of samples is only proportional to the number of groups, which is significantly smaller than the size of the entire action space. Therefore, these findings suggest that solving the approximate optimization problem (P2) allows us to obtain the optimal grouping function g with little performance degradation across a wide range of MDPs, while maintaining the sample costs at reasonable level.
PROOF SKETCH OF MAIN THEOREM AND TIGHTNESS ANALYSIS
Proof Sketch The presented Theorem 1 establishes the upper bound for VV VM r performance loss between the optimal policy and the policy obtained by our algorithm. Let प the group-wise optimal policy. We can decompose this difference into two parts: the approximation error IIV - VV so and the estimation error
xe the
[V VM V.
To establish an upper bound for the approximation error, we introduce an auxiliary MDP M₁ A, I,, ? which shares the same state and action spaces as the original MDP but differs in terms of transition distribution and rewards. The extent of this dissimilarity can be quantified by parameters 3p and $R. By comparing the value functions of executing the same policy on Mj and M, we can derive value function difference in terms of 3p, 8R. and the horizon 1/(1 - 7)) We can further get the approximation error is upper bounded by the twice of the value function difference under Mi and M.
To derive the upper bound of the estimation error, we employ the leave-one-out analysis (Agarwal et al., 2020b), which constructs auxiliary MDPs where one state is set absorbing while the others remain unchanged. This helps us to disentangle the connection between probability kernel estimation PG and the optimal group-wise policy && (Agarwal et al., 2020b). Compared with (Agarwal et al., 2020b; Wang et al., 2021), we extend the estimation error analysis sis from tabular MDPs grouped MDPs, obtaining a minimax optimal upper bound for the estimation error.
Tightness Analysis We compare our result with a known lower bound on the estimation error to show that it is tight. Further, we provide an example in Appendix C.3 for which the approximation error is also relatively tight.
Tightness of Estimation Error: Recall that the estimation error contains sampling error 6samp which is related to K and algorithmic error which is related to T. While sampling error decreases sublinearly with respect to K, the algorithmic error diminishes at faster, linear rate. Consequently, the limited sample size predominantly limits the estimation performance. The required sample size to achieve (1-7))<=) ). Due the lower bound of sample complexity in the generative model (Azar et al., 2012), we achieve the minimax optimal sample complexity.
e-optimal approximation error is Ó Sigl
Example showing tightness of Approximation Error: The example is designed such that the group- wise optimal policy पड has a high probability selecting a state-action pair with nearly zero potential reward while letting the optimal policy n" choose state-action pairs that have large potential rewards. We show that for any E > O, the difference between the derived performance loss of Thcorem I and Eapprox 2 is smaller than when 8p and 3R are small enough. This implies that the derived upper bound of the approximation error only differs by a constant factor of
7 CONCLUSION
This paper addresses the curse of dimensionality by exploring the inherent structure of group-wise similar action space. We introduced linear decomposition model for representing the similarity of actions within the same group. Our work provides insights into the trade-off between complexity and performance loss when applying reinforcement learning algorithms to practical applications.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work has been supported in part by NSF grants: CNS-2312836, CNS- 2223452. CNS-2225561, CNS-21 2NS-2112471, CNS- 2106933, a grant from the Army Research Office: W911NF-21-1-0244, and was sponsored by the Army Research Laboratory under Cooperative Agreement Number W91 INF- 23-2-0225. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
REFERENCES
Abel, D., Hershkowitz, D., and Littman, M. (2016). Near optimal behavior via approximate state abstraction. In International Conference on Machine Learning, pages 2915-2923. PMLR.
Abel, D., Umbanhowar, N., Khetarpal, K., Arumugam, D., Precup, D., and Littman, M. (2020). Value abstractions. In International Conference on Artificial Intelligence and Statistics, pages 1639-1650. PMLR.
preserving
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020a). Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095-20141
Agarwal, A., Kakade, S., and Yang. I.. F. (2020b). Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67-83, PMLR.
Antos, A., Szepesvári, C., and Munos, R. (2008). Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71:89-129.
Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L. (2020). Model-based reinforcement learning with value-targete regression. In International Conference on Machine Learning, pages 463-474. PMLR.
Azar, M. G.. Munos, R., and Kappen, B. (2012). On the sample complexity of reinforcement learning with a generative model. arXiv preprint 1206662006..466) 6.61.
Barto, A. G. and Mahadevan, S. (2003). Recent advances in hierarchical reinforcement learning. Discrete event dynamic systems, 13(1-2)441-77.
Du, S., Kakade, S., Lee, J., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization rl. In International Conference on Machine Learning, pages 2826-2836. PMLR.
Du, S., Krishnamurthy, A., Jiang, N., Agarwal, A., Dudik, M., and Langford, J. (2019). Provably efficient with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665-1674. PMLR.
Dulac-Aroodd G., Evans, R., van Hasselt, H., Sunchag, P., Lillicrap. T., Hunt, Jonathan anåd Mann, T., Weber, T., Degris, T., and Coppin, (2015). Deep reinforcement learning large discrete action spaces, arXiv preprint arXiv: 1/Xiv:/5/2.07699
Gelada, C., Kumar, S., Buckman, J., Nachum, O., and Bellemare, M. G. (2019). Deepmdp: Learning continuous latent space models for representation learning. In International Conference on Machine Learning, pages 2170-2179. PMLR.
Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. (2013). Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91:325-349,
Givan, R., Dean, T., and Greig, M. (2003). Equivalence notions and model minimization in markov decision processes. Artificial Intelligence, 147(1-2):163-2233
Ha. D. and Schmidhuber, J. (2018). Recurrent world models facilitate policy evolution. Advances in neural information processing systems, 31.
10

---

Published as a conference paper at ICLR 2024
Hafner, D., Lillicrap, T., Fischer, I., Villegas, R., Ha, D., Lee, H., and Davidson, J. (2019). Learning latent dynamics for planning from pixels. In International conference on machine learning, pages PMLR.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017). Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704-1711 PMLR.
Jiang, N., Kulesza, A., and Singh, S. (2015). Abstraction selection in model-based reinforcement learning. International Conference on Machine Learning, pages 179-188. PMLR.
Jothimurugan, K., Bastani, O., and Alur, R. (2021). Abstract value iteration for hicrarchical rein- forcement learning. In International Conference Artificial Intelligence and Statistics, pages 1162-1170. PMLR.
Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. (2023). Is q-learning minimax optimal? a tight sample complexity analysis. Operations Research.
Li, Walsh, T.J., and Littman, M. L. (2006). Towards unified theory of state abstraction for mdps. In AI&M.
Luo, B., Li, X., Wang, S., Huang. J., and Tassiulas, L. (2021). Cost-effective federated learning design. In IEEE INFOCOM 202 I-EEE Conference Computer Communications, pages 1-10. IEEE
Modi, A., Jiang. N., Tewari, A., and Singh, (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference Artificial Intelligence and Statistics, pages 2010-2020. PMLR.
Munos, R. (2005). Error bounds for approximate value iteration. Proceedings of the National Conference on Artificial Intelligence, page 1006.
Munos, R. and Szepesvári, C. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5).
Nachum, O., Gu, S., Lec, H., and Levine, S. (2019). Near-optimal representation learning for hierarchical reinforcement learning. In International Conference Learning Representations.
Ortner, R., Pirotta, M., Lazaric, A., Fruit, R., and Maillard, O.-A. (2019). Regret bounds for learning state representations in reinforcement learning. Advances in Neural Information Processing Systems, 32.
Puterman, M. L. (2014). Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons.
Ravindran, B. and Barto, A. G. (2002). Model minimization in hierarchical reinforcement lcarning. In Abstraction, Reformulation, and Approximation: 5th International Symposium, SARA 2002 Kananaskis, Alberta, Canada August 2-4, 2002 Proceedings 5, pages 196-211. Springer.
Ravindran, B. and Barto, A. G. (2004). Approximate homomorphisms: framework for non-exact minimization in markov decision processes. In the 5th International Conference Knowledge- Based Computer Systems.
Sun, W. Jiang, N., Krishnamurthy, A., Agarwal, A., and Langford, J. (2019). Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. Conference on learning theory, pages 2898-2933. PMLR.
Sutton, R. S., Precup, D., and Singh, S. (1999). Between mdps and semi-mdps. A framework for temporal abstraction in reinforcement learning. Artificial intelligene, 1111-11
Uehara, M., Zhang, X., and Sun, W. (2021). Representation learning for online and offline rl in low-rank mdps. arXiv preprint 1 10.04652.
Vershynin, R. (2018). High-dimensions probability: An introduction with applications in data science, volume 47. Cambridge university press.

---

Published as a conference paper at ICLR 2024
Wang, B., Yan, Y., and Fan, J. (2021). Sample-efficient reinforcement learning for linearly- parameterized mdps with a generative model. Advances in Neural Information Processing Systems, 0-223009-2302).
Weisz, G., Amortila, P., and Szepesvári, C. (2021). Exponential lower bounds for planning in mdps with reaaaaly optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR.
Zhang, X., Song. Uehara, M., Wang. M., Agarwal, A., and Sun, W. (2022). Efficient reinforce- ment learning in block mdps: A model-free representation learning approach. In International Conference on Machine Learning, pages 26517-26547. PMLR.
Zhou, D., Gu, Q., and Szepesvari, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages PMLR.
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL NOTATIONS
Define the the set of policies of MDP M := (S A, as aI { : [[ Given M and policy и E IT S + (2(A), we have collection of trajectories 7M (8t, at, N' starting from state-action pair ($o; an). Here, 8t+1 ~ P(-|s;, at), 4+41 ~ ((-181+1). and r = R(,,, a4).
We present the definition of value functions QM and VM for any E 8 and E A.
o
(m( = : Σ
Nre 80 = 8, = a
(8)
(T)() == (a [Q a)],
(9)
where [1 is taking expectation with respect to the randomness of TM- The optimal policy under M is defined as xI MM and its corresponding value functions are denoted as Q'M and Vū* Define Bellman optimal operator JMJ(s (s, a) == R(s, a) + + (P((1s,, a), max f(, a' )}- Bellman optimality equation indicates that Q'M is the fixed point of the Bellman optimality operator and satisfies Qi- TMQ
In addition to the set of policies IT defined on M, we also define the set of grouped policies based on a "lower-level" policy X' as follows:
llc == (malTa = x Port, , S + ((G))
(10)
Let & denote the optimal policy belonging to IIG that maximizes Vλ-
We also construct some special MDPs based on the grouping function g and "lower-level" pol- icy n!. We define the grouped MDP as MM == (S.9,Pa. Ra,7), where (s(
Ea-r((1k) [PP(''ss [s, a)] and Rc(s, h) == Ea-r(()n) [R(s,a)].
When P and R of M have the linear decomposition form Eqs. (1) and (2), we define Mi
(S, A. P1, R[, 7), where (s'ls, a) == Pi (s'(s,g(a)) and R (8, a) == Ri (6, ((a))for any (8, a).
For notational simplicity, we write ('(4z/)) (1 (1++)) and P (21+1|2)) (2( 1841).
(st, a.), PP (2 z.) = IP(s (z)) (ar+1181-))
B EXAMPLES OF GROUPED DEVIATED MODEL
B. WIRELESS ACCESS EXAMPLE
Consider wireless access system where multiple users send packets to an access point. Assume we have an access point and N users, where all users generate the same packet arrival rate and possess the same finite queue buffer. The local state of each user is defined as the number of packets in their buffer. When a user's local state is not less than 1, they have two available actions: either remain idle or transmit a packet to the access point. A collision occurs if multiple users attempt to send packets simultaneously, resulting transmission failure.
The success of a transition in the wireless access system depends not only on collision-free scheduling but also on the system's 's operational mode since the system may experience failures due to system errors. We denote the probability of the transmitter being in good condition and the corresponding transition kernel under state- acatenaction pair (s, a) as Ggood( (s, a) and P (- respectively. Note that when a collision does not happen, IP Fgood is irrelevant which user is sending the packets, that is, F gooo is irrelevant to a. We also denote the probability and transition kernel of the system failing due to system error under the mate-action pair (s, a) as Oer, (s, a) and Per, (+Is, a), respectively.
We can divide all actions into two groups Ai and A2 by the grouping function shown as
1, ||]||| = 1; g(a)
2, otherwise.
13

---

Published as a conference paper at ICLR 2024
Let 8p(s, a) = 11 (s, a), (i(-ss, 1) = Pgood(-ls), and "2(-(s,0) = Σ aem, (a.a) (1
1-agul
For A1, write the transition probability distribution as
a(-)s,a) = O'good( 8, a)P good a) +
Oen, (8, Pen (18,,a
= -1-Bpp(8, P 8p(8, (12(,,)))((-1s.)))
For other actions belonging to A2, the transmission certainly fails, therefore they have the same transition distribution, which we denote as cooliision Therefore, for a E A2, we have (-(-),,2) = coollision (-Is,, a), and (p(s, a) O.
To account for the varying importance levels of users, we assign reward of w1, to the user n whose packet is transmitted without collision. Additionally, to discourage long queues, can introduce penalty term w s. The reward function is defined as
max (wf w/ s) a A1.
R(s, a)
(o, otherwise.
B.2 DOWNLINK WIRELESS TRANSMISSION
Consider a downlink transmission system where a base station transmits packets to multiple users. In this system, adjacent users typically exhibit similar channel characteristics, leading to similar successful transmission rates. Furthermore, adjacent users often belong to the same category (e.g.. machines in factory) and have similar packet requirements.
S - 1} as the length the packet queue at the base station, with buffer size of S 5-11 1. The action establishes a connection. Assume users can be classified into G groups by the grouping function g A A (1, where the of users belonging group h An. The arrival rate at the base station is X.
Define the state 8 E {0. 10 S
f1,... AA} represents the user with whom the base station
We assume the successful transmission rate and reward of user a E An are u(s, = (1- (p(s,a))) h) (p, (s, and R(s, a) (1 Bn(ss R1,, h) BR(s, a))n(ssa)- c(s), respectively, μii and Rí represent the common transmission rate and common reward function, respectively. wp(8, a) and wR(s, a) are independently sampled from normal distribution. Note that we put penalty c(s) proportional to the queue length discourage congestion at the base station.
The setting of Fig. and Fig. 2 is as follows. The common successful transmission rate and rewards of all groups evenly spaced between [0, 1], given by (1 h) 2h-1 and (s, h) 1 2h-1
The penalty for queue-length
- We set (s a) = Br(ss a) = 0.01 in Fig. and (p(s.a) = Bn a) = 0.001 in Fig. 2. The packet arrival rate at the base station is 0.5. worth noting that the transmission rate and reward values are clipped within range of [0, 1]. The probability transition matrix can be obtained based on the arrival rate at the base station and the successful transmission rate for each user.
defined as c(s)
C PROOF OF THEOREM
C.I TIGHTNESS EXAMPLE
We now give an example to show that the approximation error bound of Theorem is tight with only a constant difference. Consider an MDP M = (S, 7,P,) R, where S (8o- 81) and A (ag. a1}.
The corresponding transition probability and reward function are shown in Table 1. Assume all actions belong the same group, then it follows that there exist (P1, P2) and (R2, R2) such that P and can be decomposed as
P(-ss,)) = (1 -1- +
R(s,a) =11 R, (s) (s
14

---

Published as a conference paper at ICLR 2024
8, a
a
S0: Og
5g, d1
$1, Up
$1, d1
0g
Q1
S0
1 3p
3p
0
80
0
81
3p
3p
1
81
1
8
(a) Transition kernel P(s'|s, (s,a)
(b) Reward function Rt(s, a)
Table 1: Transition distribution and rewards setting of the example MDP
80
$1
a
Sp/ $1, 4g
So/ 01
a
do a1
00
a1
80
80
1
0
80
0
0
0
81
81
0
1
$1
1
81
0
1
(a) (s(laa
(b) P2 (2('(ss,)))
(c) (s(s)
(d) R2(s,
Table 2: Linear decomposition the example MDP
where Pı, 12, R1, and Rg are shown in Table 2. Set the action-sclection policy n' as choosing ao with probability 1. Therefore, =t R n/ is
Ta = 1
a = E S: 00 a1,8 E S.
Applying = into the example MDP, we can have the long-term return as
VM (80) =0,
1 1-
VM (81) = 1- BP)r
Moreover, is obvious that the optimal policy that can maximize global long-term returns
0. au. E S
xt' (als)
1, a1, s E S,
and the corresponding value function is
3R
Bp
(50) 1 7(1 3r)
(1 - 7 Br))(1 -r)
Vi1ss) -1 -
Then for any initial state S, have
BR
73p
(s) VMto (8) 1- 8p)y
+
(1
Br
(11)
Expoos
As shown in Eq. (4) of Theorem 1, the approximation enror resulting from treating all actions within the same group as identical bounded by
2.
273p
Capprox
+ (1 - 7--
(12)
1 1-7
where we replace 3p and 9% by 3p and 3R. since we have 3p = 3p and 3 = 3R in this example MDP.
Comparing Eq. (11) and Eq. (12), we can see that the actual error caused by grouping Epppnn is close to the upper bound 2 when 3p is small.
Specifically, can show that for any 0, S V2(1 1 2 and 3R 1-2 then
V24"
C Capprox
2
apppox
S..
15

---

Published as a conference paper at ICLR 2024
10.03
0.002
0.01
0.00
0.10
0,05 0.00
0.0
Sp
0.10 0.00
0.00
Figure 3:
Cappons 2
approxx
To show this, we rewrite
Eappent
2
approxx as
E Cappeox
8pBRY (1 - 7) (1 Bp)r)
(3pr)²
appnox
Se.
2
7)2 (1 (1-3p)y)
By letting
< (1 7)e and b S ye, can get the conditions of 3p and 3R as
1-7
Br s V2(1 7)) Bn S
V27
We also verify the closeness between Supprox and Supess by simulation. Let 3p and 8n range from 0 to 0.1 and 7 = 0.5. As shown in Fig. 3, we can approximate 3n are small enough.
[V
-VMa by
Fappoux when 3p and
Therefore we can achieve the upper bound shown in Lemma with constant difference.
C.2 PROOF OF THEOREM
The presented Theorem establishes the upper bound for V V
_ the performance loss The performance loss can
between the optimal policy and the policy obtained by our algorithm.
be decomposed into two parts: the approximation error
Vū V and the estimation
VM "a.r where गद is the optimal policy belonging to HIg We provide two lemmas to bound these errors: the approximation error lemma, whose derivations can be found in Appendix C.3, and the estimation error lemma, whose derivations can be found in Appendix C.4.
Lemma 1. (Approximation Error Lemma) Under Assumption I, we have
B
Vv
2
+
1 1-7
(1-
where Bp and BR are given in Eq. (22).
Lemma 2. (Estimation Error Lemma) Assume |
V Ma
5 Copt-
When K 2
618 log s81vl
with probability larger than 8, one has
(1 11-))
Slyl log
881g8
VT VM VITaT||
< 220
8(1-7)
4copt
(1 3
1 1-7
16

---

Published as a conference paper at ICLR 2024
Using the above two lemmas,
easily get the performance loss bound.
When K' 2
648 log
58lal
with probability exceeding - 6, one has
7)
VM
V..
S
VM
Vi
+
V
00
(triangle inequality)
20
Slgl log
8.51g
5
7pp
5(1-7)
4
2
+ 2071
7)
(1-7) 7
1
(by Lemma and Lemma 2).
C.3 APPROXIMATION ERROR: PROOF LEMMA
Proof. We begin by demonstrating that the difference between Vū, and V is determined by 8p. and Bi. As both 'M, and T are policies within Hgg, with T being the optimal policy in HIg we
can subsequently establish an upper bound on the difference between V and VM- We now proceed to formalize this derivation.
Define
(z)( Erj,,
Σ 1=0
r'r I+ B Bepn) [[M(11+1)
(13)
Substituting Eq. (1) into (z)(,)) we have
(20) -Errg
Σ r'r, + T (1
(1xr) (0M())+))
+ T+1 Bp T (2g (Q
T
< Ey, M1
Σ 1=1
prr + 7
T+ 2 12 (21+1))
(14)
+ T+ 1 Tin
(using S 3r(2r) S 3r)
<A + 3p7 T+1
(by QM(()) 1
1-7
We then derive the upper bound of A₁ Since
Qm((+:) ET, (Pe] + (B (x++))))
17

---

Published as a conference paper at ICLR 2024
have
T
A1 = E 3eg
Σ
r' + 7 T+
PP (err))))) [r+1]]
1==0
+ xr (((ET))))()
Σ Cn' T+ X [(1 (e [rr+i]
( |B, Ra(E [rr+il P [M (by Eq. (2))
T
-ErJ,
7'r + T+1 XTTa>Pp" R [TT+]]
1=
+ (8glrr4iiRR
[rr+1] + (Er
(by 0 S 3x(zT) s 3p)
-Er
Σ
Xr + BEy 12 (2 + BR7 (by TT41 1)
1==0
-G (zo) ARY T+1
(15)
Plugging Eq. (14) into Eq. (15), we have
3pyT+1
(7(z)) S G7+1(20) + +12
T+1 +
(16)
1 1-9
We can expand (=0)
(20) R(=a) [ro] PxI (0((21))
12 [no] + (2o) [ro] + (2, [x)(
(by Eq. (2))
EEry, [ro + (1 1Q []] + ,n
-Go(zo) + FBx
(by definition of (zu) in Eq. (13)) Bry
T+1
(17)
lim
(zu) +
Σ
Ban
ΣΣ
7000
1=u
t=1
(by applying Eq. (16) for 7 times and letting T approach infinity)
3R
3py
= lim G7(2)) +
+ (1 71-
T-000
1-7
Specifically,
lim G7 lim Ery, T
N're + TT
T+1 PPT [Q((2++))]
T-00
(18)
lim Ery. T-
Σ 7're = Qmm(20))
Plugging Eq. (18) into Eq. (17), we finally get
|| Qui
= max (2) Qu,, (z)
< 3R +
3pp
(19)
7 (1 7
18

---

Published as a conference paper at ICLR 2024
To get tighter bound, want to get the minimum 8p and 3/ such that there exist (3p, P5)) and (5), R2, R2)) satisfying Eq. (1) and Eq. (2). The 3p minimization problem can be written as
min S.t.
3p
Eq. (1),
( A, (8,h)
Eres Pi 8, h) -1
(
Eves P2 s,a)=
(8.0)
(20)
Pi h)) 2 0,
( g. ( x A. (8.a) SxA,
P2(e(|s,a)200 0 S. (p(s,a)
8p,
where Eq. (1) is the linear decomposition of P, the last constraint is the the definition of 8p, and all other constraints ensure P1 and P2 are transition probability distributions.
The 3R minimization problem can be built in similar way as
min s.t.
BR
Eq.
(2),
e A.
0 < (8, h) 1,
(8. E
(21)
(2 1,
(s E S A.
(n( S BR.
(s.a) ExxA.
The derivations presented in Appendix C.5.1 reveal the following minimum values for 3p and nn.
3p
max (1 - Σ
min P(s'|s,a)) aEAr
*ES,
s'ES
(22)
8R
max SES
max R(s, a)
min R(s,a) aeAn
aEAAn
Plugging 87. and $7 into Eq. (19), we have
BR
3p7
|1o Quilloo 5
(23)
1-
(1-7)²
We can write (s) VM (s) as
(s) Mi (s) (s) + (-V (8) VMl + (-Vi, (8) + V2, a (s)
=VVM (8) - VNTH(() (8)) + (VTT (8) - Vi, (8)) + (VM, (8) - -V (8))
<(VM($) VUN (8)) (VM, (8) ViTl" (8)) (by Vil (8) Vin, (8) 0).
Since Vi(()= - Tim (s) 2 0. we have
V vM 11.- - Vin - -VAN + VM, - Vi |1
Vi VUN
Vin, V
(by triangle inequality)
max E. Ba (-1e)
(M(( Q (s.a)
max BaNtzy (110) Qiu, (8,a)
e Tim 2x (s,ai]
< max
(i, a)
QTiii (s, a)
+ max a.a
- 2' (s,
8.0
e1
+ +|1emn - -
31 +
713p.
$2
1 1-7
(1 - (1-7)2
(24)
19

---

Published as a conference paper at ICLR 2024
We can write (i((s) VM (s) as
VM(() Vi (8) -V (8) + (-V tMg (8) + (8)) V (s)
M
SVM (s) Vi (s)
(by TM, E Il and म.
=
max VM)
relle
Since (s((s) - Vin (8) 2 0 for all E S, we can apply infinity norm to both sides of the above equation and get
1|VM - Vialla
-
V - -V ||
2 1-7 7 (1 71p
(by Eq. (24)).
7)
This concludes the proof of Lemma 1.
C.4 ESTIMATION ERROR: PROOF OF LEMMA
Proof. To quantify the estimation error, convert the upper bound to the disparity in policy performance between variants: MMg and Mg. To accomplish this, utilize the leave-one-out analysis (Agarwal et al., 2020b). In this analysis, we create an auxiliary MDP denoted Ma. where one state is treated as an absorbing state while leaving the rest unchanged. This approach enables us to disentangle the relationship between the estimation of the probability kernel IPG and the optimal policy for the entire group T..
We can write Via (s) MM (s)
Vio (s) Vid (s) = -VMo (s) + (-V (8) + V
Mc (8)) (-V (s) + +Maa (s))
Ma
Ma
(--V (8) + 23
(8) V (8)
Ma
Ma
S(VMo (8) VT
Ma (s) + (V+ (s)
V Ma
(s) + (V (8) - Vilc (8)
Mc
(by Mo (8) s Via (s) for any s).
(25)
Applying infinite norm on both sides, we have
Viseo
- Vioo
+ +lIVin
- -v |1 +
+||
-vato
Ma
Ma
Ma
+ Copt + -10 QQMa
<
Q'a
(26)
(by
|
V
Mo
S Copt).
We first bound
1
2 and
leioo - 2x00 l can then be bounded in the same manner.
Ma
By Lemma 4, we have
1 - 2
|| < 2 -
Po) Ma |
Capt
+
(27)
1-7
Since V is not independent with P.. therefore we cannot directly use the concentration of the sum of independent variables to bound the sampling error ( - Pc) We construct the s-absorbing MDP MG = {S, G, P.G....... RG. 7), where s E S, E Ue and U, is the set of the feasible in state For any hn E 9 and so S, P.G.,,(() ho) and Ra (80, ho)
20

---

Published as a conference paper at ICLR 2024
defined as
Pa($1|80,ho)) ha),
80 f 8, 81 E S, 80 81 8, 80 8, 81 + 8, 80 + 8,
(G.a.u(1l(sohh))
1,
0,
(G,
ho))
u,
80 8.
Denote (s,)) Po h). We can rewrite
|Be - PG. iic
(PG (o.)) Ma
I (PG - Pa)( V Mann
+ (IP PP))(a))) -Vana
$ (Pa - Pa)( Vi Ma....
Vita. - -V villlo
(28)
(since
( (G.)
- 1).
Note that V
Ma... is independent with (s. and (Pa) We can use the variant of Bernstein's 's inequality Lemma 7 and union bound to bound the first term. With probability exceeding 55/2, for all 8, h, u, one has
log 4144
log 4
(o (o)() Viaaa
Var(Fa)io.)
Vinan
3K'(1 -
K'
(a) 4 4 /
4log 4 51g//8
-Vice
3K'(1 -7)
K'
loog S1g1/8
Var(Pa)am [viil.
K'
(29)
where (a) is because
V Varlalum
S Var(Falina) Viaan
V Ma.
+ Var(Falino)
Viaal
(by Varp [X + +Y v Van X + Vare [Y]
$ V Vo....
+ +v Var(Polann [vic]
Ma
Substituting Eq. (29) into Eq. (28), we have
(PP -Fa) <
<(V 4log 4 S19//8
+1 | - -Vitoll
K"
llog 4/24, 1Sg91/8
4log 4|4gg51
Varraaan
K'
V
Mal
(K'(1-2)
(30)
By Lemmas 10 and 11, we have
| - Vialll
=
=
| |iiaan
- V
$ u Vio (8)
(
(31)
where the first equality is because Lemma 10 and the second inequality is because Lemma 11. Substituting Eq. (31) into Eq. (30), we have
log 4 SM///gg//8 <(V
(PF -Po) Vinal s
||vie - -allo
+1
K'
4log 4/24, /
4log (|U4g|
VarpPo)am
Vx Mo.
K"
3K'(1 -7)
(32)
21

---

Published as a conference paper at ICLR 2024
/a log(
45|p1
We set Us as the uniformly spaced elements in [VMo (s)
7
VMdo (8) +
(1-7)²
K'
log 48 21)
and [Maa] = (1-9)z. We replace M and M in Lemma 8 by Ma and Mc. respectively, and then we have
2 log
45
min well
u/1 5(1 - ({1-
27
Ma
(1 - 7)2
K'
451g
2 log
=27
K'
Plugging the above equation into Eq. (32), we have
8 8log
8
88 aa 8 log
2 log
88191
(PG -Pa)(an)
Vi Mio
- 3k'(1- 7)
3(1
+ 2n
5(1
+ 1
K'
K'
8 log 8(1~>)
851g8
Var(Falian
Vina
K'
As
[Vinal]
As
S
+ +8 3(1 7)
K' + +22
7+1 Var(Folian
V
K"
(33)
where As = log
K5 (((1-))
Specifically,
Var(Falinn)
Viol can be rewritten as
Var(Bo)aa))
Vinal
sv Var(ro)aa
Viaa - v.g Var(Fo)
y Ma
V
Ma
+ V Var(Falina)
|ind (by
Varp X
S Var X + v Var [Y]
-vag $ Viio
+ +/|vvze Ma - MMo 00
+ Var(Folamn
VMO
Mo 10
Seape + 110 Mo -Qii
| Ma]
+ V Varraoaa
(by Viie - v villl
/
S Copt))
(34)
We come back to the upper bound of @ -Maalls
1 - -xioll
5||2(I-
-IpG - -Pa) Ma
Heopt
(by Eq. (27))
1-7
((
7
8
+ +88
As
KJ + +2v27V
Ao K
Nept
1 7
3(1 - 7)
7
+ 2222
(I- yIP 2 1-
Varea [Virc]] V
A K
(by Eq. (33))
7 1 1
A8 3(1 7) 888
8
K" + +2v27V
A
Nept
1
1
24,
K"
7
K"
+ 27V
2A
(I - (I- Po
)
) 1'1 Varra [v Ma
K"
2y
2A
+ 1 1-7
(by Eq. (34)).
K"
Me
22

---

Published as a conference paper at ICLR 2024
We replace P and in Lemma 9 by P& and mř, respectively, and then we have
(I (1- a PP )-1 1-/VVarr [vide]
2 S V (1 7)3
Plugging the above equation into 1 - Q
we then get
1 - -hioll
=1-~
- 2 ((
(1311-
+ +8y
A6
+
+2222
A
+
YCop
1+
2As
3(1
-1
K'
K'
1-7
K'
+ V7
As
K"
7)
1-
27
V
2
K"
2
Ma
2x0olloo
Rearranging the above equation, we have
1
eit
S
7
8
87
As
Ma
27
24
1- γ
3(1 - ?)
K
b
2/272
1
A
Eopt
2D
47
1+2
1-7
(1 - 7)3
K
7
K"
When K' 2 6484, (1-y)2, we have
A (1
As
a I 8
1
9
3)
C.8%%
(1 3
3
K"
d
6
110
Therefore, we get the upper bound of
Ma
- -Q
as
| Me - 2
As
s10%
+
K" 7)3
1 1-
With a similar derivation, we have
As K"(1 - 73
|Min - Miall
S $1071
Plugging the above equations into Eq. (26), we finally get
Viño - Mc.
As
$207
+
+ Eapt
K"(1 - 7)3 1 1-
SIg|As
4copt
/207%
K(1 7/
1-7
We finally show VMo ViA Since 7 E HG. there exists 00 such that m = 0- ní. For any : R(G) is higher-level policy, can establish the equivalence between Vi and V
Ma
23

---

Published as a conference paper at ICLR 2024
using the following reasoning.
V (50) (s0) (h) (o) a R(so, ao) + Σ P(s s0, ao Vo) (si)
hEg
(by Bellman equation)
Σ
(h]so)) (Baonih s0.b) [R(so. ao)l
heg
+7 Σ Bap [P((81)00 ao)l V (81)
Σ hEg
T (h|so)
Ro(so, + Σ (o(ssilsohh)V (81)
=BrMo Ma
Σ rrrelso
(by repeating above steps for infinite times)
Li=U
VMo (80)
(by definition of VMa))
(35)
Therefore,
Vi Via.r = =11320 - vilalee $2071
Sig
4yCopt
K(1 7)3
This concludes the proof of Lemma 2.
C.5 SUPPLEMENTAL LEMMAS THEOREM
C.5.1 MINIMIZATION OF 3p AND 3R
We solve the Br and in minimization problem (20) and (21) in this section.
We rewrite (20) as follows.
min
3p
s.t.
Eq. (1),
(s,s,,)) Sx A,
h))
(8,h) Sxg,
a)) =1,
(8,0) (.a)
(i( 0,
(s.s,,)) ($'88,)) x A.
Pr(s'(s,a)20,
0 0 Spp
(8.
As the optimizations over (p(s, S, e G are independent, we can decompose the above optimization problem into Sigl sub probloeolem.. Each sub sub-problem seeks to find the minimum value of (s, h)) that satisfies the given constraints related to state s and group h. Consequently, &p is determined the maximum of (p h) over all S and h G. We formally express this relationship as follows.
3p
max S.
Bp(s,h),
(36)
where (7,s,h) h) is the solution to the following problem.
min
3p
s.t.
Eq.
(1),
(8',a) E S x An.
Σ Exes P
8, h) 1,
Ee'ss P2
a.
a Ar.
(37)
Pi 8, 0.
s' S'ES,
(z(s'(s.a) 2
(s',)) E S Ar.
0 5 ()
< SBp
a Ar.
24

---

Published as a conference paper at ICLR 2024
Without loss of generality, we assume (s a1) = 3p(s, h), where a1 Aq, This implies that for any other actions a such that g(a1) = g(a), we have Bp(s, a) S (p(s,a1):
We firstly show the optimal solution h)) to Problem (36) is also the optimal solution to the following problem which relaxes the constraint 0 S (p a) S 3p.
min s.t.
3p
P(s'
8, a) = (1 3p) (s'sss 3pP2(s') a), (s', a) E E An.
wes Pi (8 8.) 1, P 11
(38)
a E Ab: s E S
Pi 8,)) 20, 0,
P2(5" 20,
(s', a)
E S
x A
We verify the equivalence between Problem (37) and Problem (38) through two steps. We first show that (8 h) is a feasible solution to Problem (38), then we show (3 h) is a optimal to Problem (38).
(Step 1) Suppose Pf(-|s, h) and ( a) are the common and individual transition probabil- ity distribution when Problem (37) attains optimal. We construct Fi (1 h) Pf h), and P2(1|s, a) (a( P1 h) + #f((,)) (-5(s,, a). Then we can easily verify PP (-1s,h) 8 (p(a)))
and P2(-|s,, a) satisfy constraints of problem (38), respectively.
(1) For the first constraint, we have
P(-|s, a) -(1 - (s(ss, a) (-1s, h) + 8p(s, a) (11s,a)
()) Pi h). and P5 a) satisfy the first constraint of Problem (37)) -(1-3b(6 (-
B,, h)) 1))22-18s
(substituting P (1 h) and (-)
(2) Since E Eves P1 (0, Exes (s'lss,, h) 1, the second constraint is satisfied. (a(lx.A)-8p1... Ph(e.)
(3) Eves (2(6'(s,h)
Pp(en) then the third constraint is satisfied.
(p(s.a)
(4) By the definition of IP and PřS have Pi (1 s, h) (s'l's h) 2 0 and (S |s, a) 2 0 for all s' S.
(5) Since 0 s (p a) S (7, h) < 1, then (b(a,)) (s.a) (a.h)
0, and (p.a.) (p))))
2 0. We have
(p(a.a) P2(s''ss a) a) (p(a,M)- (s' ss h) 3)(a,a) ( (s"1s, a) for all s' E S.
(p.)))
(Step 2) We then show that (p h) is the optimal solution to Problem (38). If there ex- ists (8p(s, s. h), (-|s, h), P2(-|s.00 a)) that satisfy all constraints of Problem (38) and Bp(s, h) < 37 (8, h), we arrive at contradiction. this case, (p, h) is also feasible solution to sub-Problem Eq. (37), and it contradicts the assumption that (7. h) is the optimal solution to Problem (37).
We will focus on solving Problem (38). By the first constraint of problem (38), for any a, a' E An. we have
P(s'(s s a) P(s'|s, a 3p h) (1P2('') [s, a,,,,)) P2(s' |s, a)). Summing both sides of Eq. (39) over s' and using Eves P2(s'(s,a) = 1. we have
(39)
1- Σ P(s'|s, a. B)(s,h)
(1-
1 Σ
P2(s'|s ((ch.rr)
FES
x'ES
Therefore 3p(s, h) can be rewritten as
Eves P(s'ls,
1r(s,h)
Eves F2(5'|s,a
2 Σ P(s' a a. (by P2(8'(12 an 2 0)
s'ES
=1
Σ
min P(s'|s, a) asAr
(by ain arg min ((s' s, s,))), aE
e'ES
25

---

Published as a conference paper at ICLR 2024
where the inequality is tight when P2(s'|ss as,h,,))) 0 for all s', 8 S. Thus have op(o, h)
Σ min P(s' P(s|(8,a):
aeAn
N'ES
Plugging (p(s, h) into Eq. (36), we have Bp hee Ee'es min P(s'(s,a))
3R minimization problem can built similar way as the Bp minimization problem.
min n
Eq. (2),
(s, < 1,
(s,h) E Sxg.
(40)
(2
(8,a) 8 A,
a) S Sn. (
Same to the discussion in the 3p minimization, the optimization solution to the above problem is
SR max (s,,,)) SEE,
(41)
where (8, /) is the optimal solution to the followin problem.
min
3x
s.t.
R(s a) = (1 h)) Bn A
(42)
0 < h8, 5 0 (2(8, 11
a a
By the first constraint the above problem, for any E E. a, e As such that R(s, a) # R's
have
Bu(s,h) R(s, a) R(s,a')
R2(s, a) R2(s, a')
2 R(s, a) R(s, a') (using 0 S R2(s, S 1).
Therefore, Bn(s, h) should satisfy
ht) 2 max (R(8, a) - R(s, d'))
a,A'
max R(s, a) min R(s, a), aελr
where inequality is tight when (s, a) and Rg a') 0 with a arg max R(s, a) and a' arg minaeA,, R(s, a). Thus (s. h) ma R(s,a) - minaEA, R(s, a). Plugging [ h) into Eq. (41), have
max R(8,a) min R(s. (1) aEAs,
(k(g) = max
sES,
concludes the proof.
C.5.2 SUPPLEMENTAL LEMMAS FOR ESTIMATION ERROR
(S, Lemma 3. For any MDP M -M, A.P. P. R, 7). the action value function with any policy π ((A) can be written
Qu = -I -1- -1-
Proof. By definition of (8, a), we have
Qu((, a) =E Er
r'z 80 8,
1=0
7 p (8t 8', 0, = a'1s0 8,00 a) a)R(s'
( a')
Σ
(TPTy y R (I - -T- R.
26

---

Published as a conference paper at ICLR 2024
Lemma 4. Let
Vine
V
S Eopt. Then
Ma 00
1
[I ---ph -PpP - - VT
=y
Mc
20
1
Ma
Mo
S
[I - ) -PPP-PPaVVe Mo
Me
1
7eo
Proof. We have
QMa
[I 1/ ) R (I- ) (by Lemma 3)
[I - PPG ) 1(1 xPG - (I- -I--18 1)
- -P- ) (1PE" Pe 1 l
[I PP= ) - Vo)
Similar to the above derivation, we have
| - @iilll =7
pTj - (Pp Pc) llee
PP ) - Pc)(V o7
Mo
+ Ve Mid
Ma
[I )P 'Pe Po)
V Viool
Ma
+ (I up lPo Po) 1000
$ 1-7 + (1 - ( ) - Pc) Vio
Copt
(by |
-vnll $ <optt
Lemma 5 (Hoeffding's inequality for general bounded random variables (Vershynin (2018), Theorem 2.2.6)). Let X1." XN be independent random variables. Assume that X; E [m, Mor every i. Then, for any t 0, we have
2t
P
EX,
(x,
EX.) 21 < exp
Σ (M, m.)
Lemma (Bernstein's inequality for bounded distributions (Vershynin (2018), Theorem 2.8.4)). Let X1, ... ,x be independent, mean zero random variables, such that [X,] < B for all i. Then for every we have
N Σ
6/2 7 Bt/3
X 21
< 2exp
(43)
where o² = EiE (X,).
Lemma 7 (Variant of Bernstein's inequality). Let XI,..., ,N be independent, identically dis- tributed, mean zero random variables, such that Xxi S B and Var [X.] = Var [X] for all i. Then with probability exceeding 8/2, we have
1
4B
4
4Var X
4 5
Σ i=1
X,
log
log
(44)
N
3N
N
Proof. When X1. be rewritten as
X are identically distributed and Var [X,] = Var [X] for all i, Eq. (43) can
1
N
Nt2/2
P
Σ
X
21
2cxp
(-Var
N
Var [X] Bt/3)
i=1
27

---

Published as a conference paper at ICLR 2024
Let
N2²/2
2 exp
S
(45)
Var [X] + B1/3
rewrite the above equation
2Var [
2Bt
4
log
log
N
3NV
A sufficient condition of t satisfying the above inequality is
4Var [X]
4Bt
4
2
log
and
12 2
log
N
3N
Therefore, when t
4B 3N
log
Varr
X
log 1.
8
X
2
N
On the other words, with probability exceeding
8/2, we have
N
4B
4Var
X
X,
log
log 8
N
3N
N
t=1
Lemma (Gheshlaghi Azar et al. (2013), Lemma 4). Consider MDP M A,, 7 which satisfies Assumption 1. M is estimation of M based on the generative model with n samples for each state-action pair. With probability exceeding ö, one has
2 log (2A4)
IV
V M 1100
7
(1-7)2
n
2 log (25A4)
[[V Villo
7
(1 - 7)2
n
Lemma (Agarwal et al. (2020b) Lemma 5). For any policy a and MDP M (8,A, R.7).
2 S V (1-7)3
(I- 11-PP (I->P">-
Varp [V
Lemma 10 (Agarwal et al. (2020b) Lemma 8). Let u² = Vin (8) and un (s).). We have
V VM.awr and for all policies n, V = VU
Lemma 11 (Agarwal et al. (2020b) Lemma 9). For all states 8, u, v' E IR, and policies n, |M - Qu, 1lso $ Iu u'l
and ||Q QM, 1l.0 I lu u'
Lemma 11 implies
V - VM. I <11 - -i..o I s/u -u'l.
D UPPER-BOUND OF PERFORMANCE LOSS WITH VALUE ITERATION
We consider value iteration (VI) specific dynamic programming algorithm shown in Algo- rithm Algorithm 2 provides generative-model-boee based value iteration, where Q++1 Tyu Q' for each iteration / and the output policy is mp(s)) arg max; Q' (s,h).
28

---

Published as a conference paper at ICLR 2024
Corollary 1. Let that Algorithm 2 be the dynamic programming algorithm in Algorithm 1. When sample complexity and computational complexity are Cramp (K) = K and Coomp (1g T) = (S + 2SIg])I, respectively, With a probability larger than -6 6,
VM
VaG.7 11 S Eporl (e, K,T),
where
851g1 Slgl log
(porl,,K1 = (p)())
1-7 + 79p(9)
8(1-7)
8y7
+ =20%
7)3
K(1 7)
- 7)3
Algorithm 2 Value Iteration
1: Input: MM = (S.9, A, Pa. R6
2: Output: policy n
3: for i 1.... . do
4: for hs E S do
5: Qi+ h) = Ro(s, h) + x(Po(-ls, h), maxires ((,,))))
6: end for
7: end for
8: Output policy (s) arg g Q" (s)
Previous research has demonstrated that the value function of the resulting policy converges to that of the optimal policy under Mg at a linear rate Munos (2005); Munos and Szepesvári (2008). This convergence is formalized in the following lemma.
Lemma 12. Let अ. be the output policy of A'Aggriitmm after T iterations. Then we have
2TT
Vi
V Ma
S (1 7)
For the completeness of this paper, we provide the proof of Lemma 12 in Appendix D.I.
Plugging Lemma 12 into Theorem leads to Corollary 1.
D.1 ALGORITIM ERROR
Proof. By Bellman optimality equation and VI update rule, we have P'm, hs TT Vio (s, (s, and (T, h) = TMa TT h), respectively, where Tua is the Bellman operator under Mc. We write QQin (8, QT (s, h))
1 (s,h) - (
= Tuo Pino (s, - Tuo (r,
=y (Pa(- (-((ssss))) ht. max O (,,1') - max Q - (,)'))
W
(by definition of TM/)
=7 (P(((11))))) max Pine (,hh)) max QT R²) h"
(by triangle inequality)
max Q2 - ((-)(()1))) -y [
h¹' Ma
Sy max 8'
@iai (s', h1)) (T- nn')
(by Σ Pa(s'ls, =
<7 .i - QQT-11
29

---

Published as a conference paper at ICLR 2024
Maximizing both sides of over (s, ft), we have
1 - - s sTlleino - -QT-1 lmo
(46)
Since Q' S - 1, we can apply the Eq. (46) over 1 - -Q"
for T steps and get
1 - -Q"
ST Oiua - -0"1
(47)
7"
(by s Qua:: Q" S 1-7 )
y
Then we can write Ve (s) - V (s)
Ma
Ma
Viaa (s) v (s) lire (8, Ma (s)
Mo
x00 (8)) (-Q" (8, (8)) + Q" (8, T (s)) + Qine (8,
+ + (s,,
+ (-Q (8, 7. (8) Vine (8, (8 Mo (8, m8(())
(Qin (S.7T) (s))
(s)) ( (', T0 (s.
+ (f, Dia (s, (f
+ (s, 2 Me (s, (8)))
where the inequality is because Q (s, (s))) arg maxi Q²,sh)). h).
(T
1 0 since ()))) =
Since Ma (8)
V (s) 21200 O. we apply infinity norm on both sides of the above equation and get Ma
||vee
V
11
Ma
max
(Qiúo (8, Q" T 7 (8)))
+ (Q² (8) Q'n (8,
+( Mo (s, (8)) 2+a Ma (s. (3)))
< max (0, (s)) Q²" (8, ग (s)) + max (8, (B)))) - Vuio (0, (8)
max Pino (s, (s)) 2th (s, (s)) (by triangle inequality).
Ag
We bound As and A2 separately.
A < max 1 -(a)))))
+1l)+mmas> max (=((s, -in (s) a.
<2 Q'no - :5T
Then.
A2 < max Dire (8) 2 (s,
= -max
R( + x (Po
Vio (-))
-(R(s, +7 (Po (f))) V= (.)) Ma
(by Bellman's Equation)
max
(Po( m)(() Vine (+) 3
Ma (+))
(Pa(118, 12 (8)), Vi ()) p () S
Vio - -va+ -
Sy max
30

---

Published as a conference paper at ICLR 2024
Plugging the upper bound of A1 and A2 into
Vioa
-
and rearranging the equation, we have
Ma
20 Ma
-
2y7 (1 - 7))
V Mo
20
S
1 1-7
where the last inequality is because Eq. (47). This concludes the proof of Lemma 12.
PROOF OF PROPOSITION
The approximate grouping function optimization problem can be rewritten as max (9 ((g)), (I9))) Cammp ( 9ED
(K" Commp (T),
(48)
where
éparll: ((g))) =2 (10(
+ (1(( 1 1-7
Slg log
8[1
851g
4e 4
+ 20m
(1 - 7)-
K(1 7)3
(b(19)) max aES,hEG
1 1- Σ
min P(s' ((ss|ssaa) aEAn
(1ol))
max oES.g(a))=g(aa)
(R(s,a1) - R(s,az))
(49)
For notational simplicity, we write f(épar K (1g)), T ((g)))) Csamp (K'(''"''s (191)), Coomp ( ((9))). the optimization objective function Eq. (48) that maps from g R. as f :
Proof. We first show for any MDP satisfying Eq. (7), the approximation error of (1g()) bounded by terms related to 7/p.
Bp(1g) = max
1 1-
min (( aedh
sES
max sES
max aE.An
P(s'(s,
Σ
min PP ( aeAn
(by Σ (((s'ssaa) for any a)
max SEG
Σ max (()'(s,))
Σ
min P(s'ls, acAt
aEAAn
max sES,
max P(s'|s, (8(18,0) aEd:
min P(s' s asd:
max (()) a2)) agE
max sEg
max
max |. P(ssssss
- az))
<STP
(by Eq. (7)).
Since 0 < (p((g))) ( < 1, we can write (7((g) - (lo(ll) as
(bol)) (p(())) & (p(lo)) s Sup-
31

---

Published as a conference paper at ICLR 2024
Define 0² arg ainaeA, P(s' s, a). We can rewrite {p(1g)) (l1( as
(b(1 (b((9)) = max sEg
Σ min P(s/)s.a)
1 Σ
min P(s'|s,a) aeAn
acdn
sES,hEg
min PP 1s, a) - E aEAn
min ((s5|s,,a) aeAn
max kEG
min P(s'ls,a) aEAh
min P(s'|s, a)) aedi
SES
P(s' s a² P(sssss
max SES
(by s, P(s
min P(s'|s,a) aEAr
ss P
We also slightly abuse the infinite norm at the last line and define
P
P
max ES
(((8's, P(s'(s,
Through Hoeffding's inequality shown in Lemma 5, with probability exceeding 6, one has
SIAT log 25
P P
2K1
The above equation shows 0 < (7<(1g)) s (3((g))
Combining the above equations, we have
STAl log
2SL 8
80 (1g1)) - < S max 11, V
(50)
2K1
Similarly,
(1gl))
max (Ra(s, - Rr (s, $ nR.
max
aES, NEN a1,a,EA,
where the inequality is by Eq. (7). Comparing the definition of Ba((l)) and Bi((l))), we have < (7(l9)) s (t(l))). Therefore,
0 E Pk(lo)) (lg))) & (%(ll)) S nn-
(51)
32

---

Published as a conference paper at ICLR 2024
b
100
Performance Loss
Ruaming Time (1n8]
grouping K' 500
non-grouping. K' 500
50
grouping K" = 10
100
non-grouping, K' 10
Iteration Number
Iteration Number
Figure 4: Downlink transmission setting with S A 10 and 10. (a) Performance loss comparison between grouping and non-grouping structure. (b)Running time comparison.
Then we can get Lemma by decreasing and Lipschitz continuity property of the utility function. have
=((gg) - ((ğ"1) (by definitions of f and f in Section 5) 8- i
=[( + (-f(1=*)) + f(lg*))) (-f(10))) f( f(()"))
- =(f(l=")) - f(lg"D) + (f(')))))(('))))>> + (f((")) f(("")))
<(S(19"1) - [(lg"D) + (f(1")) ((()g))
(by 1Ø^1 arg max f(1g)) and f(19")) - f(1g")) 0)
lsl
< <1(cpor((9")) éperl (1 [|epar((g)1)) (par((g))) (by Eq. (7))
(ppee((91) (p)))( 22L max lal
(R()))) (
b (pp(1))) (1a)))
4L max
+ 4L max
[gl
1-7
191
(1 1 7)²
(by definitions of (per((gg)) and Sper((1)) in Eqs. (4) and (49))
4 max
1]p V
SIÁ log
28]
2K:
4LR
(by Eqs. (50) and (51)).
(1 - 7-
This concludes the proof of Proposition 1.
F EMPIRICAL RESULTS
F.1 LARGER ACTION SPACE
We conducted an experiment under the wireless transmission system with a larger action space. We S = A 10a, and the number of groups is G 10. The details the downlink transmission setting are in Appendix B.2. As demonstrated in Fig. 4, when the number of samples is limited, the grouping- algorithm performs significantly better than the non-grouping method, and the computational complexity is greatly reduced. This simulation implies that the grouping method is applicable practical setting with large action space.
F.2 GROUPING SELECTION METHOD
We applied the grouping selection method within downlink transmission scenario, detailed in Appendix B.2, For this purpose, we randomly selected 20 actions from each group, allocating 200 samples for the MDP estimation corresponding each action. In this specific scenario, addressing
33

---

Published as a conference paper at ICLR 2024
(b)
Performanee Loss
G=2
vallue
G=5
G=10
C=20
10-2
100
10a
10
10
10
10
10
Sample Size
Sample Size
Figure 5: Downlink transmission setting with A = 1000, S = 5. (a) Performance loss of applying
Algorithm 2. (b)Objective function of (P2).
the approximated optimization problem (P2) enables effectively identify optimal grouping function, which balances the trade-off between sample complexity and performance loss. Notably, in conditions where substantial sample size is available, our optimization approach tends to select more refined grouping function. Conversely, under sample size constraints, the method inclines towards coarser grouping approach. This adaptability reflects the capability of the proposed grouping function optimization method in practical settings.
34


Reviews:
[{"review_id": "Yn6BJjjFux", "reviewer": "Reviewer_62eA", "summary": "The paper proposes an approach to achieve better sample efficiency in high-dimensional RL. To that end, the authors find a low-rank representation of the high-dimensional MDP by partitioning the action space in groups according to the predictive capabilities of the transition and reward models. In particular, the presented approach reduces complexity (induced by the abstraction) while addressing the decline in performance due to abstraction errors.  For that, the authors build a linear decomposition model to capture these relationships and optimize over the grouping strategy to strike this trade-off.  The authors also establish (tight) bounds for the performance drop due to action grouping. Finally, the paper presents a general optimization problem that considers the trade-off between performance loss and complexity.", "questions": "See weakness section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper proposes an interesting idea (group the action space according to the environment model) and addresses a challenging problem (high dimensional RL). The paper is also generally well written and states the details of the derivations clearly. The authors review the existing work in detail. The inclusion of theoretical results solidifies the claims made in the paper.", "weaknesses": "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.\n\nIn 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?\n\n[1] [https://github.com/MyoHub/myosuite](https://github.com/MyoHub/myosuite)", "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": "", "extra_scores": {}}, {"review_id": "U7MFZWcQzr", "reviewer": "Reviewer_oqpX", "summary": "This paper studies abstraction in reinforcement learning at the level of the action space. The authors propose to group similar action under an action grouping method, using this grouping method they can significantly reduce the size of the action space and lead to faster convergence.\nThe authors also analyze the loss induced by this grouping mechanism and show that it depends on the approximation error of the grouping method and the estimation error of the MDP induce by the grouping method.\nIt is then shown that it is possible to strike a balance between these two terms and that using a abstraction even if not perfect can lead to better performance.\nFinally the author show how to optimize the grouping function to minimize this error.", "questions": "Can you explain to me how Algorithm 1 is working without doing exploration?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper studies action abstraction, historically it has been less studies than state abstraction or abstractions over multiple timesteps.\nOverall the paper is well written and the main ideas are explained in detail.\nThe main result of the Theorem 1 is also interesting and new as far as I known.", "weaknesses": "The notation used in the paper were often not precise and made it more difficult to understand the work presented:\n- In section 3.1 it is not explained if the state space and action are discrete, finite or bounded.\nBecause of that is also unclear if |g| defined in section 3.2 can be infinite. In the same section for the definition of $\\pi^i$ should it be $\\{h\\}$ instead of $h$?\n- It would also be helpful to properly define the input of $\\mathbb{P}_1$ and $\\mathbb{P}_2$ to highlight that one applies on the original action space and the other applies on the lifted action space.\n- How is K defined in section 3.3? I don't understand the notation used.\n\nMy 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 a good coverage of the action / state space. Right now the algorithm could be stuck in a local minima while being able to accurately model the lifted MDP. Please let me know if I missed something\n\n\"However, the relationship between the performance loss and the goruping function is surprising. A grouping function with a larger number of groups can sometimes achieve better performance.\"\nI don't think this is particularly surprising when this is the reason why we use abstractions! Similar results exisit in the context of state abstraction, when looking at finite time guarantees while abstraction introduces an approximation error it can also lead to much better performance. [1, 2]\n\nSection 5.2, given that $\\mathbb{P}$ and R are bounded isn't assumption 4 always verified?\n\n[1] A unifying framework for computational reinforcement learning theory, Lihong Li\n[2] Approximate Exploration through State Abstraction, Taiga et al. arxiv 2018", "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": "", "extra_scores": {}}, {"review_id": "fGepYCLiku", "reviewer": "Reviewer_4oMe", "summary": "In large action space tasks, action grouping can make learning tractable. This paper formulates and objective to combine the performance loss due to grouping along with the computational and sample-efficiency benefits of grouping. They propose a practical approximation to this objective, that can provide a strategy for selecting near-optimal yet sample-efficient grouping strategies, altogether.", "questions": "- 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?\n- If the groupings are learned, how can the lower-level policy be feasibly obtained using domain knowledge? With the group compositions potentially changing non-stationarily, the lower level policy might itself be very challenging to learn or provide with domain knowledge.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "- The paper has a well-written flow and provides all the necessary prerequisities to understand the key contribution and distinction from the prior work.\n- The novel insight of cumulatively considering the performance loss due to grouping with limited samples and compute is an important relationship to understand and subsequently help with selecting a strategy for action grouping.\n- The practical algorithm makes the complexity of optimal grouping search to be proportional to the number of groups, which makes the problem tractable to solve.", "weaknesses": "- 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.\n- 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.", "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": "", "extra_scores": {}}, {"review_id": "vrpT75eGCZ", "reviewer": "Reviewer_ND6P", "summary": "This paper addressed the issue of explosive state-action spaces in high-dimensional RL problems. More specifically, it proposed to partition the action spaces into multiple groups based on the similarity in the transition distribution and reward function to reduce the size of the action space. Theoretical analysis shows that a finer representation reduces the approximation error resulting from grouping and also introduces higher estimate error when estimating the model. In addition, this work formulated a general optimization problem to select the grouping function.", "questions": "- How would the proposed perform when compared with other kinds of action abstraction methods?\n\n- I am not sure when do we need the proposed method. In which RL tasks do we specific need the proposed method to perform well?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed grouping strategy for high-dimensional RL problems is novel.\n\n- This paper provides theoretical analysis of the proposed method and the conclusions are interesting.\n\n- The writing is clear and easy to follow.", "weaknesses": "- Since this work focuses on MDPs with large action spaces that exhibit group-wise similarity, so it's application could be narrow.\n\n- The current experiments are only conducted on toy tasks. So it's not unclear how would the proposed method perform in more complex tasks.\n\n- Typos: \"of each sate-group pair\" ==>  state,", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)