Title: SUBJECTIVE REINFORCEMENT LEARNING FOR OPEN COMPLEX ENVIRONMENTS Anonymous authors Paper under double-blind review

Abstract: Solving tasks in open environments has been one of the long-time pursuits of reinforcement learning research. We propose that data confusion is the core underlying problem. Although there exist methods that implicitly alleviate it from different perspectives, we argue that their solutions are based on task-specific prior knowledge that is constrained to certain kinds of tasks and lacks theoretical guarantees. In this paper, Subjective Reinforcement Learning Framework is proposed to state the problem from a broader and systematic view, and subjective policy is proposed to represent existing related algorithms in general. Theoretical analysis is given about the conditions for the superiority of a subjective policy, and the relationship between model complexity and the overall performance. Results are further applied as guidance for algorithm design without task-specific prior knowledge.

1. INTRODUCTION:

One important target of reinforcement learning (RL) is to realize an autonomous agent that can help people solve various kinds of tasks in open environments, where the agent's observations and the environment's dynamics is both diverse and unpredictable (Wu et al., 2019) . For example, a visionbased robot doing housework in all kinds of room-settings may observe various combinations of indoor scenes; different tasks may require it to take different actions under the same observation; the successor observation after performing an action is not predictable, because the shape of rooms, furniture settings and pets' movements, etc. are not known a priori. Classical RL models environment and tasks as a Markov Decision Process (MDP). From this perspective, tasks in open environments pose difficulties that the state space S is large, the state transition dynamics P is nonstationary, and the reward function R may be contradictory (Brodeur et al., 2017; Xu et al., 2018) .

We argue that the key problem underlying these difficulties is data confusion, that is every sample the agent acquires from an open environment may reflect the properties of only a small part of the entire environment for a specific time period (Kempka et al., 2016) , thus data samples with similar current observations may have contradictory meanings under different circumstances, i.e. different transition dynamics, state (or state-action) values or action preferences. For this problem, current RL methods introduce out-of-MDP information such as task-encoding (Zhu et al., 2016) and goal-description (Wang et al., 2018) , or expand the state space into history space, in which every element is the concatenation of all information gained so far τ t = s 1:t (Farias et al., 2007) . As for the former category, the quality and quantity of extra information are decided by the designer (Schaul et al., 2015) . As for the latter category, although the whole history is what we can use best to alleviate data confusion in theory, it increases the complexity to a maximum point and is hard to achieve in practice; algorithms in this category thus either introduce regularization terms or transform the optimization target to easier ones. The problem is that both these categories depend on humans' understandings to certain tasks and lack theoretical guarantees; consider that tasks in open environments are diverse and unpredictable, it is necessary to build a system that can dynamically fit tasks without prior knowledge.

Intuitively, we humans also face data confusion problems in the real world, e.g. when going to office from home, different modes of transportation may include conflict behaviors e.g. walking in opposite directions. However, as long as we utilize arbitrary information and subjectively choose one of the modes, e.g. taking the bus, this task becomes concrete and without confusion; also we may subjectively focus on more concise aspects of the problem e.g. selecting bus numbers, which make the tasks simpler. Inspired by this, we propose a novel framework named Subjective Reinforcement Learning Framework that models the environment and tasks as a set of simple MDPs with no data confusion problem, and a subjectivity model over them; the corresponding subjective policy then includes two parts: acquiring subjectivity for each state with subjective samples, and choosing an action under the selected subjectivity. From this perspective, all aforementioned existing methods can be summarized as introducing subjective samples, i.e. state history or extra task information, beyond current observation s t to form a subjectivity so that the resulting subjectivity-conditioned policy does not suffer from data confusion problem and thus have better performance. Therefore they can be recognized as instantiations of our subjective policy, and analysis based on our framework is general and meaningful for all these methods.

In this paper, we discuss the conditions under which the subjective policy can achieve better results, and analyze in theory the relationship between overall performance and some key elements that characterize a subjective policy. The key elements are concrete and modifiable, and the analytical results guide us to design policy models that fit the need of problems in open complex environments without task-specific prior knowledge and with theoretically-guaranteed performance.

