# exploration_via_state_influence_modeling__f724847f.pdf

Exploration via State Inﬂuence Modeling

Yongxin Kang1,2*, Enmin Zhao2,1*, Kai Li2, Junliang Xing2

1 School of artiﬁcial intelligence, University of Chinese Academy of Sciences 2 Institute of Automation, Chinese Academy of Sciences {kangyongxin2018, zhaoenmin2018, kai.li}@ia.ac.cn, jlxing@nlpr.ia.ac.cn

This paper studies the challenging problem of reinforcement learning (RL) in hard exploration tasks with sparse rewards. It focuses on the exploration stage before the agent gets the ﬁrst positive reward, in which case, traditional RL algorithms with simple exploration strategies often work poorly. Unlike previous methods using some attribute of a single state as the intrinsic reward to encourage exploration, this work leverages the social inﬂuence between different states to permit more efﬁcient exploration. It introduces a general intrinsic reward construction method to evaluate the social inﬂuence of states dynamically. Three kinds of social inﬂuence are introduced for a state: conformity, power, and authority. By measuring the state inﬂuence, agents quickly ﬁnd the focus state during the exploration process. The proposed RL framework with state inﬂuence evaluation works well in hard exploration task. Extensive experimental analyses and comparisons in Grid Maze and many hard exploration Atari 2600 games demonstrate its high exploration efﬁciency.

Introduction

Reinforcement learning (RL) in hard exploration tasks with sparse rewards is an essential problem in artiﬁcial intelligence. Unlike typical RL problems, hard exploration tasks with sparse rewards often consist of two stages. First, there is a long period of exploration before the agent obtains a new reward, which we term the no-reward exploration stage. Second, after the agent obtains some local rewards, it follows a process of experience utilization and continuing to explore, which we term the local-reward exploitation stage. In this paper, we focus on the ﬁrst and more difﬁcult no-reward exploration stage. During the no-reward exploration stage, traditional RL algorithms based on value function (Mnih et al. 2015; Van Hasselt, Guez, and Silver 2016) or policy gradient (Schulman et al. 2015, 2017) often get trapped in some confusing states because the state value they used is only evaluated by the reward. Since only a few states contain rewards, the agent cannot distinguish between those no-reward states, even if it have experienced them many times.

*Equal contribution, corresponding author. Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

(a) A person s social influence

(b) Traditional MDP model in RL

(c) State influence model

Focus state

Figure 1: (a) The social inﬂuence of one person in a social network. Three characteristics are often used to represent a person s social inﬂuence: 1) the size of the node indicates his conformity, 2) the blue dotted line indicates his power which is usually related to the number of connections within his group, and 3) the solid orange line indicates the authority, that is, how many followers a person has. The most inﬂuential person in a social network is called the focus. Similarly, we regard the states in (b) the traditional MDP model in RL as the nodes in (c) social network and obtain the focus state by measuring the states social inﬂuence. The focus state will be related to more states, and the exploration of it can accelerate the agent s cognition of the environment.

To deal with the hard exploration tasks with sparse rewards, many previous works try to imitate expert demonstrations (DQFD) (Hester et al. 2018) or their own successful experience (SIL) (Oh et al. 2018). In practice, however, expert demonstrations are often unavailable, and SIL focuses on the second stage, where the agent has already received local rewards. In the no-reward exploration stage, HER (Andrychowicz et al. 2017) randomly sets virtual goals from the experience replay buffer, regardless of which experience might be the most valuable. So it suffers from low sampling efﬁciency. To explore more meaningful directions, some researchers design intrinsic rewards based on the curiosity of states, where curiosity is measured by prediction errors (Pathak et al. 2017), reachability (Savinov et al. 2019) or pseudo-count (Bellemare et al. 2016). Although have achieved some success, they only consider the attributes of the state itself but ignore the relationships between states.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

