[RL] (Spinning Up) Key concepts in RL

(본 글은 OpenAI Spinning Up 글을 개인적으로 정리한 글입니다. 원본)

Part 1: Key Concepts in RL — Spinning Up documentation

Agent와 Environment간의 상호관계

 RL을 다루면 가장 많이 나오는 개념이 바로 Agent와 Environment라는 것이다. Environment는 Agent가 살고 있고, 그 안에서 Agent와 Environment간 상호 작용이 일어나는 세계를 나타낸다. 이렇게 매번 상호 작용이 발생할 때마다, Agent는 세계의 State에 대해서 부분적으로나마 관찰하게 될 것이고, 이에 대해서 취할 Action을 결정하게 된다. 이 때, Environment는 Agent의 Action이 작용하면 변할 수도 있고, 어쩌면 스스로 변화를 나타낼 수 있다. (보통 이런 것을 Environment Dynamics 라고 표현하기도 한다.) 

 이 때 Agent는 Environment로부터 Reward (\(r_{t}\))신호를 인지하게 되는데, 이 Reward는 현재 World의 State가 얼마나 좋은지 혹은 나쁜지를 표현해주는 척도가 된다. Agent의 목표라고 하면 바로 이렇게 누적된 reward를 최대화할 수 있도록 Action을 취하는 것이 될텐데, 이를 Return (\(G_{t}\))이라고 표현한다. 보통 강화학습을 한다라고 표현하는 것은 Agent가 이런 목표를 달성할 수 있도록 행동을 가르쳐주는 것이 의미를 두고 있다.

 RL이 어떤 일을 하는지 더 자세히 다루기 위해서, 몇가지 표현에 대해서 소개할 필요가 있다. 다음 글을 통해서
 - State와 Observation
 - action spaces
 - policies
 - trajectories
 - return에 대한 다른 공식들
 - RL 최적화 문제
 - value function
에 대한 설명을 할 예정이다.

State와 Observations

 State \(s\)는 앞에서 언급한 세계에서의 모든 상태를 나타내는 단어이다. 여기에서 벗어난 정보는 없다고 보면 된다. 반면 Observation \(o\)는 State를 부분적으로 표현할 것으로, 어떻게 보면 몇몇 정보는 빠져있다고 보면 된다. 

 Deep RL에서는 State와 Observation을 실수로 구성된 벡터나 행렬, 또는 고차원의 tensor의 형태로 나타낸다. 예를 들어 시각적으로 관찰되는 정보는 각각의 pixel값의로 구성된 RGB 행렬로 나타낼 수 있고, 로봇의 움직임은 로봇을 구성하는 관절의 각도와 속도로 관찰할 수 있는 것과 같은 것이다. 

 만약 Agent가 environment를 구성하는 모든 state를 관찰할 수 있다면, 해당 Environment를 Fully Observed이라고 표현하고, 일부분만 볼수 있다면 Partially Observed라고 표현한다. 

Action Spaces

 다양한 Environment에는 각각 나름의 action들이 존재한다. 이때 이 action들의 모든 경우의 수를 action space라고 부른다. Atari나 바둑과 같은 Environment는 discrete action space를 가지는데, 이는 agent가 취할 수 있는 action의 수가 한정적인(finite) 것을 말한다. 실생활에서 로봇을 제어하는 agent의 경우는 continuous action space를 가지는데, 이때 action은 보통 실수로 구성된 벡터의 형태로 나타난다. 

 이런 구별은 Deep RL 내에서도 적용 방법에 대한 약간의 중요한 영향을 미치는데, 어떤 알고리즘의 경우는 특정 경우에 대해서 바로 적용이 가능한 경우도 있지만, 어떤 경우에는 적용하기 위해서 재작업이 필요한 경우도 있다.

Policy

 Policy는 agent로 하여금 어떤 action을 취해햐 할지를 결정해주는 일종의 규칙과 같다. 이 규칙은 deterministic, 다시 말해서 딱 결정된 형태로 나올 수 있는데, 이때는 보통 \(\mu\) 를 사용해서 표현한다.

$$ a_{t} = \mu (s_{t}) $$

아니면 규칙은 stochastic (확률로 표현되는 형태) 일 수 있는데, 이때는 \(\pi\) 사용해서 표현한다.

$$ a_{t} \sim \pi(\cdot|s_{t}) $$