To sum up, we think our contributions are as follows:

1. To our best knowledge, we are the first to point out data confusion as a key problem to solving tasks in open complex environments;

2. We propose a novel framework named Subjective RL Framework and give theoretical analysis from a broader and systematic view;

3. We provide guidances for algorithm design based on our theoretical results.

2. RELATED WORK:

Our subjective RL framework deals with data confusion problem facing tasks in open environments, which has also been implicitly considered in several RL fields: multi-task RL (Zhu et al., 2016) , meta-RL (Rakelly et al., 2019) , continuous adaptation (Yu et al., 2018) and hierarchical RL (Al-Emran, 2015) . We analyze their inherent defects-dependence on designers' knowledge for tasksin the following three paragraphs.

The field of multi-task RL considers an agent performing different tasks in possibly different environments, where data confusion is expected to happen across tasks. One direct category of methods equips the agent with extra task-specific information (Riedmiller et al., 2018) , e.g. a vector g i describing the goal of task T i ; these methods requires the extra information to be available and sufficient enough to distinguish tasks from each other, which is guaranteed by designers' knowledge.

Considering cases where suitable extra information is not available, various task-encoding methods have been proposed (Sung et al., 2017) , which generally extract a task feature vector from the whole trajectory τ and build the policy under condition of such feature vectors. These methods can be concluded as adding regularization terms into the complex end-to-end framework according to experts' prior knowledge, which includes the length (Sorokin & Burtsev, 2019) and prior distribution (Rakelly et al., 2019) of the feature vector.

Meta-RL methods, or learning-to-learn, turns to model the learning process instead of the original task (Gupta et al., 2018a; b) , which implicitly bypass the problem of data confusion. However, these methods still treat the learning process as a single-value function, e.g. the learning process of task embedding (Lan et al., 2019) and an exploration strategy (Garcia & Thomas, 2019) ; thus their successes are based on the assumption that there are no data confusion in the meta learning phase. Similarly, continuous adaptation problems focuses on the transfer performance from source to target tasks and neglect the data confusion problem by assuming that the relationship between successive tasks can be correctly modeled by single-value mappings (Al-Shedivat et al., 2018) .

Hierarchical RL is a broad field where methods aim to divide complex tasks into many different sub-tasks so that the overall data-efficiency can be improved (Barto & Mahadevan, 2003; Al-Emran, 2015) . Although this idea of divide-and-conquer may result in the confusing data samples being divided into different sub-models and thus each sub-model handles no confusion, which is one typical target of subjectivity in our framework, the actual performance is determined by the design of the hierarchical structure, e.g. number of options (Jain et al., 2018) and capacity of both the top-level and low-level models, which are still designed according to prior knowledge and adjusted through empirical results. Instead, our framework takes all these hyper-parameters in consideration and can adjust to tasks without prior knowledge.

The data confusion problem in open environments can also be recognized from the perspective of errors in function approximation. Existing research on function approximators in RL consider some specific types of model like linear approximations or neural networks, and analysis are given about the overall convergence or performance of certain RL algorithms (Schoknecht, 2003; Achiam et al., 2019; Papavassiliou & Russell, 1999) . However, approximators considered are end-to-end and do not consider the utilization of extra information. Different from these, our framework formalizes both original data samples and extra information used to construct subjectives, and so has the capacity to analyze the effect of extra information.

3. SUBJECTIVE REINFORCEMENT LEARNING FRAMEWORK:

In this section we describe the data confusion problem of tasks in open environments. Then we give mathematical formulation of our subjectivity reinforcement learning framework that states the data confusion problem from a broader and systematic view.

3.1. PROBLEM STATEMENT:

In traditional RL, the environment and tasks are modeled as T, S, A, P, R, γ, ρ , where T = {0, 1, 2, . . . } is the set of considered time steps, S = {s t } the state space, A = {a t } the action space, P (s t+1 |s t , a t ) the transition probabilities from each state-action pair to successive states, R : S × R → [0, 1] the reward distribution over states that expresses the task, γ the discount factor that describes the relative importance between short-sight and far-sight rewards, and ρ the probabilistic distribution of initial observations. The goal of traditional RL is to find a policy π T : S → A that maximizes the following return:

EQUATION

where V πT (s) is the state-value function that satisfies the following Bellman equation:

EQUATION

RL agents interact with the environment to collect transitions s t , a t , s t+1 , r t+1 . Different RL algorithms utilize the collected transitions and equation (2) in different ways to construct functions that represent polices so as to maximize objective (1). Generally they can be summarized into three categories: model-constructing, value-based, and direct action-mapping, which respectively process the transitions into forms of (s t , a t ) → s t+1 , s t → V (or (s t , a t ) → Q for state-action value-based methods) and s t → a t . In this paper we call such correspondences "data samples" to emphasize that they are the actual data used to construct function that represent the policy, and use z = (x, y) to generally represent the content and label of a data sample. Further, we denote the function as g T (•), and the optimization problem becomes:

EQUATION

)

where D is the set of data samples and N D is the number of them; L is a predefined loss function, e.g. l2-norm.

Note that data samples reflect properties of environment, policy and tasks, and they depend on the sampling process in RL. Because g T (•) is a single-value mapping, normally the optimization problem (3) results in the expectation of data samples and alleviate the variances induced by the sampling processes. However, in open environments the observation space S is large, the transition dynamics P is nonstationary, and reward function R may be contradictory; thus same state-action pairs may transit to contradictory successive states and rewards; then the Bellman equation ( 2) may return different label y for the same data content x. Such differences come from the variances in environment or tasks, and should not be entangled through expectation. In this paper we name this problem data confusion. To eliminate this problem, extra information, which we denote as κ, need to be introduced, and the key problem is how to select κ and efficiently use it to eliminate data confusion at the minimum cost of simplicity. In the next subsection we introduce Subjective RL Framework to formalize this problem.

As aforementioned, methods that expand the state space directly into the history space and try to construct the mapping from history to labels does not necessarily eliminates this problem in practice, so it remains meaningful to analyze the data confusion problem under the assumption that function approximators can only handle finite length of states. To make notations simple, here we focus on confusing mapping from single states and leave the history to the subjectivity part, without loss of generality.

3.2. FRAMEWORK:

We propose to model tasks in open environments as h, M k , where h is the subjectivity that "subjectively" treats the entire large, nonstationary and possibly contradictory environment as some separate, simple and stationary MDPs

M k = T k , S k , A k , P k , R k , γ k , ρ k , which we call subjective MDPs.

One key property of subjective MDP is that there are not data confusion problems for the functions used to construct corresponding policies, i.e π k S (a|s), V k S (s), Q k S (s, a) and P k S (s, a) should not contain data confusions. The expected role of h is to utilize extra information κ to divide contradictory data samples into different sets. A formal definition of it is given below.

Definition 1. The subjectivity h in subjective RL framework is a function that maps a piece of extra information κ to the sum-to-one vector that corresponds to the weights of all possible subjective MDPs M k .

Correspondingly, we maintain a subjective policy π k S (a|s, κ) for each subjective MDP and the overall policy can be formulated as:

EQUATION

where h k is the k-th element of h and N S is a variable characterizing the number of maintained subjective MDPs; κ ∼ F (κ) where F (κ) is a distribution that is assumed to be available. Here κ may correspond to multiple types of information, including state history, out-of-MDP task encoding, samples from related tasks, etc. Similarly the overall value functions or model transitions can be represented in similar forms, e.g.

V πz (s, κ) = NS k=1 h k (s, κ) V k S (s).

Then the overall global optimization problem of the task becomes:

EQUATION

where

EQUATION

Note that the subjectivities only disentangle the original problem into a variable number of subjective MDPs and does not change the original properties, thus the global return G reflects the same optimization goal.

From the perspective of data samples, the policy function g z (•) becomes: One important property of extra information κ is that it may become available only after certain time step and its effect on subjectivity about data samples may only last for a finite time-period, e.g. the history of states τ t appear at time-step t and expires after the possibly existing episode ends. Therefore we use κ t to denote the extra information that becomes available at time-step t, and introduce a data-related mask to characterize its range of effect: Φ (x j , κ t ) = 1 if κ t can affect the subjectivity about data content x j , and 0 otherwise. Note that Φ only depends on the arriving time of extra information and the data samples, so it should be available under most conditions. Then the constraint on h can be formalized as