But the human essence is no abstraction inherent in each single individual. In its reality it is the ensemble of the social relation (Marx and Engels 1969). Social inﬂuence refers to the change of a person s behavior after an interaction with other people or organizations. It consists of the process by which the individual opinions can be changed by the inﬂuence of another individual or other individuals (Friedkin 2006). Based on these considerations, when estimating the value of a state in RL, it s better to consider the relationship with other states besides its own attributes. Inspired by the concept of social inﬂuence in the social networks analysis community (Friedkin 2006), we regard each state as an individual, the relationship between states as a link in social networks, and the exploration process as a series of accesses to the opinion leader states (Figure 1). A general intrinsic reward construction method is thus introduced to measure the social inﬂuence of states dynamically, which is termed as Social Inﬂuence (SI) based intrinsic reward function. It comprises three kinds of social attributes: conformity, power, and authority. In particular, the conformity measures how often a state is visited, the power measures the relations with its former states in the MDP process, and the authority measures the relations it might have with its followers. By evaluating these social attributes of states, the agent can ﬁnd the focus state and exploit this information to accelerate the exploration process. We form a general RL framework using this SI-based intrinsic reward function. The new RL framework applies to both value based RL algorithms like DQN (Mnih et al. 2015), Dueling DQN (Wang et al. 2016), policy gradient based RL algorithms like PPO (Schulman et al. 2017), TRPO (Schulman et al. 2015), and the hybrid one like A3C (Mnih et al. 2016). For a series of hard exploration tasks like Grid Maze and Montezuma s Revenge, we develop corresponding learning algorithms based on the proposed RL framework. The results demonstrate that, with the introduction of social inﬂuence, all the evaluated algorithms signiﬁcantly improve their learning efﬁciency and quickly accomplish the goal of each task. In speciﬁc, on the Grid Maze game, the proposed method distinctly reduces the total exploration steps compared with the classical Q-learning based method. On the Montezuma s Revenge, compared with existing algorithms, the proposed method converges faster and obtains higher scores. To summarize, the main contributions of this work are listed as follows in threefold:

We point out that in the no-reward exploration stage, it is not enough to deﬁne intrinsic rewards based on the attributes of the state alone. The relationship between different states is introduced as a new part of intrinsic rewards. According to the measurement of individual social inﬂuence in social network analysis, a generalized intrinsic reward function is deﬁned for each state, including the attributes of the state itself and the relationships between the state and others. A new RL framework of SI-based intrinsic reward function is proposed and applied to Q-learning and A2C to improve the performance in some hard exploration games.

The source code, trained models, and all the experimental results will be released to facilitate further studies on reinforcement learning in hard exploration tasks.

Background To expatiate the proposed intrinsic motivation model, we ﬁrst introduce some background knowledge on basic reinforcement learning, intrinsic reward, and social inﬂuence. Basic RL. The standard RL formulation involves an agent interacting with an environment. An MDP is a tuple M = S, A, R, T, γ , consisting of a set of states S, a set of actions A, a reward function R : S A R, a transition probability model T(st+1, rt+1|st, at), and a discount factor γ [0, 1]. A policy π maps a state to an action, π:S A. An episode starts with an initial state s0, and at each timestamp t, the agent chooses an action at=π(a|st) based on the current state st. The environment produces a reward rt+1 to the agent, which reaches to next state st+1 sampled from the distribution T(st+1, rt+1|st, at). The reward might be discounted by a factor γ at each timestamp, and the goal of the agent is to maximize the accumulated reward,

k=0 γk Rt+k+1. (1)

Intrinsic reward. Intrinsic rewards become critical when extrinsic rewards are sparse (Pathak et al. 2017). They guide the agent based on the change in prediction error or learning progress (Bellemare et al. 2016; Schmidhuber 1991; Oudeyer, Kaplan, and Hafner 2007). If en(A) is the error made by the agent at time n over some event A, and en+1(A) the same one after observing a new piece of information, then the learning progress is en(A) en+1(A). To further quantify the learning process, researchers provide an information gain related method to explain the intrinsic reward (Bellemare et al. 2016). At each timestamp, the agent is trained with the reward rt = et +βit, where et is the extrinsic reward provided by the environment, it is the intrinsic reward generated by the agent, and β > 0 is a scalar balancing between the intrinsic and extrinsic rewards (Taiga et al. 2020). The overall optimization problem solves the following Bellman equation,

V (s) = max a A[et + βit + γEπ[V (s )]]. (2)

Social inﬂuence. In social network analysis, social inﬂuence of a node is often characterized by three main features (Friedkin 2006): 1) conformity, that occurs when an individual expresses a particular opinion in order to meet the expectations of a given other, though he/she does not necessarily hold the belief that the opinion is appropriate; 2) power, that is the ability to force someone to behave in a particular way by controlling his/her outcomes; and 3) authority, that is the power that believed to be legitimated by those who are subjected to it.

