Safe and Sample-Efficient Reinforcement Learning Algorithms for Factored Environments

1 Model-based Exploration in RL

To find the optimal policy quickly, the R-max algorithm [Brafman and Tennenholtz, 2002] incentivizes the agent to explore unknown parts of the environment in early stages of the learning process. To do so, it keeps track of a set of stateaction pairs considered known:

where n(s, a) is the number of times the agent has applied action a in state s, and m is a threshold to consider a stateaction pair known.

Often, the state space S can be represented by a set of state factors X = {X1, · · · ,X|X|} where each factor has a domain Dom(Xi). When these factors are highly independent, a Factored MDP (FMDP) can compactly represent an MDP, using a dependence function D : S ×A×X → I that indicates the commonalities among different factors, where I is a set of dependency identifiers [Strehl, 2007]. The probabilistic transition function can be compactly represented:

where s′i is the value of Xi in the next state s′ .

The factored R-max algorithm is a direct extension of Rmax for FMDPs [Guestrin et al., 2003]. It maintains an estimate of each transition component distribution and decides which state-action pairs are known or not according to these estimates. This algorithm only considers as known parts of the environment where the estimate of all transition components have been experienced enough times. In particular, given a minimum number of samples for each factor ⃗m = 〈m1, . . . ,m|X|〉 and the counters of each transition component n(j), the set of known state-action pairs is constructed as follows:

2 Safe Policy Improvement

Safe Policy Improvement (SPI) addresses the question of how to compute a new policy π that outperforms the behavior policy πb with high confidence 1 - δ, given a batch of previous interactions D and an admissible error ζ.

The SPI by Baseline Bootstrapping (SPIBB) framework is a model-based approach that guarantees safety by bootstrapping unknown parts of the approximated model with the behavior policy πb [Laroche et al., 2019]. Formally, the set of bootstrapped state-action pairs Bm is the complement of the set Km (1). This way, the SPIBB algorithms guarantee to perform at least as well as the behavior policy and do not rely on a safety test, in contrast to other SPI algorithms.

The policy-based Πb-SPIBB algorithm attributes the same probability to bootstrapped pairs as the behavior policy, which restricts the policy space to

Laroche et al. [2019] prove that if m = 2 ϵ2 log |S||A|2|S| δ then the Πb-SPIBB algorithm is safe, where ϵ is a bound on the L1 distance between the estimated transition function and the true transition function, that depends on the precision parameter ζ.

The Πb-SPIBB algorithm can change the policy if a subset of the state-action pairs is well known, therefore it ca be less conservative than other SPI algorithms. Nevertheless, when the problem is described by a set of factors, m grows exponentially in the number of factors. In the next section we show that, by taking in account the independence between features, it is possible to exploit the factored representation of the problem using a minimum number of samples that is only polynomial in the number of parameters of the FMDP.

3 Main Contributions

To exploit the structure of an FMDP we proposed the Factored Πb-SPIBB algorithm, an adaptation of Πb-SPIBB algorithm for factored environments [Sim˜ao and Spaan, 2019]. This algorithm takes an extra input: the dependency function D that determines which transition components must be estimated.

First, the algorithm estimates each transition component according to D using the same counters as the factored Rmax algorithm. Second, it redefines the set of state-action pairs to be bootstrapped B⃗m as the complement of the set of known state-action pairs K⃗m (2). In this way, given B⃗m and the behavior policy πb, the constrained policy space Πb can be computed using (3). Finally, the algorithm searches for an optimal policy in Πb, however, in this case the transition function ˆ T(· | s, a) is estimated according to the estimate of each transition component.

The theoretical analysis shows that it is possible to bound the probability that the Factored Πb-SPIBB algorithm computes a policy worse than the behavior policy. To do so it is necessary to define ⃗m such that

Therefore, given a desired ϵ, the term |A||S| is replaced by |Q| and |S| is reduced to |Dom(Xi)|. This comes at the lower cost of adding a term polynomial in the number of variables |X|2 (necessary to bound the error of each component distribution). In domains where the features are highly independent from each other these results reduce significantly the number of samples necessary to improve the behavior policy.

Next, we relax the assumption that the dependency function D is known a priori, by proposing the Structure Learning Πb-SPIBB that integrates different structure learning algorithms [Diuk et al., 2009; Strehl et al., 2007] in the SPIBB framework.

The empirical analysis shows a large difference in the number of samples necessary to change the behavior policy of flat SPI algorithms and their factored counterparts. In the SysAdmin domain (Figure 1), the Factored Πb-SPIBB algorithm manages to compute policies better than the behavior policy given batches with only 100 trajectories, in contrast to the Πb-SPIBB algorithm, that only shows improvement when |D| ≥ 2000. Finally, we find that even without the prior knowledge about the dependency function D, the Factored Πb-SPIBB algorithm equipped with the structure learning kmeteorologists algorithm can also exploit the independence between features, finding improved policies with 1000 trajectories.

4 FutureWork

Some directions for future work include: extension of other model-based safe RL methods to factored environments, such as the robust approach by Petrik et al. [2016]; exploitation of other types of structure in the SPIBB framework such as decision trees and relation between objects; and development of a general SPIBB framework to be applied under different assumptions of prior knowledge.

Mean Performance

Acknowledgments

This research received funding from the Netherlands Organisation for Scientific Research (NWO).