Policy라는 단어 자체의 의미가 agent의 brain을 나타내는 것이기 때문에, " 현재의 Policy는 reward를 최대화하려고 한다" 라는 표현과 같이 "agent" 입장에서 "policy"란 단어를 대체한 표현은 주변에서 많이 볼 수 있다.

 Deep RL에서는 Parameterized policy에 대해서 다루게 될텐데, 여기서 말하는 policy란 출력이 (신경망의 weight이나 bias와 같은) 일종의 parameter에 의해서 결정되는 함수의 형태로 나타나는데, 개발자는 특정 최적화 알고리즘을 통해서 함수의 동작을 조정할 수 있을 것이다.

 보통 특정 policy에 대한 parameter를 \(\theta\) 나 \(\phi\) 로 표현하고, 이 parameter와 함수간의 관계를 강조하기 위해서 policy symbol의 첨자형태로 쓴다.

$$ a_{t} = \mu_{\theta}(s_{t}) \\ a_{t} \sim \pi_{\theta}(\cdot|s_{t}) $$

Deterministic Policies

 간단하게 Tensorflow로 구현한 continuous action space에 대한 deterministic policy 코드는 다음과 같다.

obs = tf.placeholder(shape=(None, obs_dim), dtype=tf.float32)
net = mlp(obs, hidden_dims=(64,64), activation=tf.tanh)
actions = tf.layers.dense(net, units=act_dim, activation=None)

 여기서 mlp는 주어진 node 크기와 activation function (여기서는 tanh 함수)로 구성된 dense 계층 여러개로 구성된 함수를 의미한다.

Stochastic Policies

 Deep RL에서 가장 많이 언급되는 Stochastic Policy 두가지는 Categorical policy와 Diagonal Gaussian policy이다. Categorical policy는 discrete action space를 가지는 환경에서 사용되고, diagonal Gaussian policy는 Continuous action space를 가지는 환경에서 사용된다.

 이런 stochastic policy를 사용하고 학습시키는데 있어, 두가지 핵심 동작은 다음과 같다.

 - policy로부터 action을 sampling하는 것
 - 그리고 \(\log \pi_{\theta}(a|s) \)라는 식을 통해 특정 action에 대해 log likelihood를 계산하는 것

아래의 설명을 통해 categorical policy와 diagonal Gaussian policy가 어떻게 다른지를 언급해보고자 한다.

Categorical Policies
 categorical policy는 discrete한 action에 대한 classifier와 같다. 그래서 categorical policy에 대한 신경망을 만들때는 classifier를 만들때와 동일하게 만들면 된다: 이때의 입력은 observation이 되고, 뒤이어 몇몇 계층이 붙게 된다. ( 아마 입력의 종류에 따라서 convolutional이거나 densely connected 계층이 될 것이다.) 그런 후에 각 action에 대한 logit를 보여줄 수 있는 출력 계층이 하나 있을 것이고, 마지막으로 각 logit들을 확률로 변환시켜주는 softmax 가 activation function으로 붙게 될 것이다.

 Sampling : 각 action에 대한 확률이 주어졌을때, Tensorflow와 같은 framework에서는 sampling을 위한 내장 함수들을 가지고 있다. 관심이 있으면 tf.distributions.Categorical 이나 tf.multinomial 문서를 참조해보면 좋을것 같다.

 Log-Likelihood : 마지막 출력 계층의 확률을 보통 \(P_{\theta}(s)\)라고 표현하는데, 이는 수많은 action들로 구성된 vector형태로 존재한다. 이 action의 갯수가 많기 때문에, 보통 vector에 대한 index를 action으로 치환해서 사용하기도 한다. 결론적으로 action \(a\)에 대한 log likelihood는 vector에 대해서 indexing을 함으로써 얻어낼 수 있다.
$$ \log \pi_{\theta}(a|s) = \log[P_{\theta}(s)]_{a} $$

Diagonal Gaussian Policies
 Multivariate Gaussian Distribution (또는 multivariate normal distribution)는 mean vector \(\mu\)와 covariance matrix \(\Sigma\) 로 표현된다. diagonal Gaussian distribution은 covariance matrix가 diagonal에만 요소를 가지고 있는 특별한 경우를 말하며, 결론적으로 말하자면 이를 vector 형태로 나타낼 수 있다.

 Diagonal Gaussian policy는 항상 신경망을 가지고 있는데, 이 신경망은 observation을 mean action \(\mu_{\theta}(s)\)로 mapping 해주는 역할을 한다. 여기서 covariance matrix가 표현되는 두가지 방법이 있다.