The Model There are two main obstacles in the process of exploring a sparse reward environment. The ﬁrst obstacle comes from

the vast state space. The other one comes from the uncertainty across states. Too many non-reward states and unknown transitions between states cause great confusion to agents and slow down the exploration process. Figure 1(b) is a simple example that regards state as the node and transition as the edge in a dynamic directed graph. When the number of states increases with the exploration process, the number of nodes in the graph increases and the number of possible edges also increases. This brings great trouble to the exploration task. Social networks can also be modeled by dynamic graphs (Figure 1(a)). However, as the population size increases, it can quickly ﬁnd an effective way to spread information without confusion from the uncertainty. This beneﬁts from the efﬁcient utilization of the focus person and the modeling of the relationship between persons. Based on these observations, we introduce the concepts from the social network into the process of exploring to narrow the exploration space and reduce the uncertainty. Intuitively, as the exploration task shown in Figure 1(c), if you want to explore state S8, you must have a corresponding state S6 appeared. Whether the arrival and re-exploration of a state are instructive to the policy improvement not only relates to the current state itself but also how to reach the state and how much potential the state can get in the future. The exploration process thus can not just be summarized as explore what surprises the agent as most previous methods did. It should take exploit what inﬂuences the environment into account. Just like the focus person in the social network in Figure 1(a), his importance to information broadcasting not only relates to his conformity (occurrence frequency), but also his power and authority (connections with other people). Therefore, we give a more reasonable formulation of intrinsic reward according to the concepts in social inﬂuence analysis, which consists of the state s characteristics and the relationship between states.

State Inﬂuence Deﬁnition 1 (Conformity function) We deﬁne the conformity function on the state space S, f C : S R mapping the state to a conformity level. si, sj S, if f C(si) < f C(sj), we say state sj is visited more often than state si. In the study of social network, conformity indicates that the opinion of an individual is the same as that of the majority of people, or whether the opinion of the individual is expected by the public. In the exploration task of RL, we regard each state encountered as an individual and its visited characteristics as opinions. The conformity function f C measures how often a state is visited. In social networks, the focus person will not blindly follow others, which means, less conformity. Meanwhile, in our exploration problems, we should avoid accessing the already familiar states. In the episodic RL, we formalize the conformity as

f C(si) := p(si). (3)

Deﬁnition 2 (Power function) We deﬁne the power function f P on the state space S, f P : S R, and it maps the state to a power level. si, sj S, if f P (si)<f P (sj), we say that there are more states which can lead the agent to state sj than to si.

Powerful person inﬂuences society by controlling other people s labor or information output and the power is the embodiment of compulsion. In this paper, we deﬁne the power of a state as how many states must achieve the ultimate goal through information exchange with the current state. The power function measures the relationship among states, which can be regarded as a structure of the partially explored environment. In episodic RL, we formalize the power function as

f P (si) := Z

sk Sp p(si|sk)dsk, (4)

where the Sp is the states set which appear before si.

Deﬁnition 3 (Authority function) We deﬁne the authority function on the state space S, f A:S R mapping the state to an authority level. si, sj S, if f A(si) < f A(sj), we say that state sj can lead to a more diverse state space, i.e., having more states followed.

A person should inﬂuence more communicators through his authority . It is necessary for individuals to shape their own information and then inﬂuence others. We deﬁne the authority of state as the inﬂuence of the absence of one state on other states The authority function measures another kind of relationship among states, which indicates how many future states can be reached from a speciﬁc state. In episodic RL, we formalize the authority function as

f A(si) := Z

sk Sa p(sk|si)dsk, (5)

where the set Sa contains states after state si in the currently known trajectory. Combined the three functions, the Social Inﬂuence (SI) based intrinsic reward function can be represented as:

i SI(s) Ψ(f C(s), f P (s), f A(s)), (6)

where Ψ can be a function with parameters or a task related deterministic function. With these characteristics to describe the social inﬂuence of states, we combine the SI-based intrinsic reward function with the extrinsic reward et(s) to evaluate the reward, rt = et + βi SI t , where β is a balancing factor between the extrinsic environment value et and the proposed instinct reward i SI(s). In all the evaluations conducted in experiment part, β is experimentally set to 1. And then, in substitution of traditional formulation Gt in Equation 1, we evaluate the SI-based accumulated reward by

k=0 γk(β i SI(St+k+1)+ e(St+k+1)), (7)

