A Difficulty With Density-Zero Exploration discussion post by Alex Appel 446 days ago | 1 comment Summary: If exploration rates decay to zero, the obvious way of ensuring that exploration occurs infinitely often (have a trader that sells the sentence saying that exploration will happen) may fail when there are long delays before you get feedback on whether exploration happened, because the trader can go indefinitely into (possible) debt due to slow feedback. And, if the trader budgets itself, then it won’t do enough trading to acquire unbounded money from the slowly decaying exploration rate. So, Density-Zero Exploration was motivated by the following concern: A trader could mess up conditional utilities, and the way in which it did it left the trader capable of taking the same action next turn, as detailed here Of course, $$\epsilon$$-exploration takes care of this issue, and further, you don’t really need the $$\epsilon$$ to remain constant over time, you can have it drop as $$\frac{1}{n}$$ on the $$\overline{\mathbb{P}}$$-generable weighting which corresponds to the trades of the enforcer trader. The obvious hope is that exploration would happen infinitely often along the subsequence, so any enforcer trader would lose eventually. Intuitively, that’s how it works. But it’s a bit harder to get than I naively thought at first. My first attempt at proving it (modulo some finicky details about $$\overline{\mathbb{P}}$$-generable weightings and how they aren’t always 1) was something along the lines of “in the limit, the probability of exploration on the $$n$$’th element of the subsequence will be very close to $$\frac{1}{n}$$, and because of this, if there’s only finitely much exploration, it’s possible for a trader to get infinite money by selling stocks of the exploration sentence.” However, there’s a problem when you don’t get immediate feedback on whether the exploration step occurred. If you have to wait a very long time to hear whether the exploration step happened, then the strategy of “sell stocks in the exploration sentence” may leave the trader unboundedly in debt. For most of the theorems in the logical induction paper, it was acceptable to take a very long time to exploit an arbitrage opportunity, because by assumption, arbitrage opportunities occurred infinitely often. However, because the frequency of exploration on a subsequence drops as $$\frac{1}{n}$$, you can’t get a contradiction with the logical inductor criterion if the trader only exploits a sparse subsequence of those days. Therefore, you can’t guarantee infinite exploration steps occur with $$\frac{1}{n}$$-exploration, and sparse feedback on exploration steps, if you’re using the path of “ooh there’s infinite money available by selling stocks in the exploration sentence.” The trader’s plausible value will either be unbounded below (by selling a bunch of overpriced stocks, but selling faster than they get feedback of whether they were worth anything or not), or bounded above (because waiting for feedback for budgeting purposes is slow enough that the trader cannot accumulate infinite money) I still very strongly expect that on any $$\overline{\mathbb{P}}$$-generable weighting of the sequence of days, there will be infinite exploration steps, but the obvious way of showing it fails.

 by Alex Appel 445 days ago | link Update: This isn’t really an issue, you just need to impose an assumption that there is some function $$f$$ such that $$f(n)>n$$, and $$f(n)$$ is computable in time polynomial in $$f(n)$$, and you always find out whether exploration happened on turn $$f(n)$$ after $$\mathcal{O}(f(n+1))$$ days. This is just the condition that there’s a subsequence where good feedback is possible, and is discussed significantly in section 4.3 of the logical induction paper. If there’s a subsequence B (of your subsequence of interest, A) where you can get good feedback, then there’s infinite exploration steps on subsequence B (and also on A because it contains B) This post is hereby deprecated. Still right, just not that relevant. reply

NEW DISCUSSION POSTS

[Note: This comment is three
 by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
 by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
 by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
 by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
 by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes