Answers.Body: <p>Actually your source only gave a deterministic environment example (ToZerind) which may not definitely mean they only consider deterministic environment for the general action cost function which is a concept rooted from control theory similar to (expected) reward from RL and loss function from statistics as the author wrote somewhere else in your reference.</p>
  <blockquote>
  <p>It prevails not only in AI, but also in control theory, where a
  controller minimizes a cost function; in operations research, where a policy maximizes a sum of rewards; in statistics, where a decision rule minimizes a loss function</p>
  </blockquote>
  <p>In Sutton's RL book the reward (cost) function <span class="math-container">$\mathcal{R}$</span> is a random variable and they never wrote or needed <span class="math-container">$\mathcal{R}(s_t, a_t, s_{t+1})$</span>, but instead, its <em>expected</em> value <span class="math-container">$r(s_t, a_t, s_{t+1})$</span> is defined on page 49 due to possible stochastic environment unlike a normal grid world game:</p>
  <blockquote>
  <p>We can also compute the expected rewards for state–action pairs as a two-argument function <span class="math-container">$r : \mathcal{S} \times \mathcal{A} \to \mathbb{R}$</span>:
  <span class="math-container">$$r(s,a) = \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} rp(s',r|s,a)$$</span>
  and the expected rewards for state–action–next-state triples as a three-argument function <span class="math-container">$r : \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to \mathbb{R}$</span>,
  <span class="math-container">$$r(s,a,s') = \sum_{r \in \mathcal{R}}r\frac{p(s',r|s,a)}{p(s'|s,a)}$$</span></p>
  </blockquote>
  <p>In fact in Sutton's book the only place the 3-argument expected reward is explicitly used appears in a nondeterministic finite state diagram for a recycling robot example on page 52:</p>
  <p><a href="https://i.sstatic.net/5UpVs.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5UpVs.png" alt="enter image description here" /></a></p>
  <p>You see in such a diagram the expected reward function needs the explicit dependence of the entering state to conveniently express its value based on its entering state for each of the possibly branching state transition due to its random environment characterized by Markovian transition dynamics <span class="math-container">$p(s',r|s,a)$</span>. Therefore sometimes the 3-argument cost (reward) function in the sense of expectation may be needed even assuming the usual MDP environment in the most general conceivable cases.</p>
  <p>There's a very similar question recently and you can refer to my related answer <a href="https://ai.stackexchange.com/questions/43550/how-can-reward-at-time-step-t-can-be-a-function-of-a-state-at-time-step-t1/43552#43552">there</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-25T19:39:24.520Z
Answers.LastActivityDate: 2024-02-25T19:45:54.113Z
Answers.LastEditDate: 2024-02-25T19:45:54.113Z
Answers.UserDisplayName: cinch
Answers.Body: <p>You are correct that <span class="math-container">$s'$</span> is redundant information in <span class="math-container">$c(s,a,s')$</span> for a deterministic environment.</p>
  <p>However, using the full form of the cost function, that also covers non-deterministic environments, saves the authors from redefining it later. The form <span class="math-container">$c(s,a,s')$</span> is generic enough to cover a much wider range of problems, and some of the equations and methods derived using it can be re-used in more complex environments, whilst if it was specialised to deterministic environments only, then the same equations would have to be derived again.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-25T09:55:44.480Z
Answers.LastActivityDate: 2024-02-25T09:55:44.480Z
Answers.UserDisplayName: Neil Slater
Body: <p>In the famous AI book <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig (4th edition)</a>, in chapter 3, the action cost function of a problem solver agent denoted as <span class="math-container">$c(s, a, s')$</span>, that gives the numeric cost of applying action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span> to reach state <span class="math-container">$s'$</span>.</p>
  <p>But according to the text, in that chapter, it is assumed that the environment is deterministic. So, given the current state and the action, the next state is known.</p>
  <p>My question is that, as the next state can be determined by the current state and applying action, why does the cost function depend on the next state?</p>
  
Tags: <objective-functions><search><norvig-russell><problem-solving>
Title: Why does an action cost function dependes on result state in search problems?
UserDisplayName: user153245
ThreadText: # Why does an action cost function dependes on result state in search problems?
  
  (Asked by: username_0 on 2024-02-24)
  
  In the famous AI book [Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig (4th edition)](http://aima.cs.berkeley.edu/), in chapter 3, the action cost function of a problem solver agent denoted as $c(s, a, s')$, that gives the numeric cost of applying action $a$ in state $s$ to reach state $s'$.
  
  But according to the text, in that chapter, it is assumed that the environment is deterministic. So, given the current state and the action, the next state is known.
  
  My question is that, as the next state can be determined by the current state and applying action, why does the cost function depend on the next state?
  
  **Tags:** objective-functions, search, norvig-russell, problem-solving
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-02-25. Score: 1
  
  Actually your source only gave a deterministic environment example (ToZerind) which may not definitely mean they only consider deterministic environment for the general action cost function which is a concept rooted from control theory similar to (expected) reward from RL and loss function from statistics as the author wrote somewhere else in your reference.
  
  > It prevails not only in AI, but also in control theory, where a
  > controller minimizes a cost function; in operations research, where a policy maximizes a sum of rewards; in statistics, where a decision rule minimizes a loss function
  
  In Sutton's RL book the reward (cost) function $\mathcal{R}$ is a random variable and they never wrote or needed $\mathcal{R}(s\_t, a\_t, s\_{t+1})$, but instead, its *expected* value $r(s\_t, a\_t, s\_{t+1})$ is defined on page 49 due to possible stochastic environment unlike a normal grid world game:
  
  > We can also compute the expected rewards for state–action pairs as a two-argument function $r : \mathcal{S} \times \mathcal{A} \to \mathbb{R}$:
  > $$r(s,a) = \sum\_{r \in \mathcal{R}} \sum\_{s' \in \mathcal{S}} rp(s',r|s,a)$$
  > and the expected rewards for state–action–next-state triples as a three-argument function $r : \mathcal{S} \times \mathcal{A} \times \mathcal{S} \to \mathbb{R}$,
  > $$r(s,a,s') = \sum\_{r \in \mathcal{R}}r\frac{p(s',r|s,a)}{p(s'|s,a)}$$
  
  In fact in Sutton's book the only place the 3-argument expected reward is explicitly used appears in a nondeterministic finite state diagram for a recycling robot example on page 52:
  
  [![enter image description here](https://i.sstatic.net/5UpVs.png)](https://i.sstatic.net/5UpVs.png)
  
  You see in such a diagram the expected reward function needs the explicit dependence of the entering state to conveniently express its value based on its entering state for each of the possibly branching state transition due to its random environment characterized by Markovian transition dynamics $p(s',r|s,a)$. Therefore sometimes the 3-argument cost (reward) function in the sense of expectation may be needed even assuming the usual MDP environment in the most general conceivable cases.
  
  There's a very similar question recently and you can refer to my related answer [there](https://ai.stackexchange.com/questions/43550/how-can-reward-at-time-step-t-can-be-a-function-of-a-state-at-time-step-t1/43552#43552).
  
  
  ---
  
  ### Answer by username_2 on 2024-02-25. Score: 0
  
  You are correct that $s'$ is redundant information in $c(s,a,s')$ for a deterministic environment.
  
  However, using the full form of the cost function, that also covers non-deterministic environments, saves the authors from redefining it later. The form $c(s,a,s')$ is generic enough to cover a much wider range of problems, and some of the equations and methods derived using it can be re-used in more complex environments, whilst if it was specialised to deterministic environments only, then the same equations would have to be derived again.
  
  
  ---
  
  