첫번째 방법 : \( \log \sigma \) 라는 standard deviation에 log를 취한 single vector가 있는데, 이건 state에 대한 함수가 아니고 \(\log \sigma \)자체가 독립된 parameter이다. (우리가 구현한 VPG, TRPO, PPO가 이런 방식을 취했다.)

두번째 방법 : state와 log standard deviation 을 mapping한 신경망이 있는데, \(\log \sigma_{\theta}(s)\)로 표현된다. 아마 몇몇 계층에 대해서는 mean network들로 공유될 것이다.

 두가지 방법에 대해서 유념할 것은 출력으로 standard deviation (std) 을 직접적으로 받지 않고, log standard deviation (log std) 을 받았다는 것이다. 이렇게 한 이유는 일반적인 std가 항상 양수가 나오는 반면에, log std는 \( (-\infty, \infty) \) 내에서 어떤 값을 가져도 괜찮기 때문이다. 이렇게 하면, 학습 시킬 때 있어 constraint를 가할 필요가 없기 때문에 parameter를 학습시키는 것이 용이 해진다. 물론 std 자체도 log std에다 exponentiating을 하면 바로 구할 수 있기 때문에 이렇게 표현한다고 해서 손실되는 정보가 없다.

 Sampling : mean action \(\mu_{\theta}(s) \) 과 standard deviation \(\sigma_{\theta}(s)\), 그리고 spherical Gaussian \( (z \sim \mathcal{N}(0, I) )\) 를 가지는 noise vector \(z\)가 주어졌을대, action sample은 다음과 같이 계산할 수 있다.
$$ a = \mu_{\theta}(s) + \sigma_{\theta}(s) \circ z $$
 여기서 \( \circ \)는 두 vector에 대한 elementwise product (요소별로 곱하는 것, 보통 hadamard product로 알려져 있다.) 많이 쓰이는 framework에는 tf.random_normal 같은 noise vector를 계산하는 내장 함수들을 가지고 있다. 아니면, mean과 standard deviation을 바로 tf.distributions.Normal object 에 넣어 sampling하는데 사용할 수 있다.

 Log-Likelihood : mean \(\mu = \mu_{\theta}(s) \)과 standard deviation \( \sigma = \sigma_{\theta}(s) \)를 가지는 diagonal Gaussian 에서 k 차원의 action \(a\)에 대한 log-likelihood는 다음과 같이 구할 수 있다.
$$ \log \pi_{\theta} (a|s) = - \frac{1}{2} \left(\sum_{i=1}^{k} \left(\frac{(a_{i} - \mu_{i})^{2}}{\sigma_{i}^{2}} + 2 \log \sigma_{i} \right) + k \log 2 \pi \right) $$

Trajectories

 trajectory \(\tau\) 는 world상의 state와 action의 sequence 형태를 말하며, 다음과 같이 표현한다.

$$ \tau = (s_{0}, a_{0}, s_{1}, a_{1}, ... ) $$

 world에서 제일 처음 뽑아낸 state \( s_{0} \)는 state-state distribution에서 random하게 sampling된 것인데, 때로는 \( \rho_{0} \)로 표현되기도 한다.

$$ s_{0} \sim \rho_{0}(\cdot) $$

state transition ( world에서 time t의 state, \( s_{t} \)에서 t+1 에서의 state, \(s_{t+1}\) 간에 발생한 변화)는 environment가 가지고 있는 자연적인 현상에 의해서 좌우되며, 가장 최근에 발생한 action \(a_{t}\)에 의해서만 영향을 받는다. 이 형태는 아래와 같이

$$ s_{t+1} = f(s_{t}, a_{t}) $$

deterministic할 수도 있고, 혹은 아래와 같이

$$ s_{t+1} \sim P(\cdot | s_{t}, a_{t}) $$

stochastic할 수도 있다. 이때의 Action은 agent가 가지고 있는 policy에 의해서 도출되게 된다.

Trajectories는 다르게는 episode, 혹은 rollout이라고 부르기도 한다.

Reward와 Return

 reward function \(R\)은 강화학습에서 매우 중요한 요소이다. 이건 world상에서의 현재 state와 방금 취해진 action, 그리고 world에서의 next state에 의해서 달라지게 된다.

$$ r_{t} = R(s_{t}, a_{t}, s_{t+1} ) $$

