Effective planning horizon narrow class

Theorem of effective horizon equivalence

Let $J_R:\mathrm{\Pi }\to \mathbb{R}$ be a return function, ${\pi }^{\ast }=\arg \underset{\pi }{max}{J}_R(\pi )$, the sequence $\{{\pi }^k{\}}_{k\in \mathbb{N}}$ is fixed, and $J_R({\pi }^{\ast })\ne J_R({\pi }^0)$. We define:

Then we prove that:

Lemma

Let $J_R({\pi }^{\ast })-J_R({\pi }^0)\ne 0$. Then:

where $f(k,R):={\displaystyle \frac{J_R({\pi }^{\ast })-J_R({\pi }^k)}{J_R({\pi }^{\ast })-J_R({\pi }^0)}}$.

Proof

$(⟸)$: Suppose $\mathrm{\forall }k:f(k,R^{\prime })=f(k,R)$. Then for every $\epsilon$, $\{k:f(k,R^{\prime })\le \epsilon \}=\{k:f(k,R)\le \epsilon \}$, hence $\mathrm{\forall }\epsilon >0:H_{\text{eff}}(R^{\prime },\epsilon )=H_{\text{eff}}(R,\epsilon )$.

$(⟹)$: Assume there exists the smallest $k_0$ such that $f(k_0,R^{\prime })\ne f(k_0,R)$. Without loss of generality, let $f(k_0,R^{\prime })<f(k_0,R)$ (the case $>$ is symmetric). Choose:

Then $k_0$ is included in the set $\{k:f(k,R^{\prime })\le {\epsilon }_0\}$, but not in $\{k:f(k,R)\le {\epsilon }_0\}$. Consequently:

From necessity and sufficiency, the lemma is proven.

Now, based on the lemma, it suffices to prove:

Let's introduce the notation: $J:=J_R$, $J^{\prime }:=J_{R^{\prime }}$, ${\mathrm{\Delta }}_k:=J({\pi }^{\ast })-J({\pi }^k)$, ${\mathrm{\Delta }}_0:=J({\pi }^{\ast })-J({\pi }^0)\ne 0$.

$(⟸)$: Suppose $J^{\prime }(\pi )=aJ(\pi )+b$ for all $\pi \in \{{\pi }^{\ast },{\pi }^0\}\cup \{{\pi }^k\}$, with $a\ne 0$. Then for any $k$:

Since $a\ne 0$, the denominator $a{\mathrm{\Delta }}_0\ne 0$, and:

$(⟹)$: Suppose $\mathrm{\forall }k\in \mathbb{N}:f(k,R^{\prime })=f(k,R)$. This means:

Where $J^{\prime }({\pi }^{\ast })\ne J^{\prime }({\pi }^0)$, since otherwise $f(k,R^{\prime })$ would be undefined for all $k$, contradicting the assumption $\mathrm{\forall }k:f(k,R^{\prime })=f(k,R)$.

Let's define:

From $(1)$, by multiplying both sides by $a{\mathrm{\Delta }}_0$:

We also separately check the cases with ${\pi }^{\ast }$ and ${\pi }^0$:

$aJ({\pi }^{\ast })+b=aJ({\pi }^{\ast })+J^{\prime }({\pi }^{\ast })-aJ({\pi }^{\ast })=J^{\prime }({\pi }^{\ast })$

From the definition of $a$, we have $J^{\prime }({\pi }^0)=J^{\prime }({\pi }^{\ast })-a{\mathrm{\Delta }}_0=J^{\prime }({\pi }^{\ast })-a(J({\pi }^{\ast })-J({\pi }^0))=aJ({\pi }^0)+b$.

Thus, from necessity and sufficiency, the relation $J^{\prime }(\pi )=aJ(\pi )+b$ is proven for all $\pi \in \{{\pi }^{\ast },{\pi }^0\}\cup \{{\pi }^k{\}}_{k\in \mathbb{N}}$, where $a\ne 0$, meaning $J^{\prime }$ is an affine transformation of $J$ on the specified set.

Since the proof establishes that $\mathrm{\forall }\epsilon >0:H_{\text{eff}}(R^{\prime })=H_{\text{eff}}(R)$ if and only if $J_{R^{\prime }}$ is an affine transformation of $J_R$ ($a\ne 0$) on ${\pi }^{\ast },{\pi }^0\cup {{\pi }^k}_{k\in \mathbb{N}}$, and STARC-equivalence requires $J_{R^{\prime }}=a{J}_R+b$ with $a>0$ on the entirety of $\mathrm{\Pi }$, it follows that STARC-equivalence is a strictly stronger condition. In particular, $[R{]}_{\text{STARC}}\subseteq [R{]}_{H_{\text{eff}}}$, because any $a>0$ is a special case of $a\ne 0$, and the condition on the entirety of $\mathrm{\Pi }$ implies the condition on a subset.