where 0 < γ < 1 is the discount factor. According to GSI(St), we propose SI-based value function, which evaluates the expectation of the total value of a state St following current policy π.

V SI π (St)=Eπ[GSI(St)|St = s]

k=0 γk(β i SI(St+k+1)+e(St+k+1))]. (8)

Algorithm 1 SI-based RL framework

1: Initialize policy π0, exploration steps k0, and expansion interval δ. 2: while not done do 3: Generate M trajectories in local environment by πi. 4: Evaluate i SI(s) of the known state by i SI(s) = Ψ(f C(s), f P (s), f A(s)). 5: while πi not convergence do

6: Update πi using reward rt = et + βi(SI) t with an RL algorithm, e.g., Eqn. (9) or Eqn. (10). 7: end while 8: Expand the scope of exploration by increasing ki+1 = ki + δ. 9: if Agent get local rewards then 10: Any local-reward exploitation stage algorithms will be used. 11: end if 12: end while

Compared with the deﬁnition of the traditional V (s) in Section , V SI(s) preserves extrinsic reward e(s) and introduces intrinsic rewards i SI(s). This form of V (s) can give general guidance without arriving at the reward state, which makes it an effective attempt to overcome the hard situation with no reward. Moreover, it inherits the characteristics of i SI(s), measures the structural information of the environment through the relationships between states, and its evaluation of state value is more instructive to the exploitation in the exploration process. It provides a generalized intrinsic rewarding mechanism for hard-exploration tasks in sparse reward environments and can be integrated with different RL algorithms. We will describe its iterative nature in the following and incorporate it into the traditional Q-learning and A2C frameworks.

SI-based RL Framework

The social inﬂuence based value function can be embedded into any RL algorithm that involves value iteration. The key idea of the SI-based RL framework is that an agent utilizes the current i SI(s) and π to explore a desired part of the environment, progressively broaden the exploration scope, and update the social inﬂuence of states in turn with newly acquired information about the environment. This process is iteratively advanced until the agent ﬁnds the target or receives extrinsic reward signals. Algorithm 1 shows the detail of SIbased RL framework. The main advantages are in twofold: 1) RL framework with i SI(s) expands the agent s horizon incrementally, shown in Step 8 in Algorithm 1; and 2) the evaluation function V SI(s) contains not only the reward but also the structure information among states, shown in Eqn. (8). With the ﬁrst advantage, agents can gradually explore the unknown environment and get sub-optimal solutions in each local context. With the second one, the agent can exploit the intrinsic state relationships even though there are no reward signals. In this way, the agent obtains a reasonable explore direction before getting a reward in the hard exploration environment. We incorporate it into the traditional RL algorithms to construct different SI-based RL algorithms, such as SI-based Qlearning and A2C. Applying i SI(s) to traditional value based methods, such

as Q-learning, we get the update formula:

QSI π =Eπ[GSI(St)|St = s, At = a]

s ,r T(s , r|s, a)[βi SI(s )+e(s )+γV SI π (s )]. (9)

State inﬂuence can also accelerate the exploration process of policy gradient based methods, such as AC. When apply to the One-step Actor-Critic, the parameters update rule is as follows:

θt+1= θt+α(GSI t:t+1(St) ˆV SI(St, η)) π(At|St, θt)

π(At|St, θt)

= θt+αδt π(At|St, θt)

π(At|St, θt) , (10)

where ˆV SI(St, η) is the evaluation of SI-based value function and

δt=GSI t:t+1(St) ˆV SI(St, η)

=βi SI(St+1)+e(St+1)+γV SI π (St+1) ˆV SI(St, η). (11)

Connections to Other Intrinsic Motivation Methods The state inﬂuence modeling is a generalization of the existing intrinsic reward construction methods. For example, the ˆ Nt in pseudo-count (PSC) (Bellemare et al. 2016) is a kind of conformity, and the core idea of the curiosity algorithm is to avoid large conformity. They formalize the intrinsic reward as i P SC(st) ( ˆNt(st)) 1/2. If we ignore power and authority, assume that all states are independent, and deﬁne our conformity as f C(si) ( ˆNt(st)) 1/2, i SI(s) will degenerate to pseudo-count in (Bellemare et al. 2016). Similarly, both i ICM(s) (Pathak et al. 2017) and i RND(s) (Burda et al. 2019) are constructing curiosity by modeling the relationship between the current state si and the next state si+1, where they formulize the intrinsic reward as i ICM(st) ||ˆΦ(st+1) Φ(st+1)||2 2 and i RND(st) || ˆf(st; θ) f(st)||2 2 (the ˆΦ( ) and ˆf( ) are estimation of states by a trained model). Comparing with Deﬁnition 6, ICM or RND is just the special case of the State Inﬂuence. In general, to achieve the sparse goal, agents should ﬁght against the uncertainty of both environment and policy.

