My reduction works as follows: first the highest reward choice is chosen, then its reward is adjusted to $-\infty$, and the process is repeated until a set of size $m$ has been achieved. This is essentially how I've always seen it done in the past (e.g., construct a regressor, and fill positions in sorted order), but for this greedy approach to work the positional dependence cannot be arbitrary: it must be that \[ \sum_{i=1}^m \max_{a_i \in A \setminus \{ a^*_1, \ldots, a^*_{i-1} \} } r (a_i, i) = \max_{a \in \tilde A^m}\; \sum_{i=1}^m r (a_i, i). \] Here $r: A \times [1, m] \to [0, 1]$ are the (conditionally expected) rewards, $A$ are the actions, and $[1, m]$ are the positions, and the right hand side maximum is over vectors of actions $\tilde A^m$ that do not have duplicates (i.e., the same action cannot be chosen at multiple positions). This ``greedy works'' condition is actually a much weaker condition than I'm used to assuming. For instance, here's an example set of expected rewards for which greedy works: \[

\begin{array}{|c|c|c|c|}

\mbox{Action} & r (a, 1) & r (a, 2) & r (a, 3) \\ \hline

1 & 10 & 5 & 1 \\

2 & 2 & 4 & 1 \\

3 & 1 & 2 & 3

\end{array}

\] The first action has decreasing reward by position, while the second action prefers a particular position and the third action has increasing reward by position. So I thought I'd had some fun exploring the above ``greedy works'' condition.

Lemma:Position Maximizers

If there is at least one maximizer of $\sum_{j=1}^m r (a_j, j)$, then there is a maximizer of $\tilde a^*$ of $\sum_{j=1}^m r (a_j, j)$ which uses each individual position maximizer $a^*_i$ for all $i \in [1, m]$, where $a^*_i$ maximizes $r (a, i)$.

**Proof:**Let $a^*_i$ be a maximizer of $r (a, i)$, and assume $\tilde a^*$ is a maximizer of $\sum_{j=1}^m r (a_j, j)$ that does not use $a^*_i$ in any position. Define $a^\prime$ as $\tilde a^*$ with position $i$ replaced by $a^*_i$. Since $a^*_i$ is a maximizer of $r (a, i)$, the resulting total reward cannot decrease, therefore $a^\prime$ would also be a maximizer of $\sum_{j=1}^m r (a_j, j)$. Repeating this argument for each position $i$ eventually uses an individual position maximizer from every position.Sufficient Condition:Swap Supremacy

If \[

r (a, i) \geq r (a^\prime, i) \implies \forall j > i: r (a, i) + r (a^\prime, j) \geq r (a, j) + r (a^\prime, i),

\] then \[

\sum_{i=1}^m \max_{a_i \in A \setminus \{ a^*_1, \ldots, a^*_{i-1} \} } r (a_i, i) = \max_{a \in \tilde A^m}\; \sum_{i=1}^m r (a_i, i).

\]

To show $m - 1 \Rightarrow m$, note from the lemma it follows that there is a maximizer of the right hand side that uses $a^*_1$ in some position. If that position is $j \neq 1$, then construct a new maximizer of the right hand side by swapping positions 1 and $j$: this is guaranteed not to decrease the total reward due to the precondition of the theorem. Since both the left hand and right hand side of the desired result use $a^*_1$ in position 1, it can be subtracted from both sides, yielding \[

\sum_{i^\prime=1}^{m-1} \max_{a^\prime_{i^\prime} \in A_1 \setminus \{ {a^\prime}^*_1, \ldots, {a^\prime}^*_{i^\prime-1} \} } r (a^\prime_{i^\prime}, i^\prime) = \max_{a \in \tilde A_1^m}\; \sum_{i^\prime=1}^{m-1} r (a_{i^\prime}, i^\prime),

\] where $A_1 = A \setminus a^*_1$ and $i^\prime = i - 1$.

r (a, i) \geq r (a^\prime, i) \implies \forall j > i: r (a, i) + r (a^\prime, j) \geq r (a, j) + r (a^\prime, i),

\] then \[

\sum_{i=1}^m \max_{a_i \in A \setminus \{ a^*_1, \ldots, a^*_{i-1} \} } r (a_i, i) = \max_{a \in \tilde A^m}\; \sum_{i=1}^m r (a_i, i).

\]

**Proof:**Proof is by induction. The base case is when $m = 1$, in which case greedy always works.To show $m - 1 \Rightarrow m$, note from the lemma it follows that there is a maximizer of the right hand side that uses $a^*_1$ in some position. If that position is $j \neq 1$, then construct a new maximizer of the right hand side by swapping positions 1 and $j$: this is guaranteed not to decrease the total reward due to the precondition of the theorem. Since both the left hand and right hand side of the desired result use $a^*_1$ in position 1, it can be subtracted from both sides, yielding \[

\sum_{i^\prime=1}^{m-1} \max_{a^\prime_{i^\prime} \in A_1 \setminus \{ {a^\prime}^*_1, \ldots, {a^\prime}^*_{i^\prime-1} \} } r (a^\prime_{i^\prime}, i^\prime) = \max_{a \in \tilde A_1^m}\; \sum_{i^\prime=1}^{m-1} r (a_{i^\prime}, i^\prime),

\] where $A_1 = A \setminus a^*_1$ and $i^\prime = i - 1$.

Now to just make this work.

## No comments:

## Post a Comment