EQUATION

EQUATION

Figure 1 provides an illustration of the relationship between data samples, extra information and the mask.

We parametrize h and g S with α h and α S respectively, and require the range α h to satisfy the constraint expressed in eq.( 8). The optimization problem about data samples then becomes:

EQUATION

where N κ is the number of available extra information.

4. THEORETICAL ANALYSIS:

In the above section we formalize our Subjective Reinforcement Learning Framework which formally considers the data confusion problem and the extra information used to eliminate it. Below we analyze in theory the performance of a subjective policy. In the first part we focus on the return G which is the optimization target of RL; in the second part we turn to analyze the risk bound of the policy function which relates closely to G, is general, and does not depend on certain algorithms.

4.1. RETURN GAP:

In reinforcement learning, the return G is the overall criterion to evaluate the performance of a policy. Here we firstly define the return gap as:

EQUATION

)

where π z refers the subjective policy and π T the policies in traditional forms.

For tasks in open environments, there may be more than one optimal trajectories τ * that maximize the global return. For simplicity in notation here we consider cases where there is only one initial state s 0 and only one optimal trajectory, without loss of generality. Intuitively the loss function ( 3) and ( 9) need not be zero for an optimal policy, but the policy function must represent data samples from optimal trajectories well so as to be optimal; thus when data confusion problem happens within such data samples, the subjective policy may gain better performance.

In the following analysis we denote the optimal subjective policy as π * z (which includes h * k and π k * S ) and let the optimal trajectory achieved by it be τ * z = {(s 0 , a 0 ), (s 1 , a 1 ), . . . , (s T , a T )}. In order to express the changing of extra information κ, we use subscript i.e. κ t to denote the available extra information at time t.

Theorem 1. Assume that all possible data samples appear infinite times when the total number of samples N D → ∞, then the return gap δ ≥ 0 holds true; Proof. In our framework we have subjectivity h that aims to divide confused data samples under the constraint of eq.( 8). Consider a given piece of extra information κ and any subjectivity h 0 , our subjective policy is defined as eq.( 4). As for any traditional policy π T (a|s), we can define fake subjective policies as:

EQUATION

where π k S,fake (a|s) = π T (a|s) for any s, a, k. Then we have π z,fake (a|s) = π T (a|s) hold true for any s, a, κ, which means the policy space Π T is equally transformed in to Π z,fake . Because π k S,fake (a|s) are defined to be the same with reference to k, we have Π z,fake ⊆ Π z . Therefore, under the condition that samples required to estimate the optimal policy are plenty, which ensures that an optimal policy can be learned out of the data, the introduced subjectivity extends the policy space and theoretically provides no worse result than single-value-based methods, that is δ ≥ 0.

Corollary 1. Further, if there exists steps i, j ∈ {1, . . . , T } such that transitions from τ * z satisfies s i = s j but π z (a|s i , κ i ) = π z (a|s j , κ j ), then δ > 0.

Proof: We have π T (a|s i ) = π T (a|s j ) because s i = s j . Because of π z (a|s i , κ i ) = π z (a|s j , κ j ), π T (a|s i ) = a i and π T (a|s j ) = a j cannot hold at the same time. Thus τ * z cannot be fully presented by π T . As analyzed in part (1), the policies that can be represented by π T is a subset of π z , and according to the assumption that τ * z is unique, we reach the conclusion that δ > 0. The following theorem transforms the return gap into the analysis of risk bound of the policy functions:

Theorem 2. Under the assumption of sufficient sampling and exploration, the gap between approximate return and the optimal return satisfies the following inequality:

lim w→∞ |G (π w ) -G * | ≤ δ com + 2γ (1 -γ) 2 (12)

where π w is the policy at the w-th iteration, γ the discount rate, δ com the bound on error incurred in computation of policy update and the worst-case bound of error on function approximation (Bertsekas & Tsitsiklis, 1997) :