(a)Mini Maze (b) Conformity (c) Power (d) Authority (e) State influence

Figure 2: (a) Mini Maze. Visiting the focus states 15 and 17 can accelerate the agent s awareness of the environment because they contain more structure information. From the results calculated by 1, 000 random explorations with 20 steps at each episode, only the conformity in (b) might not well represent the structure of the environment. Combining with the power (c) and the authority (d), the focus state found in (e) is more consistent with the actual situation.

Since each exploration of a state will reduce its uncertainty, almost all intrinsic motivation methods are committed to improving the information gain of each encountered state. Only in this way can the uncertainty space be reduced faster and the goal be achieved. Most of the previous methods (Bellemare et al. 2016; Burda et al. 2019; Pathak et al. 2017) only pay attention to the novelty of a single state, while our state inﬂuence modeling reduces the uncertainty through both the state s attributes and the relationships between states. We will show the signiﬁcant performance improvement of our methods in the following.

Experiments To verify the efﬁciency of SI-based intrinsic reward i SI(s) and the proposed SI-based RL algorithms, we conduct three sets of experiments with corresponding analyses.

State inﬂuence in the Mini Grid Maze: shows the necessity and the different roles of the various intrinsic potential signals of i SI(s) SI-based Q-learning in Grid Maze: applies the SI-based Q-learning algorithm directly to solve the hard exploration problem in the Grid Maze. SI-based A2C in Atari games: extends i SI(s) and SIbased A2C to the Atari games, and shows the efﬁciency of proposed framework compared with baseline algorithms.

State Inﬂuence in Mini Grid Maze We use a toy example shown in Figure 2 to illustrate the motivation for introducing social inﬂuence into the intrinsic rewards. The Mini Maze environment is a small maze with 6 6 states, encoded as 1 to 36 from left to right, top to bottom. The structure of the environment is constructed by several impassable black holes. Assuming that all states in the environment have no reward, its state space be regarded as a limited discrete one without reward. An agent starts from the beginning state in the top left corner shown in the Figure 2a. The action space is { left , right , up , down }, and the transition limited by the walls and holes. The set of trajectories is noted as T, and the i-th trajectory as Ti = {(sij, aij)}, where the sij S, aij A, i {1, 2, , M}. In frequency statistics, the ith trajectory have Wi states, the ﬁrst visit of state Si is noted as uiwit, the wit is the order of state in this trajectory,

wit N +, 0 < wit < Wi. The sort of states that ﬁrst visit in this trajectory is Ui = {ui1, , uiwit, , ui Wi}, where uiwit S. Meanwhile, the number of times each state appears in Ti is Ci = {ci1, , ciwit, , ci Wi}, where, ciwit N +. The appearing order of state Sk in trajectory Ti is wik, and we denotes the number of all the states currently known as N. According to each component of social inﬂuence mentioned before, we use the total number of visits to states to indicate the conformity function (3) of discrete states f C(Sk) PM i=1 ciwik/N. And we use the number of states appear before Sk in each trajectory to deﬁne the power function (4), f P (Sk) PM i=1 Pwik 1 j=1 cij/N. In terms of the expressions of social inﬂuence from and to other states, this deﬁnition can be more complicated. Though this is the simplest, it will be helpful to the conduction of the following work. Similarly, we deﬁne the number of visited states Sk in each trajectory after Sk as the measurement of authority function (5) of state, f A(Sk) PM i=1 PWi j=wik+1 cij/N. Heatmaps of conformity, power, authority, and their combination are shown respectively in Figure 2. The blue heatmap (b) is the number of states that occur, as the counts in the count-based method, which is the simplest form of conformity. It is obviously not enough to evaluate the properties of states. We can see that the green (c) and orange (d) implementation in the ﬁgure can bring us more information. From the perspective of statistical information in Figure 2c, state 15 has strong power, and more information on state must be transmitted through it, which can be used as the focus state in the local area. To illustrate the effectiveness of social inﬂuence, we also combine the three attributes in the form (f P (s) + f A(s))/ p