Counterexample to the Pointwise Implication

We show that replacing $\mathrm{\forall }\epsilon >0$ with $\mathrm{\exists }\epsilon >0$ breaks the theorem: we construct explicit $J,J^{\prime }$ for which the values $H_{\text{eff}}(R,{\epsilon }_0)$ and $H_{\text{eff}}(R^{\prime },{\epsilon }_0)$ coincide at one specific ${\epsilon }_0$, but $J^{\prime }$ is not an affine transformation of $J$ on $\{{\pi }^{\ast },{\pi }^0\}\cup \{{\pi }^k{\}}_{k\in \mathbb{N}}$.

Let us define

Then $J({\pi }^0)=0$, $J({\pi }^k)\in [0,1)$ for all $k$, and $J({\pi }^k)\to 1$, so ${\pi }^{\ast }=\arg \underset{\pi }{max}J(\pi )$ and the condition $J({\pi }^{\ast })-J({\pi }^0)=1\ne 0$ holds. A direct computation gives

Take ${\epsilon }_0=2/5$. The condition $1/(k+1)\le 2/5$ holds for $k\ge 3/2$, that is, $H_{\text{eff}}(R,{\epsilon }_0)=2$.

Now define $J^{\prime }$ on the same $\mathrm{\Pi }$:

All values lie in $[0,1)$, so ${\pi }^{\ast }=\arg max{J}^{\prime }$ and $J^{\prime }({\pi }^{\ast })-J^{\prime }({\pi }^0)=1\ne 0$. We compute the ratios:

For $\epsilon ={\epsilon }_0=2/5$ we have $f(0,R^{\prime })=1>2/5$, $f(1,R^{\prime })=3/5>2/5$, $f(2,R^{\prime })=3/10\le 2/5$. Hence

We show that there is no affine relation. Suppose $J^{\prime }(\pi )=aJ(\pi )+b$ on the entire set $\{{\pi }^{\ast },{\pi }^0\}\cup \{{\pi }^k\}$. From $J({\pi }^{\ast })=J^{\prime }({\pi }^{\ast })=1$ and $J({\pi }^0)=J^{\prime }({\pi }^0)=0$ we get $b=0$ and $a=1$, that is, $J^{\prime }(\pi )=J(\pi )$. But $J^{\prime }({\pi }^1)=2/5\ne 1/2=J({\pi }^1)$, so we have a contradiction.

Theorem of extension to dense subsets of $\epsilon$

Fix $R,R^{\prime }$ for which $f(k,R),f(k,R^{\prime })$ are well-defined. Introduce the notation ${\varphi }_R(\epsilon ):=H_{\text{eff}}(R,\epsilon )\in \mathbb{N}\cup \{+\mathrm{\infty }\}$, setting ${\varphi }_R(\epsilon )=+\mathrm{\infty }$ if $\{k:f(k,R)\le \epsilon \}=\mathrm{\varnothing }$. The function ${\varphi }_R$ is non-increasing on $(0,\mathrm{\infty })$.

Let $E\subseteq (0,\mathrm{\infty })$ be dense in $(0,\mathrm{\infty })$. Then

Combined with the original lemma, this yields the equivalence of $(\mathrm{i})$ with the affinity $J_{R^{\prime }}=a{J}_R+b$, $a\ne 0$, on $\{{\pi }^{\ast },{\pi }^0\}\cup \{{\pi }^k\}$.

Proof

The implication $(\mathrm{ii})\Rightarrow (\mathrm{i})$ is trivial.

We show $(\mathrm{i})\Rightarrow (\mathrm{ii})$. By contradiction suppose there exists ${\epsilon }^{\ast }>0$ with ${\varphi }_R({\epsilon }^{\ast })\ne {\varphi }_{R^{\prime }}({\epsilon }^{\ast })$. Without loss of generality ${\varphi }_R({\epsilon }^{\ast })<{\varphi }_{R^{\prime }}({\epsilon }^{\ast })$. Denote $n:={\varphi }_R({\epsilon }^{\ast })\in \mathbb{N}$.

By the definition of ${\varphi }_R({\epsilon }^{\ast })=n$ we have $f(n,R)\le {\epsilon }^{\ast }$. From the inequality ${\varphi }_{R^{\prime }}({\epsilon }^{\ast })>n$, for all $k\in \{0,1,\dots ,n\}$ we have $f(k,R^{\prime })>{\epsilon }^{\ast }$. Set