EQUATION

Proof : Bertsekas & Tsitsiklis (1997) proves that:

EQUATION

where V * the optimal state value function. Recall that the overall optimization problem is defined as:

EQUATION

Because ρ (s 0 ) ≥ 0 and s0∈S ρ (s 0 ) = 1 for any s 0 ∈ S, the following equation gives the proof:

EQUATION

In practice, γ is a part of the environment, and δ com can be made small (Bertsekas & Tsitsiklis, 1997) . Thus the above theorem shows that decreasing is necessary for improving the overall performance.

In the following subsection we analyze the relationship between and the general design of policy functions.

4.2. RISK BOUND:

In order to analyze the errors in approximation of policy functions, we transform the loss L in the optimization target of the policy to a compact and probabilistic form. 

EQUATION

We denote the distribution of b and d respectively as F (b) and F (d); the parameters of h and g are still α h and α S . Then we define the expected risk and empirical risk as follows:

Definition 2. The expected risk functional in subjective reinforcement learning is:

EQUATION

For simplicity, we use α to denote the combined set of α h and α S , and

ς (d, b, α) = L [y i , g (d i , b)] h (d i , b).

Then the above definition results in:

EQUATION

We denote the considered number of possible b to be m; under specific design of the output of h (x, κ), m can be represented using N S , e.g. in one-hot cases we have m = N S . Then we can define the empirical risk functional as follows.

Definition 3. The empirical risk functional in subjective reinforcement learning is:

EQUATION

Note that the Risk (α) here expresses the in eq.( 12). In order to minimize it, we consider the maximum possible risk gap between Risk emp and Risk (α):

EQUATION

The above form of expression enable us to adopt results from Su et al. (2019) , which is summarized in the following theorem:

Theorem 3. Consider α * that minimizes the empirical risk (20), the following inequality takes place with probability 1 -η:

EQUATION

where Note that A b , B b , A d and B d are fixed once the actual form of functions are determined. We also want to emphasize that α * h and α * S , which compose α * , should respectively satisfy eq.( 8) and the independence of g(•) on κ.

EQUATION

5. GUIDANCE FOR ALGORITHM DESIGN:

In previous section we analyze in theory how the performance of a subjective policy relates to different factors. Now we discuss how these results can be utilized to guide the designing of algorithms for tasks in open environments.

As analyzed in section 3, there is data confusion problem in tasks in open environments. Generally extra information should be introduced, but how to select the capacity of functions so that the overall performance is optimal becomes an important problem, because there are not tasks-specific prior knowledges in open environments. In theorem 2 we derive that, under the assumption of sufficient exploration and sampling that ensures the unbiasedness of data samples, the gap between achieved overall return and the optimal return tends to a value that is bounded according to ; then in theorem 3, this is further bounded by ζ n,m plus the empirical risk with probability 1 -η, considering their maximum values over the whole learning process.

Note that the elements in eq.( 23), i.e. u b , u d , m, A b , B b , A d and B d , are all accessible and modifiable as long as the data and the designed functions are determined, and can have concrete meanings if actual algorithms are given. Concretely, m may be the number of options if b is set to be one-hot and the option-based algorithms are adopted; A b , B b , A d and B d may be directly accessible if sigmoid functions are appended to function h and g; u b , u d can be determined once the functionals and the mask Φ (x, κ) are given.

Therefore, for tasks in open complex environments, we may first select η which reflects the needed confidence level of the analytical results. Then, after data samples from the tasks being collected, eq.( 23) guides us to reduce ζ n,m through the design of elements u b , u d , m, A b , B b , A d and B d , which can then be used for the design of actual forms or hyper-parameters. Note that the expected risk Risk also includes Risk emp which may also be affected by such adjustments, but as both Risk emp and ζ n,m have been expressed explicitly, we argue that a satisfying adjustment is still achievable despite the possible difficulty in computation. may also be affected by such adjustments. Besides, the data samples change as the policy evolves during training, which may lead to the change of ideal adjustments; for this case, changes to m, u b and u d may require the re-tunning of the parameters α in e.g. neural networks; one solution is to calculate adjustments with strict η but change them when loose η is not satisfied, another solution may require designing a form of parameterflexible function model.