f C(s). The results are shown in Figure 2 (e), from which we can say that state 17 is the most inﬂuential state. It can also be seen from Figure 2 (a) that node 15 and 17 are the focus state of the environment, which could improve exploration efﬁciency. This is an environment without any reward. Now we apply i IS(s) to the sparse reward environment.

SI-based Q-learning in Grid Maze

In Grid Maze, a frequency-based form is detailed to show the feasibility of the Social Inﬂuence based intrinsic reward function i SI(s). We deﬁne the i SI(s) used in this discrete

(a) Grid Maze

(b) SI Q-learning

(c) Q-learning

Figure 3: (a) Grid Maze is a 20 20 maze with random holes and a reward in the bottom right corner. Examples of some focus states during the local exploration process are represented by the numbers within the circles. (b) Steps in each episode and total steps by SI Q-learning. The enlarged gray area shows the process of gradual exploration. (c) Steps in each episode and total steps by Q-learning.

environment as:

s = argmaxs f P (s) + f A(s) p

f C(s) , (12)

i SI(s) = 1 , if s = s , 0 , else. (13)

The basic principle of constructing SI value is proportional to power and authority, and inversely proportional to conformity. As for the dominator of Eq. (12), we follow the count-based method (Bellemare et al. 2016; Pathak et al. 2017) for intrinsic reward construction. As for the numerator, we set the two terms have equal importance. Although much better results can be obtained by searching different conﬁgurations of these three terms, we found Eq. (2) already works well in the experiments. To verify the generality of the algorithm in a direct and straightforward way, we do not set the scaling factor in this experiment. By introducing the generalized intrinsic reward signals i SI(s), we apply SI Qlearning to a sparse reward Grid Maze. We also compare SI Q-learning with the traditional Q-learning to illustrate the feasibility and the efﬁciency of our framework. To illustrate the progressive exploration, we show several representative states in Figure 3(a). They are focus states of local stabilization policy before the agent gets any extrinsic reward. And we can see the staged exploration in Figure 3(b). In Figure 3(b), we zoom in on the curve before we get the reward, which is the gray part of the graph. In the gray part, the steps of each episode grow up along with the expanding of exploration scope in each state of Figure 3(a). Combining Figure 3(a) with Figure 3(b), it can be seen that since we integrate the social inﬂuence into intrinsic reward, our SI-based Q-learning can give a reasonable exploration direction before getting rewards. Therefore, we can also reduce the total exploration steps. A comparison between Figure 3(b) and Figure 3(c) illustrates this advantage. Figure 3(b) and Figure 3(c) respectively show the total training steps of SI Q-learning and Qlearning in the orange curve. The SI Q-learning gradually expands the scope of exploration and converges in about 75,000 steps, compared to the Q-learning, which converges in about 90,000 steps. These results show that the introduction of the SI based intrinsic reward function i SI(s) can effectively deal with the hard exploration tasks.

SI-based RL in Atari Games

To verify the efﬁciency and generalization ability of the proposed method, we apply i SI(s) to some hard exploration Atari games like Montezuma s Revenge, Gravitar, Freeway and so on. These games are generally considered as a notoriously difﬁcult games in Atari games (Van Hasselt, Guez, and Silver 2016). For example, Montezuma s Revenge has three levels, each level has 24 different rooms, the agent navigate through different rooms to collect treasures. Here, we treat the coding of original frame as the state, and the state space is gradually increased along with the exploration. The action consists of 17 movements, such as up, down, jump, etc. In the Atari experiments, we convert the 210 160 input RGB frames to grayscale images and resize them to 42 42 images following the practice in (Tang et al. 2017; Bellemare et al. 2016). The position of the agent is then discretized into a state in 42 42, and we set the i SI(s) with the same settings in Eqn. (12) and Eqn. (13). To compare the proposed SI-based A2C with the countbased A2C (Bellemare et al. 2016) on the ﬁrst no-reward exploration stage of the sparse reward problem, we use the ﬁrst room of Montezuma s Revenge as the experimental environment in Figure 4. We can see that the point with the highest heat in each stage are the points that the agent must explore to pass the ﬁrst room. They can assist the agent to exploit what inﬂuences the environment . According to the results shown in Figure 5(a), SI-A2C converges to the local goal in fewer training steps. This proves that the integration of relationship evaluation in social inﬂuence helps ﬁnd the focus states. It is more effective to explore the focus states than only to explore the state with few visits, and SIbased A2C can get the reward in the environment faster as the green curve shown in Figure 5(a). For the Montezuma s Revenge is a game with many rooms, it is a good example of multi-phase exploration. As shown in the Figure 5(a), after completing the ﬁrst stage of exploration (about 2000 points average rewards have been obtained), our SI-based method also experiences a period of rest period (at about 20M to 28M steps). With the continuous increase of exploration scope (the 8th step in the Algorithm 1), our algorithm can quickly form the exploration advantage in the next stage. In contrast, the Count-based A2C will stay in the rest period for a long time. This shows that