혹은 현재 state에 의해서만 달라지거나 ( \( r_{t} = R(s_{t}) \) )나 state-action pair 의 영향을 받는 형식 (\( r_{t} = R(s_{t}, a_{t} \))으로 간략화되기도 한다.

 agent의 목표는 trajectory간에 축적된 reward의 어떤 형식이 최대화되는 것이 될텐데, 사실 이걸 통해서 몇가지를 도출할 수 있다. 아래에서 \(R(\tau)\) 에 관한 모든 케이스를 소개할 것이고, 이걸 통해서 어떤 것이 우리가 의도한 것이고, 어떤 것이 상관이 없는 것인지를 명확하게 표현할 수 있을 것이다. (왜냐하면 모든 케이스에서 같은 공식들이 사용되기 때문이다.)

 return에 대한 첫번째 종류는 finite-horizon undiscounted return 인데, 이는 정해진 window step 안에서 얻은 reward (\(r_{t}\))의 총합을 나타낸 것이다.

$$ R(\tau) = \sum_{t=0}^{T} r_{t} $$

 return에 대한 다른 종류는 infinite-horizon discounted return 인데, agent가 얻어낸 모든 reward의 총합이긴 한데, reward를 얻은 시점이 미래로부터 얼마나 떨어져 있느냐에 따라서 감쇄되는 형태를 띄고 있다. 이 reward의 공식은 discount factor \( \gamma \in (0, 1) \): 을 포함한다.

$$ R(\tau) = \sum_{t=0}^{\infty} \gamma^{t} r_{t} $$

 왜 우리가 discount factor를 적용해야 할까? 그냥 모든 reward를 받아도 되지 않을까? 하고 생각하는 사람도 있을텐데, 그렇게 할수도 있지만, discount factor 자체가 직관적인 면과 수학적으로의 편이성을 둘다 가지고 있다. 직관적인 관점에서 보면: 현재의 돈이 나중에 얻는 돈보다 더 가치가 있다고 표현할 수 있다. 수학적인 관점에서 보면: 무한대까지의 reward의 총합이 어쩌면 특정 값으로 수렴하지 않는 경우가 있을 수 있는데, 이 경우에는 공식으로 가지고 답을 구하기 어렵게 된다. 하지만 이해할만한 조건 내에서 discount factor를 가지게 되면, 무한대까지 reward를 더해도 수렴하게 된다.

어떻게 보면 RL 일반화 관점에서는, 위에서 언급한 두개의 형식간의 구분이 명확한 것처럼 보이겠지만, 실제의 Deep RL에서는 그 구분이 약간 흐릿한 경향이 있다. 예를 들어 undiscounted return를 최적화하기 위해서 알고리즘을 자주 다루기는 하나, discount factor를 쓰는 것은 value function을 평가하기 위해서 사용하는 것이다.

The RL Problem

 (infinite-horizon discounted한 return을 계산하냐, 혹은 finite-horizon undiscounted한 return을 계산하냐) return을 어떻게 측정하던 간에, 혹은 policy를 어떤 것을 선택하던 간에, RL의 목적은 expected return을 최대화하는 policy를 찾아서 agent가 그것에 따라 동작하게끔 하는 것이다.

 expected return에 대해서 이야기하기 위해서는, 우선 trajectory내에서의 확률 분포에 대해서 이야기를 해야 한다.

 먼저 environment내에서의 state transition과 policy가 stochastic하다고 가정해보자. 이 경우, T step 후의 trajectory에 대한 확률은 다음과 같이 계산할 수 있다.

$$ P(\tau | \pi) = \rho_{0}(s_{0})\prod_{t=0}^{T-1} P(s_{t+1} | s_{t}, a_{t}) \pi(a_{t} | s_{t})$$

 (위 식의 의미를 말하자면, 주어진 policy \(\pi\)에서 trajectory \(\tau\)를 따르게 될 확률은 제일 처음 state \(s_{0}\)가 발생할 확률에다가 미래에 특정 state \(s_{t}\) 에서 취할 수 있는 모든 action \(a_{t}\)에 대한 확률을 모두 곱한 것과 같다는 것이다.)

 이때의 expected return은 (어느 시점에서 측정하던지 간에), \(J(\pi)\)로 표현하는데, 다음과 같이 정의할 수 있다.

$$ J(\pi) = \int_{\tau}P(\tau | \pi)R(\tau) = E_{\tau \sim \pi}[R(\tau)]$$

이렇게 되면 RL에서의 최적화 문제는 다음과 같이

$$ \pi^{*} = arg\,max_{\pi}J(\pi) $$

정의할 수 있고, 이때 \(\pi^{*}\)를 optimal policy라고 하게 된다.

Value Functions

 state에 대한 value나 state-action pair에 대해서 아는 것은 매우 유용하다. 여기서 value란, 특정 state나 해당 state에 대한 action pair에서 시작할 때 얻을 수 있는 expected return을 의미하는데, 이를 통해 끝날 때까지 특정 policy에 의해서 행동하게 된다. 여기서 Value function이라는 사용되는데, 거의 모든 RL 알고리즘에서 하나나 여러가지 방법으로 나오게 된다.

 여기서 네가지 핵심 함수를 소개해본다.

 1. On-Policy Value Function \( V^{\pi}(s) \) : state \(s\)에서 시작하고 policy \(\pi\)에 따라서 항상 행동을 취할 때, 이에 대한 expected return을 출력으로 내보낸다.

$$ V^{\pi}(s) = E_{\tau\sim\pi}[R(\tau) | s_{0} = s]$$

 2. On-Policy Action-Value Function \( Q^{\pi}(s, a) \) : state \(s\)에서 시작하고, 임의의 action \(a\) (참고로 이때의 action은 policy에서 나온게 아닐 수도 있다.)을 취하고 난후, policy \(\pi\)에 의해서 행동하게 될 때, 이에 대한 expected return을 출력으로 내보낸다.

$$ Q^{\pi}(s, a) = E_{\tau\sim\pi}[R(\tau) | s_{0} = s, a_{0} = a] $$

 3. Optimal Value Function \( V^{*}(s) \) :  state \(s\)에서 시작하고, environment 상에서 optimal policy에 따라 항상 action을 취할 경우, 이때의 expected return을 반환해준다.

$$ V^{*}(s) = \max\limits_{pi} E_{\tau\sim\pi}[R(\tau) | s_{0} = s ] $$

 4. Optimal Action-Value Function \(Q^{*}(s, a) \) : state \(s\)에서 시작하고, 임의의 action \(a\)을 취한 후에 environment상에서 optimal policy에 따라 action을 행할 경우, 이때의 expected return을 반환해준다.

$$ Q^{*}(s, a) = \max\limits_{pi} E_{\tau\sim\pi}[R(\tau) | s_{0} = s, a_{0} = a ] $$

 Value function에 대해서 이야기 할 때, 시간과 관련해서 아무 언급이 없다면, 여기서는 value function을 expected infinite-horizon discounted return을 의미하는 것이다. Finite-horizon undiscounted return 에 대한 Value function은 시간을 함수의 인자로 받아야 한다. 

자주 나오고 있는 Value function과 action-value function 간의 두가지 핵심적인 요소가 있는데 바로
$$ V^{\pi}(s) = E_{a\sim\pi}[Q^{\pi}(s, a)]$$
와
$$ V^{*}(s) = \max\limits_{a}Q^{*}(s, a)$$
이 관계는 정의에서 바로 도출한 내용이다. (Sutton 책 참조)

 Optimal Q-Function과 Optimal Action

optimal action-value function \(Q^{*}(s, a)\)와 optimal policy 에 의해서 결정되는 action간에는 중요한 연결고리가 있다. 정의에 따르면, \(Q^{*}(s, a)\) 는 state \(s\)에서 시작하고, 임의의 action \(a\)를 한 상태에서 optimal policy에 따라 행동했을때, 이에 대한 expected return을 반환해준다.

 state \(s\)에서의 optimal policy는 \(s\)에서 시작해서 expected return을 최대화 할 수 있는 어떤 action이든 모든 것을 선택할 것이다. 결론적으로 우리가 \(Q^{*}\)를 알고 있다면, optimal function \(a^{*}(s)\) 를 다음과 같이 도출할 수 있을 것이다.

$$ a^{*}(s) = arg\max\limits_{a}Q^{*}(s, a) $$

 만약 \(Q^{*}(s, a)\)를 최대화 할 수 있는 action이 여러 개 있을 수 있고, 어떤 경우에는 모든 action들이 optimal해서 optimal policy가 해당 action 중 하나를 랜덤하게 선택할 수도 있다. 하지만 optimal action을 deterministic하게 정하는 optimal policy는 항상 존재한다.

Bellman Equation

 위에서 언급한 4가지 value function 모두 Bellman equation이라고 불리는 특별히 일관성있는 방정식을 다른다. Bellman equation에 깔려있는 기본 아이디어는 다음과 같다.

시작하는 지점의 value는 그 지점에 expect되는 reward에 다음 이동할 지점의 value를 더한 값이다.

On-policy value function에서의 Bellman Equation은 다음과 같다.

$$ V^{\pi}(s) = E_{a\sim\pi , s'\sim P}[ r(s, a) + \gamma V^{\pi}(s') ] $$