The minimum is over a finite set, and each term is strictly greater than ${\epsilon }^{\ast }$, so the minimum is also strictly greater than ${\epsilon }^{\ast }$. Take any $\epsilon \in ({\epsilon }^{\ast },m)$. Since $f(k,R^{\prime })\ge m>\epsilon$ for all $k\le n$, we have ${\varphi }_{R^{\prime }}(\epsilon )>n$.
On the other hand, $f(n,R)\le {\epsilon }^{\ast }<\epsilon$, so $n\in \{k:f(k,R)\le \epsilon \}$ and ${\varphi }_R(\epsilon )\le n$. In total:

The interval $({\epsilon }^{\ast },m)$ is non-empty and open in $(0,\mathrm{\infty })$. By density of $E$ there exists ${\epsilon }_0\in E\cap ({\epsilon }^{\ast },m)$. Then ${\varphi }_R({\epsilon }_0)\ne {\varphi }_{R^{\prime }}({\epsilon }_0)$, which contradicts $(\mathrm{i})$.

Sharpness of the Density Condition

We can also show that the density of $E$ in $(0,\mathrm{\infty })$ cannot be weakened without losing the theorem for all admissible $R,R^{\prime }$.

Suppose $E$ is not dense: there exists an open interval $(\alpha ,\beta )\subset (0,\mathrm{\infty })$ with $E\cap (\alpha ,\beta )=\mathrm{\varnothing }$. Without loss of generality $\beta <1$ (otherwise shift the interval inside $(0,1)$, which preserves the property of not intersecting $E$ for a suitable subinterval; the informative zone of $\varphi$ lies precisely in $(0,1)$, since $f=1$ gives $\varphi \equiv 0$ for $\epsilon \ge 1$).

Choose $c_R\ne c_{R^{\prime }}$ inside $(\alpha ,\beta )$. Define the returns via the values of $f$:

The corresponding $J,J^{\prime }$ are obtained as $J({\pi }^{\ast })=J^{\prime }({\pi }^{\ast })=1$, $J({\pi }^0)=J^{\prime }({\pi }^0)=0$, $J({\pi }^k)=1-f(k,R)$, $J^{\prime }({\pi }^k)=1-f(k,R^{\prime })$. All values $J({\pi }^k),J^{\prime }({\pi }^k)$ lie in $[0,1)$, so ${\pi }^{\ast }$ remains the argmax for both returns, and the conditions of the lemma are satisfied.

We compute ${\varphi }_R$:

• $\epsilon \ge 1$: $f(0)=1\le \epsilon$, ${\varphi }_R(\epsilon )=0$.
• $\epsilon \in [c_R,1)$: $f(1,R)=c_R\le \epsilon <1=f(0)$, ${\varphi }_R(\epsilon )=1$.
• $\epsilon \in [\alpha /2,c_R)$: $f(k,R)=\alpha /2\le \epsilon$ for $k\ge 2$, $f(1,R)>\epsilon$, ${\varphi }_R(\epsilon )=2$.
• $\epsilon <\alpha /2$: no $f$ qualifies, ${\varphi }_R(\epsilon )=+\mathrm{\infty }$.

The same for $R^{\prime }$ with the substitution $c_R\to c_{R^{\prime }}$. A discrepancy is possible only in the zone between $c_R$ and $c_{R^{\prime }}$: for $\epsilon \in [min(c_R,c_{R^{\prime }}),max(c_R,c_{R^{\prime }}))$ one of the functions equals $1$, the other equals $2$. But this zone lies entirely in $(\alpha ,\beta )$ and hence does not intersect $E$. Outside $(\alpha ,\beta )$ both functions ${\varphi }_R,{\varphi }_{R^{\prime }}$ coincide by construction.

We obtained that ${\varphi }_R={\varphi }_{R^{\prime }}$ on $E$, but not on all of $(0,\mathrm{\infty })$ as $(\mathrm{i})$ holds while $(\mathrm{ii})$ fails. By the original lemma, the failure of $(\mathrm{ii})$ means that $J^{\prime }$ is not affinely related to $J$ on $\{{\pi }^{\ast },{\pi }^0\}\cup \{{\pi }^k\}$.

As a result, for any $E\subseteq (0,\mathrm{\infty })$, the property "$(\mathrm{i})$ implies affinity for all admissible $R,R^{\prime }$ " is equivalent to the density of $E$ in $(0,\mathrm{\infty })$.