(a) Montezuma's Revenge (b) 1st stage (c) 2nd stage (d) 3rd stage

Figure 4: Heatmap of state inﬂuence in Montezuma s Revenge. The state inﬂuence changes with the expand of the horizon of exploration. (b), (c) and (d) are heatmaps sampled from the ﬁrst stage (max 500 steps per trajectory), the second stage (max 1000 steps per trajectory) and the third stage (max 1500 steps per trajectory) respectively.

(a) Montezuma s Revenge

(b) Venture

(c) Private Eye

(d) Gravitar Figure 5: Learning steps are compared with baseline algorithms in Montezuma s Revenge, Venture, Private Eye and Gravitar. The x axis is the number of steps. For the convenience of comparison, we limit the exploration steps of all games to 50 million steps. The y axis is the mean episodic rewards in each game. The results are averaged by 5 runs. These games are selected because they are all sparse reward games. The green curve represents SI-based algorithm s performance, in contrast to the red curve that only uses the Count-based method, and the blue cure represents the basic A2C which cannot get much performance.

our algorithm can effectively guide the agent to complete more valuable exploration without the extrinsic reward. In the performance of the other games, such as Venture in the Figure 5(b), Private Eye in the Figure 5(c) and Gravitar in the Figure 5(d), it also proves that our algorithm can help agents get better results faster than the baselines. We further compare our proposed method with other baseline algorithms: Sim Hash (Tang et al. 2017), Curiosity Driven Exploration (ICM) (Pathak et al. 2017), Exploration with Mutual Information (EMI) (Kim et al. 2019), Count-based method(A3C+) (Bellemare et al. 2016) and A2C (Mnih et al. 2016) on four exploration games Montezuma s Revenge(MR), Gravitar(Gvt), Freeway(Fw) and Venture(Vt), and four games which are not sparse reward environment, Berzerk(Bz), Jamesbond(Jb), Enduro(Ed), and Zaxxon(Zx). Table 1 shows performance comparison of the proposed SI-based A2C and baseline methods. Our method achieves better results on most of the Atari games. The experimental results show that i SI(s) makes the learning process faster, and enable agents to explore further in the hard exploration tasks.

Conclusion and Future Work In this work, we introduce a social inﬂuence based intrinsic reward function to reinforcement learning in hard exploration tasks with sparse rewards. This deﬁnition effectively complements existing essential reinforcement learning solutions. We use i SI(s) on the value function-based and pol-

MR Gvt Fw Vt Bz Jb Ed Zx

Sim Hash 75 482 33 445 - - - - ICM 1011 424 34 418 - - - - EMI 387 558 34 646 - - - - RND 3442 1348 34 1258 - - - - A3C+ 2551 284 30 361 - - - - A2C 6 329 0 0 1203 399 0 124

SI-A2C 5342 1451 34 783 1559 1996 60 8602

Table 1: Performance in Atari games of the SI-based A2C and baseline methods from the original papers. indicates the non-reported corresponding data. The results are averaged by 5 runs with diverse random seeds in 50M steps.

icy gradient based RL algorithms. In the Grid Maze with many obstacles and only one reward signal, our experimental results show that owing to i SI(s), the agent has a reasonable exploration direction before it gets a reward. Based on the SI based RL framework we proposed, the experience is collected in a gradually expanding way. Thus, the agent can explore and recognize the environment incrementally. Finally, by applying the proposed framework to some hard exploration Atari games, the results show that the algorithms combining with i SI(s) achieve the task objectives in fewer exploration steps than the baseline algorithms. We just focus the no-reward exploration stage in this paper, the localreward exploitation stage will be considered in the future.