$$ Q^{\pi}(s, a) = E_{s'\sim P}\left[r(s, a) + \gamma E_{a'\sim\pi}[Q^{\pi}(s', a')]\right] $$

여기서 \(s'\sim P \)는 \(s' \sim P(\cdot | s, a)\)를 줄인 표현인데, 이는 next state \(s'\)가 environment의 transition 규칙에 따라 도출되었다는 것을 의미한다. 그리고 \( a \sim \pi \)는 \(a \sim \pi(\cdot | s) \)를 줄인 표현이고, \( a' \sim \pi \)는 \(a' \sim \pi(\cdot | s') \) 를 줄인 표현이다.

 Optimal Value function에 대한 Bellman Equation은 다음과 같다.

$$ V^{*}(s) = \max\limits_{a}E_{s'\sim P}[ r(s, a) + \gamma V^{*}(s') ] $$

$$ Q^{\pi}(s, a) = E_{s'\sim P}\left[r(s, a) + \gamma \max\limits_{a'}[Q^{\pi}(s', a')]\right] $$

on-policy value function과 Optimal value function 각각의 bellman equation간의 가장 중요한 차이는 action에 대한 max function의 존재 유무이다. 해당 function의 존재는 결국 agent가 언제 action을 선택하던지간에 optimal하게 동작하기 위해서는 가장 높은 value를 주는 action을 선택해야 한다는 사실을 보여준다.

 RL에 대해서 연구하다보면 "Bellman backup" 이란 단어가 자주 나오는데, state나 action-state pair에 대한 bellman backup이라고 하는 것은 Bellman equation의 우항인 현재의 reward에 next value를 더한 값을 나타내는 것이다.

 Advantage Function

 RL에서는 때때로는, 절대적인 관점에서 취한 action이 얼마나 좋은지를 표현할 필요는 없고, 단순히 해당 action이 평균보다 얼마나 좋은지만 알아도 되는 경우가 있다. 다시 말해, 취한 action에 대한 상대적인(relative) advantage 를 알기 원한다는 것이다. 이런 개념을 advantage function이라고 정의한다.

 Policy \(\pi\)에 의한 Advantage function \(A^{\pi}(s, a)\)는 만약 policy \(\pi\)를 계속 따른다고 가정했을 때, state \(s\)에서 action \(a\)를 취한 것이, \(\pi(\cdot|s)\)에 따라 랜덤하게 선택한 action에 비해 얼마나 좋은지를 나타내는 함수이다. 수학적으로 advantage function은 다음과 같이 정의할 수 있다.