6. CONCLUSION:

In this paper we consider tasks in open complex environment and propose data confusion as one core problem. Although current methods relieve this problem to some extent, their reliance on task-specific prior knowledge limits their capacity for tasks in open environments. We propose subjective reinforcement learning framework to represent data confusion problem from a broader view, and subjective policy that generally represents many existing methods. Our theoretical analysis shows the conditions under which a subjective policy outperforms traditional ones, and the relationship between overall performance and the key elements that characterize a subjective policy. As the elements are concrete and modifiable, our analysis further provides guidance for designing algorithms with theoretically guaranteed performance. We also point out several difficulties in practical implementation, which include the complexity in calculating ideal adjustments to the elements and the probable necessity for re-tuning when considering specific kind of models; these problems are planned as future works.

:



Figures and Tables:

Figure 1: Samples in the Subjective RL Framework

First we concatenate the denotation of extra information κ i and data sample (x j , y j ) as d ij = (κ i , x j , y j ); we consider the number of available d ij to be n and thus use d i to represent the input of subjectivity. We then use b to denote the weight vector output of the subjectivity h (d i ); then we combine the N S subjective MDPs base on b as g(d i , b) = b • g S (d i )where g(•) and g S does not depend on the κ part of d i ; finally we equally express the original subjectivity in the probabilistic form h (d i , b) = P (b|d i ) and reach the transformation of L:

24) where Risk local (α, b) = ς (d, b, α) dF (d); u b and u d are the VC dimension of function h and g respectively.

Peer review (iclr2020):
The paper suggests that one common problem encountered by reinforcement learning algorithms in open environments is *data confusion*, which essentially means showing the same input data with different --possibly contradictory-- labels/targets. The proposed solution to this conceptual problem is to split the original MDP *M* up into multiple simpler MDPs *Mk*, where M does contain possibly contradictory (*confusing*) data, while each individual Mk does not contain any such problem and, even better, is stationary. The *subjectivity* function *h* then has as role to split any data tuple across Mk, possibly using extra information kappa. Furthermore, several theorems show that under several conditions, the return of the subjective policy (learned via Mk) is not worse than that of the *traditional* policy. I lean towards rejecting this paper. The whole gist of the framework can be crudely summarized as *if data contradicts, split up into non-contradictory sets using extra info.* The motivation keeps repeating that no task-specific prior knowledge being necessary, but I believe this hinges on *h* being sensible, which might not be feasible without task-specific prior knowledge. Furthermore, and this is my main concern, there is not a single experiment demonstrating how any of this would behave in practice. It would be good to have one (possibly constructed) experiment showing that data confusion indeed is a problem in practice (intuitively, it is), and then a specific instantiation of the framework that solves this example. Furthermore, I am not convinced that the proposed bounds can easily be concretized for an instantiation of the proposed framework, especially when considering deep networks; again, this concern could be alleviated by an example instantiation. Proposing something that is in principle more general and *in principle cannot be worse* but then not demonstrating that it actually is the case is, in my opinion, not enough. Finally, and this is not a deciding factor in my rating, the paper has quite some writing problems. On the first page alone, I found a lot of spelling and grammatical mistakes (see list at end) and the notation is sometimes confusing to me. For example, *R* is defined as a mapping of S x /R -> [0,1], but what is */R* (curly R)? And then in (1) R is used with a single argument while in (2) not anymore. I can guess what is meant, but it feels inconsistent. In Theorem 1, I believe it should be *the gap delta >= 0* and not *the gap g >= 0*, no? Abstract and 1st paragraph mistakes (unfortunately, no line numbers in this template!): *researches* -> *research*, *algorithm designing* -> *algorithm design*, *task-specific prior knowledge about tasks.* -> *task-specific prior knowledge.*, *not known in prior* -> *not known a priori*, *Classical RL model environment...* -> *Classical RL models environment...*. Also, quite some citations are missing the year, e.g. Schaul et al., Papavassiliou&Russell, ...