Acknowledgments This work was supported in part by the Natural Science Foundation of China under Grant No. 62076238 and 61902402, in part by the National Key Research and Development Program of China under Grant No. 2019AAA010340X, in part by the CCF-Tencent Open Research Fund under Grant No. RAGR20200104, and in part by the Strategic Priority Research Program of Chinese Academy of Sciences under Grant No. XDA27000000.

References Andrychowicz, M.; Wolski, F.; Ray, A.; Schneider, J.; Fong, R.; Welinder, P.; Mc Grew, B.; Tobin, J.; Abbeel, O. P.; and Zaremba, W. 2017. Hindsight experience replay. In Advances in Neural Information Processing Systems, 5048 5058. Bellemare, M.; Srinivasan, S.; Ostrovski, G.; Schaul, T.; Saxton, D.; and Munos, R. 2016. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, 1471 1479. Burda, Y.; Edwards, H.; Storkey, A.; and Klimov, O. 2019. Exploration by Random Network Distillation. In International Conference on Learning Representations, 1 17. Friedkin, N. E. 2006. A structural theory of social inﬂuence, volume 13. Cambridge University Press. Hester, T.; Vecerik, M.; Pietquin, O.; Lanctot, M.; Schaul, T.; Piot, B.; Horgan, D.; Quan, J.; Sendonaris, A.; Osband, I.; et al. 2018. Deep Q-learning from demonstrations. In AAAI Conference on Artiﬁcial Intelligence, 3223 3230. Kim, H.; Kim, J.; Jeong, Y.; Levine, S.; and Song, H. O. 2019. EMI: Exploration with Mutual Information. In International Conference on Machine Learning, 3360 3369. Marx, K.; and Engels, F. 1969. Theses on Feuerbach, 1888. It is available at http://www. marxists. org/archive/marx/works/1845/theses/theses. htm . Mnih, V.; Badia, A. P.; Mirza, M.; Graves, A.; Lillicrap, T.; Harley, T.; Silver, D.; and Kavukcuoglu, K. 2016. Asynchronous Methods for Deep Reinforcement Learning. In International Conference on Machine Learning, 1928 1937. Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; et al. 2015. Human-level control through deep reinforcement learning. Nature 518(7540): 529. Oh, J.; Guo, Y.; Singh, S.; and Lee, H. 2018. Self-imitation learning. In International Conference on Machine Learning, 3875 3884. Oudeyer, P.; Kaplan, F.; and Hafner, V. V. 2007. Intrinsic Motivation Systems for Autonomous Mental Development. IEEE Transactions on Evolutionary Computation 11(2): 265 286. Pathak, D.; Agrawal, P.; Efros, A. A.; and Darrell, T. 2017. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, 2778 2787.

Savinov, N.; Raichuk, A.; Vincent, D.; Marinier, R.; Pollefeys, M.; Lillicrap, T.; and Gelly, S. 2019. Episodic Curiosity through Reachability. In International Conference on Learning Representations, 1 20. Schmidhuber, J. 1991. A possibility for implementing curiosity and boredom in model-building neural controllers. In International Conference on Simulation of Adaptive Behavior: From Animals to Animats, 222 227. Schulman, J.; Levine, S.; Abbeel, P.; Jordan, M.; and Moritz, P. 2015. Trust region policy optimization. In International Conference on Machine Learning, 1889 1897. Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017. Proximal policy optimization algorithms. ar Xiv preprint ar Xiv:1707.06347 . Taiga, A. A.; Fedus, W.; Machado, M. C.; Courville, A.; and Bellemare, M. G. 2020. On Bonus Based Exploration Methods In The Arcade Learning Environment. In International Conference on Learning Representations, 1 20. Tang, H.; Houthooft, R.; Foote, D.; Stooke, A.; Chen, O. X.; Duan, Y.; Schulman, J.; De Turck, F.; and Abbeel, P. 2017. # Exploration: A study of count-based exploration for deep reinforcement learning. In Advances in Neural Information Processing Systems, 2753 2762. Van Hasselt, H.; Guez, A.; and Silver, D. 2016. Deep reinforcement learning with double Q-learning. In AAAI Conference on Artiﬁcial Intelligence, 2094 2100. Wang, Z.; Schaul, T.; Hessel, M.; Van Hasselt, H.; Lanctot, M.; and De Freitas, N. 2016. Dueling Network Architectures for Deep Reinforcement Learning. In International Conference on Machine Learning, 1995 2003.