$$ A^{\pi}(s, a) = Q^{\pi}(s, a) - V^{\pi}(s) $$

(Optional) Formalism

 지금까지 agent의 environment에 대해서 비형식적으로나마 이야기 해봤는데, RL에 대해서 조금더 파볼 생각이 있다면, 다음과 같은 표준적인 수학 공식를 파보는 것이 좋은데, 이게 바로 Markov Decision Processes (MDPs) 이다. MDP는  \(<S, A, R, P, \rho_{0}>\)와 같이 5개의 요소로 구성된 tuple이다.

• \(S\)는 모든 유효 state들의 집합이다.
• \(A\)는 모든 유효 action들의 집합이다.
• \(R : S \times A \times S \to \mathbb{R} \) 는 \( r_{t} = R(s_{t}, a_{t}, s_{t+1})\)에 대한 reward function이다. 
• \(P : S \times A \to P(S) \)는 만약 agent가 state \(s\)에서 시작하고 action \(a\)를 취한다고 했을때, state \(s'\)로 transition이 발생할 확률을 나타내는 \(P(s' | s, a)\)의 값을 가지는 transition probability function이다. 
• \(\rho_{0}\)는 starting state transition을 나타낸다.

 Markov Decision Process란 이름은 해당 system이 markov property를 따르는 사실에서 참고한 것인데, Markov property란 state transition이 과거에 대한 history와는 무관하며, 가장 최근의 state와 그때 취한 action에만 영향을 받는 것을 나타내는 것이다.