of ABP using common reinforcement learning benchmark problems. Technical proofs are provided in the appendix.

The general setting considered in this paper is a restriction of reinforcement learning.

Reinforcement learning methods can use samples without requiring a model of the environment. The methods we propose can also be based on samples, but they require additional structure. In particular, they require that all or most actions are sampled for every state. Such samples can be easily generated when a model of the environment is available.

## 2. Framework And Notation

This section formally defines the framework and the notation we use. We also define Markov decision processes and the approximation errors involved. Markov decision processes come in many flavors based on the objective function that is optimized. This work focuses on the infinite horizon discounted MDPs, which are defined as follows.

Definition 1 (e.g. (Puterman, 2005)). A *Markov Decision Process* is a tuple (S, A*, P, r, α*).

Here, S is a finite set of states, A is a finite set of actions, P : *S × A × S 7→* [0, 1] is the transition function (P(*s, a, s*0) is the probability of transiting to state s 0from state s given action a), and r : *S×A 7→* R+ is a reward function. The initial distribution is: α : *S 7→* [0, 1],
such that Ps∈S α(s) = 1.

The goal is to find a sequence of actions that maximizes γ-discounted discounted cumulative sum of the rewards, also called the *return*. A solution of a Markov decision process is a policy, which is defined as follows.

Definition 2. A deterministic stationary policy π : *S 7→ A* assigns an action to each state of the Markov decision process. A stochastic policy policy π : *S × A 7→* [0, 1]. The set of all stochastic stationary policies is denoted as Π and satisfies Pa∈A π(*s, a*) = 1.

General non-stationary policies may take different actions in states in different timesteps. We limit our treatment to stationary policies, since for infinite-horizon MDPs there exists an optimal *stationary* and *deterministic* policy. We also consider stochastic policies because they are more convenient to use in some settings that we consider.

The transition and reward functions for a given policy are denoted by Pπ and rπ. The value function update for a policy π is denoted by Lπ, and the Bellman operator is denoted by L. That is:

Lπv = Pπv + rπ Lv = max
$$\overline{{{\pi\in\Pi}}}$$
Lπv.

The optimal value function, denoted v
∗, satisfies v
∗ = Lv∗.

We assume a vector representation of the policy π ∈ R
|S||A|. The variables π are defined for all state-action pairs and represent policies. That is π(*s, a*) represents the probability of taking action a ∈ A in state s ∈ S. The space of all correct (stochastic) policies can be represented using a set of linear equations:

$$\sum_{a\in{\mathcal{A}}}\pi(s,a)=1$$ $$\pi(s,a)\geq0$$
π(*s, a*) = 1 ∀s ∈ S
π(s, a) ≥ 0 ∀s ∈ S, ∀a ∈ A
$$\forall s\in S$$
$$\forall s\in{\mathcal{S}},\forall a\in{\mathcal{A}}$$
