Вы здесь

Новости LessWrong.com

Подписка на Лента Новости LessWrong.com Новости LessWrong.com
A community blog devoted to refining the art of rationality
Обновлено: 3 минуты 52 секунды назад

Collaboration-by-Design versus Emergent Collaboration

18 ноября, 2018 - 10:22
Published on Sun Nov 18 2018 07:22:16 GMT+0000 (UTC)

Introduction

This seems to be a non-trivial problem for even current narrow AI, which is much more problematic for strong NAI, which I haven't seen called out or named explicitly. I provide a quick literature review to explain why I think it's ignored in classic multi-agent system design. (But I might be corrected)

It is unclear to me whether we can expect even introspective GAI to "just solve it" by noticing that it is a problem and working to fix it, given that people often don't seem to manage it.

The problem

One challenge for safe AI is the intrinsic difficulty of coordination problems. This includes coordination with humans, coordination with other AI systems, and potentially self-coordination when AI uses multiple agents. Unfortunately, the typical system design intends to maximize some fitness function, not to coordinate in order to allow mutually beneficial interaction.

There is extensive literature on multi-agent coordination for task-based delegation and cooperation, dating back to at least the 1980 Contract Net Interaction Protocol, which allows autonomous agents to specify markets for interaction. This is useful, but doesn't avoid any of the problems with market failures and inadequate equillibria. (In fact, it probably induces such failures, since individual contracts are the atomic unit or interaction.) Extensive follow-up work on distributed consensus problems assumes that all agents are built to achieve consensus. This may be important for AI coordination, but requires clearly defined communication channels and well-understood domains. Work on Collaborative Intelligence is also intended to allow collaboration, but it is unclear that there is substantive ongoing work in that area. Multiscale decision theory attempts to build multi-scale models for decision making, but is not tied explicitly to multiple agents.

What most of the literature shares is an assumption that agents will be designed for cooperation and collaboration. Inducing collaboration in agents not explicitly designed for that task is a very different problem, as is finding coordinated goals that can be achieved.

"Solutions"?

The obvious solution is to expect multi-agent systems to have agents with models of other agents that are sophisticated enough to build strategies that allow collaboration. In situations where multiple equilibria exist, moving from pareto-dominated equilibria to better ones often requires coordination, which requires understanding that initially costly moves towards the better equilibrium will be matched by other players. As I argued earlier, there are fundamental limitations on the models of embedded agents that we don't have good solutions to. (If we find good ways to build embedded agents, we may also find good ways to design embedded agents for cooperation. This isn't obvious.)

Collaboration-by-design, on the other hand, is much easier. Unfortunately, AI-race dynamics make it seem unlikely. The other alternative is to explicitly design safety parameters, as Mobileye has done for self driving cars with "RSS" - limiting the space in which they can make decisions to enforce limits about how cars interact. This seems intractable in domains where safety is ill-defined, and seems to require much better understanding of corrigibility, at the very least.

Next Steps

Perhaps there are approaches I haven't considered, or reasons to think this isn't a problem. Alternatively, perhaps there is a clearer way to frame the problem that exists ow which I am unaware, or the problem could be framed more clearly in a way I am not seeing. As a first step, progress on identification on either front seems useful.



Discuss

Ia! Ia! Extradimensional Cephalopod Nafl'fhtagn!

18 ноября, 2018 - 02:00
Published on Sat Nov 17 2018 23:00:05 GMT+0000 (UTC)

Hello, I'm ExCeph (short for Extradimensional Cephalopod). I've been mostly lurking here for the past decade and occasionally commenting within the past year or so. However, I never got around to actually introducing myself until now. It's good to meet you.

I was advised by a friend to actually write up a short bio, so here’s a bit about me.

*starts puffing a bubble pipe*

I grew up on science fiction and fantasy, plowing through satirical books such as the Discworld series by Terry Pratchett and the MythAdventures series by Robert Asprin, which inspired me to approach problems with a clear and critical mind.

One of my high school friends introduced me to both Less Wrong and Harry Potter and the Methods of Rationality, which resonated with me. I read HPMOR up through its then most recent update and moved on to other rational fiction, like Luminosity and Elcenia. I also acquired an addiction to taste for reading TVTropes, which has Enhanced My Life. (But ask your doctor if TVTropes is right for you).

Reading through some Less Wrong and Slate Star Codex articles about the inadequacy of existing institutions confirmed my childhood suspicions that humans didn’t really know what they were doing with the world. I became extremely frustrated that fixing these institutions was not a public priority, as if no one was aware of what was wrong or how to approach the situation.

It was the summer before my senior year of high school when I came up with the first version of my insanely ambitious plan to change the world, which has been my main project ever since. As part of the plan, I researched and tested different concepts and tools to improve my productivity and my ability to effect positive change in the world, with sporadic progress.

During my first job out of college, I reached out to find other people who wanted to change the world, and that led me to the local effective altruism community. As a result, I spent some time volunteering with an effective altruist organization. Eventually, through both the job and the EA organization, I discovered I was still missing some fundamental attributes that nobody responsible for my education had noticed or figured out how to instill in me.

Since then I've spent the past year and a half refining and practicing the tools and attributes I'd discovered, and am now ready to participate in the rationality community. I hope you find my suggestions and perspectives useful.

Okay, I’m out of bubble fluid. *withdraws into the abyss*



Discuss

Effective Altruism, YouTube, and AI (talk by Lê Nguyên Hoang)

17 ноября, 2018 - 22:21
https://i.ytimg.com/vi/sivsXJ1L1pg/maxresdefault.jpg

An unaligned benchmark

17 ноября, 2018 - 18:51
Published on Sat Nov 17 2018 15:51:03 GMT+0000 (UTC)

My goal is to design AI systems that are aligned with human interests and competitive with unaligned AI.

I find it useful to have a particular AI algorithm in mind. Then I can think about how that algorithm could cause trouble, and try to find a safer variant.

I think of the possibly-unaligned AIs as a benchmark: it’s what AI alignment researchers need to compete with. The further we fall short of the benchmark, the stronger the competitive pressures will be for everyone to give up on aligned AI and take their chances.

I have a few standard benchmarks I keep in mind. This post describes one of those benchmarks. It also tries to lay out clearly why I think that benchmark is unsafe, and explains how I think my current research could make a safe version.

I. Model-based RL with MCTS

We train three systems in parallel:

  • A generative model to sample sequences of observations, conditioned on sequences of actions.
  • A reward function that takes as input a sequence of actions and predicted observations and produces a reward.
  • A policy and value function which take as input a sequence of observations and produce the next action and an estimate of the future return.

We train the policy and value function using (roughly) the AlphaZero algorithm: Use MCTS to improve the current policy. Update the policy at the root to predict the best move found by MCTS, update the value to predict its predicted value. Use the generative model to sample environment transitions and the reward function (with a small discount rate) to score them.

We train an autoregressive generative model, to maximize the log probability assigned to the actual sequence of actions and observations produced by the AI (with each observation conditioned on the past actions). This isn’t actually a good way to train the generative model, but it’s not really central to the discussion.

We train the reward function by showing humans sequences of actions and predicted observations, asking them to assign scores, then predicting those scores with supervised learning. We show humans the sequences of actions that look most promising to the system.

There are plenty of details you’d need in order to make this work well, but that’s the basic idea. When applied with very powerful networks, it’s plausible that this system would be able to decisively outcompete humans. It would be capable performing a large intelligent search over long sequences of actions to find those that would be rated highly.

II. What goes wrong?

There are two classes of problems:

Problem 1: Bad objective

The goal of the system is to produce (action, observation) sequences that look good to humans. I claim that optimizing this objective faithfully will lead to bad outcomes.

As the system improves, the rationale of many individual actions will become incomprehensible to a human overseer. At this point the only option for a human is to evaluate sequence of observations based on whether the consequences look good.

The observations present a narrow view of the world, and I strongly suspect that the AI will find sequences of actions that make that narrow view look good without actually being good.

Control vs. intrinsic goodness. I think there are two strategies for defining a reward function:

  1. Reward worlds in which humans remain in control of the situation, in which they are able to get accurate information and correct course as needed.
  2. Reward worlds in which intrinsically good things are happening

Both of these strategies seem unworkable.

Strategy #1: maintaining control. This appears to be unworkable because determining if humans are actually in control is incredibly difficult — at best you can tell whether they appear to be and feel in control. It’s very hard to understand if the humans are getting accurate information, if their understanding of the situation is roughly accurate, if their instructions are being faithfully executed, and so on. This is already an incredibly hard problem amongst humans and gets way harder as the AI gets smarter.

This problem is serious because, if there is even a small gap between the “real” notion of being in control (which an AI cares about in order to generate maximally appealing observation sequences further into the future) and a superficial appearance of control (which the reward function incentivizes), then the AI is going to exploit that gap by taking the real notion of control for itself and giving humans the appearance of control. Of course, if the long-term goals of the AI and human are well-aligned then there would be no conflict of interest, but trying to ensure that alignment brings us back to strategy #2 which I will argue is unworkable.

You could potentially notice this problem by looking ahead to the point where humans attempt to exercise control — if the humans don’t get what they want, then they must not have really been in control. But evaluating whether they get what they want brings us back to strategy #2.

Strategy #2: evaluating goodness. This appears to be unworkable because it requires evaluating human preferences over very large objects (the whole world) under very complex conditions (in the far future, where we’ve had to make many decisions about what kind of world we want to have).

I am quite confident that “world which looks appealing on screen” is not the same as “world which is good;” the gap is already large today, and it will grow much larger over time.

Maintaining a fiction. Ultimately the goal of this AI is to make the sensors look like good things are happening in the world. This can be done either by making the world good or by carefully controlling what gets fed to the sensors. In general, there are many fewer constraints on “what gets fed to the sensors” than “what the world is actually like,” and so it’s going to be possible to produce much more desirable-looking outcomes, much more easily, by controlling the sensors.

If the humans understand what the AI is doing in detail then they can observe the sequence of actions to notice any actions that might corrupt the sensors. But as soon as the AI is engaging in complicated plans this appears to be totally intractable. Even if the AI was human-level, there are many extremely hard-to-detect plans: for example, the AI could collaborate with an external attacker, who will surreptitiously corrupt the sensor. Or the AI could create a copy of itself on an external server who then helped orchestrate a hard-to-detect corruption.

These actions would be very hard to detect even if you were monitoring a human-level intelligence, and the situation seems hopeless for much more powerful searches. Moreover, because you are searching over sequences of actions for those that receive high reward, you are directly applying optimization power to discovering covert attacks.

Other problems. I have a (fairly common) intuition that applying extremely powerful optimization at a target that isn’t quite what you want will often lead to bad outcomes. The discussion above is not exhaustive, but I think it is illustrative.

Problem 2: distributional shift (and optimization daemons)

Our training procedure produces a policy and value function, most likely represented as (really big) neural networks. At test time, we combine these the policy and value with MCTS to decide on actions.

The value function and policy have been optimized to yield good performance on the data points we’ve seen so far, as judged by human evaluations. Unfortunately, there are likely to be a very large number of networks that encode the “wrong” goals but which also yield good performance. These networks will generalize poorly, and moreover when they fail to generalize they can result in an extremely powerful optimization process being pointed at the wrong objective.

A story about training. Originally the policy and value function don’t encode anything at all. Over time, they begin to encode a complicated soup of heuristics which is correlated with good performance. If we are training sufficiently powerful models we hope they will eventually perform reasoning about outcomes. For example, the policy could learn to backwards chain from heuristics about what is valuable in order to decide which moves are good. This is what we are trying to do — the policy is supposed to backwards chain, it’s the only part of the system that can use heuristics in order to prioritize the search.

What humans actually want is somewhat complicated, so it seems quite likely that it’s easier for models to pursue a complicated soup of heuristic goals than to understand exactly what we want. This is similar to the way in which humans acquired an extremely rich set of goals even though we were optimized according to evolutionary fitness. This is a complicated question, but I think it’s the theoretical picture and I think historical experience with deep learning points tends to support it.

As the system improves, the reward function encourages it to exhibit an increasingly precise understanding of what we want. Unfortunately there are two ways to do this:

  • The intended way: adjust the implicit goals baked into the model such that they converge towards “be helpful to humans.” In the analogy to humans, this is like humans caring more and more about reproductive fitness (and less and less about things like beauty or fun except insofar as they are useful for reproductive fitness).
  • The unintended way: correctly understand that earning human approval is necessary to survival and hence to achieving other goals, and act accordingly. In the analogy to humans, this is like humans continuing to care about beauty and fun, but believing that they need to have kids in order to realize those goals in the long run.

In practice, I expect both of these changes to occur to some extent, ending up with a model that has somewhat wrong goals together with an instrumental desire to appear helpful.

Catastrophic failure. This could lead to a catastrophic failure in a few different ways:

  • An attacker deliberately produces inputs that drive our AI off of the training distribution, and it starts pursuing the wrong goals. That AI may then launch a similar attack against other AI systems it has access to, leading to cascading failures (as with a computer virus). Or an attacker may be able to simultaneously compromise a large number of systems.
  • As AI systems acquire increasing influence in the world, they necessarily move off the training distribution. Eventually this sparks a failure in some systems. These failures could cause chaos in the world, pushing us further from the training distribution and leading to cascading failures; or they may all be triggered by the same events and so be correlated.

In either case, we could end up with a massive correlated failure of AI systems, where they start effectively maximizing the wrong goals. That looks effectively like a conflict between us and the AI systems we’ve built (just as a virus might effectively lead to a conflict between you and the computer you bought). If the AI systems either have significant responsibilities, or are much more intelligent than unaided humans, then there may not be any way to recover from this failure.

Problem 1.5: non-robust reward functions

There is another risk at the intersection between robustness and value specification.

We may learn a model of human approval which is accurate on the training distribution, but incorrectly assigns a very high value to some bad outcomes that didn’t appear in training. Indeed, recent experience with adversarial examples suggests that our models often have very strange behavior on parts of the input space not visited in training and that this problem can be hard to correct. Presumably some of these inputs would be assigned unusually high values (just as some would be assigned unusually low values).

In order to reach the most pathological cases, the agent needs significant control over its own observations, which in in turn requires control over its environment. So even if the pathological inputs aren’t any worse than random on average, the ones that the system is able to reach will systematically be those where it has acquired enough influence to control its own observations.

We can potentially correct this problem by eliciting human feedback for the problematic observations and then adding them to the training set. We’re only in serious trouble if the reward function is really hard to fix. In that case, we may instead make it harder and harder for the system to modify its own observations. After a while, we might train a system which is only able to control its observations by physically overpowering us and causing a catastrophe.

III. How the problem might be fixed

I think that my research has a chance of producing an AI that (a) is nearly-as-good as the benchmark, but (b) doesn’t do anything terrible.

The main changes are:

  • Rather than learning the environment model directly from observation, produce it by amplification. The amplification process can use exactly the same data about the world (treating the data as an external resource), and it can ultimately be distilled into a neural network just like the one you would have trained. The important difference is that we now have a way to link the generative model back to (an astronomically large number of) human-comprehensible operations on human-comprehensible data and a sequence of decoders which can map from the latent space of the generative model to an implicit human-comprehensible representation.
  • Rather than learning a reward function from human data, we also train it by amplification (acting on the same representations used by the generative model). Again, we can distill the reward function into a neural network that acts on sequences of observations, but now instead of learning to predict human judgments it’s predicting a very large implicit deliberation.
  • In addition to training the policy and value function using RL, we use some combination of these techniques to ensure there is no series of observations on which the policy behaves extremely badly. For example, we may use amplification in order to understand what the policy is doing, then use that understanding in order to identify possible (pseudo-)inputs on which the policy behaves badly, then add those (pseudo-)inputs to the training set.

Competitiveness depends on three properties:

  • Training a predictor using amplification makes predictions at least as good as training a generative model directly.
  • The worst-case training for the policy and value function don’t interfere significantly with average case performance.
  • Amplification doesn’t add much overhead to the training process.

Safety is more subtle. It depends on three properties each defined in terms of some as-yet-undefined notion of “bad” behavior (incorrigible is the current leading candidate):

  1. On average, the reward function incentivizes behavior which competes effectively and gives the user effective control.
  2. There do not exist inputs on which the policy choose an action because it is bad, or the value function outputs a high reward because the prior behavior was bad. (Or else the policy on its own will generate bad consequences.)
  3. The reward function never gives a behavior a higher reward because it is bad. (Or else the test-time optimization by MCTS can generate bad behavior.) For example, if the AI deludes the human operator so that the operator can’t interfere with the AI’s behavior, that behavior can’t receive a higher reward even if it ultimately allows the AI to make more money.
My goals

In order to make all of that work, we’d need to solve a few research problems.

Reliability. Some combination of these techniques needs to successfully eliminate all bad behavior (and in particular to control optimization daemons).

Amplification. Amplification needs to be good enough for these three tasks:

  • Learn models that make competitive predictions about the world, and which are “understandable” enough that we can…
  • Implement a reward function, defined on those models, that correctly rewards competitive behavior and penalizes bad behavior.
  • Understand the internals of competitive machine learning systems, well enough to do informed oversight and to help with reliability (if interpretability is an important ingredient for reliability). Probably the key requirement is reliably identifying bad behavior.

(Without introducing significant overhead.)

Understanding bad behavior. In order to do either of the above we need some suitable notion of “bad” behavior, such that:

  • Avoiding bad behavior is sufficient to avoid catastrophic outcomes.
  • Bad behavior is an act of commission that is “easy” to avoid, such that it can be achieved in the worst case.
  • We can learn a reward function over that avoids creating instrumental incentives for bad behavior, e.g. by punishing any bad behavior which played an important role in receiving a high reward. (This is only plausible because our reward function operates on sequences of predicted states, and so if bad behavior is instrumentally useful it must be because the model “knows about” it.)

The next post in this sequence will be "Prosaic AI Alignment" by Paul Christiano, on Monday 19th November.

Tomorrow's AI Alignment Forum sequences post will be "Diagonalization Fixed Point Exercises" by Scott Garrabrant and Sam Eisenstat in the sequence "Fixed Points".



Discuss

On Rigorous Error Handling

17 ноября, 2018 - 12:20
Published on Sat Nov 17 2018 09:20:00 GMT+0000 (UTC)

In my long career as a programmer I've seen a lot of projects with a lot of error handling practices and, sadly, almost none that actually worked.

We are facing facing few high-level problems here:

  1. For many applications error handling is not critical.
  2. Error handling code is rarely executed. Consequently, it looks like it works until it doesn't.
  3. Programmers want to implement new features. Writing error handling is just an annoyance that slows them down.
Who cares about error handling?

For many applications writing rigorous error handling code doesn't pay off.

As long as you have some semi-decent way to deal with errors transparently (e.g. exceptions) you are fine. If there's a problem, throw an exception. On the top level catch all the exceptions and open a dialog box with the error message (in frontend applications) or write it to the log (on the server).

The above, of course, means that you hope that, after the exception is processed, the application will we left in a consistent, functional state. Once again, you HOPE. You do not KNOW. You do not know because, when writing the application, you haven't thought about error handling at all.

Now, don't get me wrong. I am not saying that you should never do this. It often makes sense from economic perspective. Writing rigorous error handling is expensive. If the worst thing that can happen is that a frontend application crashes once in a long while making user curse and restart it, then it's totally not worth doing.

However, there is also a different kind of application. There are medical application where the patient dies if they misbehave. There are space probes that crash into plantes, taking millions of dollars of investment as well as scientific careers down with them. There are HFT application which can generate bazillion of dollars of loss for every minute of downtime.

In these cases it's definitely worth writing rigorous error handling code.

That much everybody agrees with.

However, it is often not explicitly understood that whenever you are writing a piece of infrastructure (as opposed to a client-facing application) you are always in the latter category.

A piece of infrastructure can be used in a medical application, in a space probe, in a high-frequency trading system, but unless it's a commercial product and you take care not to sell it to anyone who looks too important to fail, then you have no way to prevent that.

Ergo, if you are doing infrastructure, you should always do rigorous error handling.

Error handling code is never executed

The mainstream attitude to fixing bugs at the moment is "run it, see what fails, then fix it". That's why we write tests. Tests make the code run and, hopefully, fail if there's a problem. That's why we have user-facing issue trackers. If a bug gets past testing, it will fail for the user and user will fill in a bug report — or so we hope, at least.

But the error handling code is, almost by definition, executed only rarely. And code that is triggered by two concurrent problems is executed almost never at all.

Therefore, tests are not likely to help. User reports may catch the issue, but are often closed with "cannot reproduce" status.

There are alternative approaches, like formal verification or fuzzing, but almost nobody uses those.

In the end, we want programmers writing error handling code that works on the first try, without any testing.

And that is, of course, impossible to do. But, on the other hand, it's not black and white. Errors are rare and if the bugs in error handling code get rare as well then you can increase the reliability of the system from, say, three nines to five nines. And as medical applications go, adding one nine of reliability saves some actual human lives.

The dilemma

So here we are. We have programmers who want to spend no time on error handling, who just want to move on and implement cool new features, and we want them to write perfect error handling code on the first try, without testing.

Even worse, attempts to solve the first problem (to make error handling invisible) often make the second problem (failure-proof error handling) even more complex. And given that everyone is writing new code all the time, but errors are rare, the solutions to the first problem are going to proliferate even at the expense of making the second problem harder or even impossible to solve.

An example

Let's have a look at OpenSSL API. I don't want to pick on OpenSSL, mind you. You'll encounter similar kind of problem with almost any library, but I happened to work with OpenSSL lately so that's what I'll use as an example. Also note that OpenSSL is notoriously underfunded, so instead of getting angry at them, do your bit and send them a donation.

Anyway, when an OpenSSL function fails it reports that it failed and you can have a look at the "error queue". Error queue is effectively a list of integer error codes. The list of error codes can be found here.

Note how documentation of an error code invariably looks like this:

#define ERR_R_BAD_GET_ASN1_OBJECT_CALL 60 Definition at line 296 of file err.h.

Yes, you get a cryptic string, a cryptic number, and a reference to the line in the source code. If you look at the source code you'll find a cryptic string and a cryptic number again. No explanation of what the error means whatsoever.

Now think for a second about how you would, as a user, handle such an error. It's a multidimensional beast and it's not even clear whether order of errors matters or not. And each error is itself chosen from a large set of cryptic errors with no explicit associated semantics at all. Needless to say, the set of error codes is going to expand in newer versions, so even if you handled every single one of them correctly you can still get a nasty failure at some point in the future.

So what I've ended up doing was logging all the errors from the queue for debugging purposes and converting the entire thing into a single "OpenSSL failed" error. I am not proud of that but I challenge you to come up with a better solution.

And no, passing the monstrosity to the caller, who has even less context about how to handle it than you have, and breaking the encapsulation properties along the way, is not an option.

The takeaway from the example is that even if you are willing to do rigorous error handling, the underlying layers often give you no chance but to go the easy and sloppy way.

As a side note, OpenSSL's system of reporting errors is by no means the worst of all. Consider typical exceptions as they appear in most languages. Exception is not a list of error codes. It's an object. In other words, it can be a list, a map, a binary tree or whatever you want, really. There's absolutely no way to deal with this Turing-complete beast is a systemic way.

What's needed

When you look at it from the point of view of the user of the API, the requirements are suddenly crystal-clear. If you are to do rigorous error handling you want a small amount of well-defined failure modes.

A function may succeed. Or it may, for example, fail because of disconnected backend. Or it may time out. And that's it. There are only two failure modes and they are documented as a part of the API. Once you have that, the error handling becomes obvious:

int err = some_library_function(); if(err != 0) { swich(err) { case ECONNRESET: ... case ETIMEDOUT: ... default: assert(0); // the function violates its specification } }

Some libraries are closer to this ideal state, some are further away.

As already mentioned, classic exceptions are the worst. You get an object, or worse, just an interface that you can (the horror!) downcast to an actual exception class. All bets are off.

OpenSSL's approach is somewhat better. You still get a list of error codes, but at least you know it's a list and not a map or something else.

Some libraries go further in the right direction and return a single error, but the list of error codes is long, poorly documented and subject to the future growth. Moreover, there's no clear association between a function and the error codes it can return. You have to expect any error code when calling any function. Often, the rigorous error handling code, as show above, would have to have dozens if not hundreds of error codes in the switch statement.

When possible errors are part of the function specification, on the other hand, we are almost OK. This is the case with I've also tried to used the same approach with my own libraries, such as [http://libdill.org/documentation.html libdill. However, even in this case it's possible to do it wrong. The list of possible errors in POSIX specification of [view-source:https://pubs.opengroup.org/onlinepubs/009695399/functions/connect.html connect() API] lists more than a dozen of possible errors which in turn disincentivizes the user from doing rigorous error handling.

In the best of the cases, the list of errors is small not only for a particular function, but also for the library as a whole. In my experience, it's entirely possible to do with as little as 10-15 different error codes for the entire library.

The advantage of that approach is twofold.

First, the user, as they use the library, will eventually learn those error codes and what they mean by heart. That in turn makes writing rigorous error handling code much less painful.

Second, a limited set of error codes makes the implementer of the library to actually think about the failure modes. If he can just define a new error code for every error condition he encounters, it's an easy way out with no need to do much thinking. If, on the other hand, he has to choose one of 10 possible error code, he has to think about which of them matches the semantics of the error the best. Which in turn results in a better, more consistent library, which it is joy to use.

November 17th, 2018

by martin_sustrik



Discuss

Act of Charity

17 ноября, 2018 - 08:19
Published on Sat Nov 17 2018 05:19:20 GMT+0000 (UTC)

(Cross-posted from my blog)

The stories and information posted here are artistic works of fiction and falsehood. Only a fool would take anything posted here as fact.

—Anonymous

Act I.

Carl walked through the downtown. He came across a charity stall. The charity worker at the stall called out, "Food for the Africans. Helps with local autonomy and environmental sustainability. Have a heart and help them out." Carl glanced at the stall's poster. Along with pictures of emaciated children, it displayed infographics about how global warming would cause problems for African communities' food production, and numbers about how easy it is to help out with money. But something caught Carl's eye. In the top left, in bold font, the poster read, "IT IS ALL AN ACT. ASK FOR DETAILS."

Carl: "It's all an act, huh? What do you mean?"

Worker: "All of it. This charity stall. The information on the poster. The charity itself. All the other charities like us. The whole Western idea of charity, really."

Carl: "Care to clarify?"

Worker: "Sure. This poster contains some correct information. But a lot of it is presented in a misleading fashion, and a lot of it is just lies. We designed the poster this way because it fits with people's idea is of a good charity they should give money to. It's a prop in the act."

Carl: "Wait, the stuff about global warming and food production is a lie?"

Worker: "No, that part is actually true. But in context we're presenting it as some kind of imminent crisis that requires an immediate infusion of resources, when really it's a very long-term problem that will require gradual adjustment of agricultural techniques, locations, and policies."

Carl: "Okay, that doesn't actually sound like more of a lie than most charities tell."

Worker: "Exactly! It's all an act."

Carl: "So why don't you tell the truth anyway?"

Worker: "Like I said before, we're trying to fit with people's idea of what a charity they should give money to looks like. More to the point, we want them to feel compelled to give us money. And they are compelled by some acts, but not by others. The idea of an immediate food crisis creates more moral and social pressure towards immediate action, than the idea that there will be long-term agricultural problems that require adjustments.

Carl: "That sounds...kind of scammy?"

Worker: "Yes, you're starting to get it! The act is about violence! It's all violence!"

Carl: "Now hold on, that seems like a false equivalence. Even if they were scammed by you, they still gave you money of their own free will."

Worker: "Most people, at some level, know we're lying to them. Their eyes glaze over 'IT IS ALL AN ACT' as if it were just a regulatory requirement to put this on charity posters. So why would they give money to a charity that lies to them? Why do you think?"

Carl: "I'm not nearly as sure as you that they know this! Anyway, even if they know at some level it's a lie, that doesn't mean they consciously know, so to their conscious mind it seems like being completely heartless."

Worker: "Exactly, it's emotional blackmail. I even say 'Have a heart and help them out'. So if they don't give us money, there's a really convenient story that says they're heartless, and a lot of them will even start thinking about themselves that way. Having that story told about them opens them up to violence."

Carl: "How?"

Worker: "Remember Martin Shkreli?"

Carl: "Yeah, that asshole who jacked up the Daraprim prices."

Worker: "Right. He ended up going to prison. Nominally, it was for securities fraud. But it's not actually clear that whatever security fraud he did was worse than what others in his industry were doing. Rather, it seems likely that he was especially targeted because he was a heartless asshole."

Carl: "But he still broke the law!"

Worker: "How long would you be in jail if you got punished for every time you had broken the law?"

Carl: "Well, I've done a few different types of illegal drugs, so... a lot of years."

Worker: "Exactly. Almost everyone is breaking the law. So it's really, really easy for the law to be enforced selectively, to punish just about anyone. And the people who get punished the most are those who are villains in the act."

Carl: "Hold on. I don't think someone would actually get sent to prison because they didn't give you money."

Worker: "Yeah, that's pretty unlikely. But things like it will happen. People are more likely to give if they're walking with other people. I infer that they believe they will be abandoned if they do not give."

Carl: "That's a far cry from violence."

Worker: "Think about the context. When you were a baby, you relied on your parents to provide for you, and abandonment by them would have meant certain death. In the environment of evolutionary adaptation, being abandoned by your band would have been close to a death sentence. This isn't true in the modern world, but people's brains mostly don't really distinguish abandonment from violence, and we exploit that."

Carl: "That makes some sense. I still object to calling it violence, if only because we need a consistent definition of 'violence' to coordinate, well, violence against those that are violent. Anyway, I get that this poster is an act, and the things you say to people walking down the street are an act, but what about the charity itself? Do you actually do the things you say you do?"

Worker: "Well, kind of. We actually do give these people cows and stuff, like the poster says. But that isn't our main focus, and the main reason we do it is, again, because of the act."

Carl: "Because of the act? Don't you care about these people?"

Worker: "Kind of. I mean, I do care about them, but I care about myself and my friends more; that's just how humans work. And if it doesn't cost me much, I will help them. But I won't help them if it puts our charity in a significantly worse position."

Carl: "So you're the heartless one."

Worker: "Yes, and so is everyone else. Because the standard you're set for 'not heartless' is not one that any human actually achieves. They just deceive themselves about how much they care about random strangers; the part of their brain that inserts these self-deceptions into their conscious narratives is definitely not especially altruistic!"

Carl: "According to your own poster, there's going to be famine, though! Is the famine all an act to you?"

Worker: "No! Famine isn't an act, but most of our activities in relation to it are. We give people cows because that's one of the standard things charities like ours are supposed to do, and it looks like we're giving these people local autonomy and stuff."

Carl: "Looks like? So this is all just optics?"

Worker: "Yes! Exactly!"

Carl: "I'm actually really angry right now. You are a terrible person, and your charity is terrible, and you should die in a fire."

Worker: "Hey, let's actually think through this ethical question together. There's a charity pretty similar to ours that's set up a stall a couple blocks from here. Have you seen it?"

Carl: "Yes. They do something with water filtering in Africa."

Worker: "Well, do you think their poster is more or less accurate than ours?"

Carl: "Well, I know yours is a lie, so..."

Worker: "Hold on. This is Gell-Mann amnesia. You know ours is a lie because I told you. This should adjust your model of how charities work in general."

Carl: "Well, it's still plausible that they are effective, so I can't condemn—"

Worker: "Stop. In talking of plausibility rather than probability, you are uncritically participating in the act. You are taking symbols at face value, unless there is clear disproof of them. So you will act like you believe any claim that's 'plausible', in other words one that can't be disproven from within the act. You have never, at any point, checked whether either charity is doing anything in the actual, material world."

Carl: "...I suppose so. What's your point, anyway?"

Worker: "You're shooting the messenger. All or nearly all of these charities are scams. Believe me, we've spent time visiting these other organizations, and they're universally fraudulent, they just have less self-awareness about it. You're only morally outraged at the ones that don't hide it. So your moral outrage optimizes against your own information. By being morally outraged at us, you are asking to be lied to."

Carl: "Way to blame the victim. You're the one lying."

Worker: "We're part of the same ecosystem. By rewarding a behavior, you cause more of it. By punishing it, you cause less of it. You reward lies that have plausible deniability and punish truth, when that truth is told by sinners. You're actively encouraging more of the thing that is destroying your own information!"

Carl: "It still seems pretty strange to think that they're all scams. Like, some of my classmates from college went into the charity sector. And giving cows to people who have food problems actually seems pretty reasonable."

Worker: "It's well known by development economists that aid generally creates dependence, that in giving cows to people we disrupt their local economy's cow market, reducing the incentive to raise cattle. And in theory it could still be worth it, but our preliminary calculations indicate that it probably isn't."

Carl: "Hold on. You actually ran the calculation, found that your intervention was net harmful, and then kept doing it?"

Worker: "Yes. Again, it is all—"

Carl: "What the fuck, seriously? You're a terrible person."

Worker: "Do you think any charity other than us would have run the calculation we did, and then actually believe the result? Or would they have fudged the numbers here and there, and when even a calculation with fudged numbers indicated that the intervention was ineffective, come up with a reason to discredit this calculation and replace it with a different one that got the result they wanted?"

Carl: "Maybe a few... but I see your point. But there's a big difference between acting immorally because you deceived yourself, and acting immorally with a clear picture of what you're doing."

Worker: "Yes, the second one is much less bad!"

Carl: "What?"

Worker: "All else being equal, it's better to have clearer beliefs than muddier ones, right?"

Carl: "Yes. But in this case, it's very clear that the person with the clear picture is acting immorally, while the self-deceiver, uhh.."

Worker: "...has plausible deniability. Their stories are plausible even though they are false, so they have more privilege within the act. They gain privilege by muddying the waters, or in other words, destroying information."

Carl: "Wait, are you saying self-deception is a choice?"

Worker: "Yes! It's called 'motivated cognition' for a reason. Your brain runs something like a utility-maximization algorithm to tell when and how you should deceive yourself. It's epistemically correct to take the intentional stance towards this process."

Carl: "But I don't have any control over this process!"

Worker: "Not consciously, no. But you can notice the situation you're in, think about what pressures there are on you to self-deceive, and think about modifying your situation to reduce these pressures. And you can do this to other people, too."

Carl: "Are you saying everyone is morally obligated to do this?"

Worker: "No, but it might be in your interest, since it increases your capabilities."

Carl: "Why don't you just run a more effective charity, and advertise on that? Then you can outcompete the other charities."

Worker: "That's not fashionable anymore. The 'effectiveness' branding has been tried before; donors are tired of it by now. Perhaps this is partially because there aren't functional systems that actually check which organizations are effective and which aren't, so scam charities branding themselves as effective end up outcompeting the actually effective ones. And there are organizations claiming to evaluate charities' effectiveness, but they've largely also become scams by now, for exactly the same reasons. The fashionable branding now is environmentalism."

Carl: "This is completely disgusting. Fashion doesn't help people. Your entire sector is morally depraved."

Worker: "You are entirely correct to be disgusted. This moral depravity is a result of dysfunctional institutions. You can see it outside charity too; schools are authoritarian prisons that don't even help students learn, courts put people in cages for not spending enough on a lawyer, the US military blows up civilians unnecessarily, and so on. But you already knew all that, and ranting about these things is itself a trope. It is difficult to talk about how broken the systems are without this talking itself being interpreted as merely a cynical act. That's how deep this goes. Please actually update on this rather than having your eyes glaze over!"

Carl: "How do you even deal with this?"

Worker: "It's already the reality you've lived in your whole life. The only adjustment is to realize it, and be able to talk about it, without this destroying your ability to participate in the act when it's necessary to do so. Maybe functional information-processing institutions will be built someday, but we are stuck with this situation for now, and we'll have no hope of building functional institutions if we don't understand our current situation."

Carl: "You are wasting so much potential! With your ability to see social reality, you could be doing all kinds of things! If everyone who were as insightful as you were as pathetically lazy as you, there would be no way out of this mess!"

Worker: "Yeah, you're right about that, and I might do something more ambitious someday, but I don't really want to right now. So here I am. Anyway... food for the Africans. Helps with local autonomy and environmental sustainability. Have a heart and help them out."

Carl sighed, fished a 10 dollar bill from his wallet, and gave it to the charity worker.



Discuss

Fixed Point Exercises

17 ноября, 2018 - 04:43
Published on Sat Nov 17 2018 01:39:50 GMT+0000 (UTC)

Sometimes people ask me what math they should study in order to get into agent foundations. My first answer is that I have found the introductory class in every subfield to be helpful, but I have found the later classes to be much less helpful. My second answer is to learn enough math to understand all fixed point theorems. These two answers are actually very similar. Fixed point theorems span all across mathematics, and are central to (my way of) thinking about agent foundations.

This post is the start of a sequence on fixed point theorems. It will be followed by several posts of exercises that use and prove such theorems. While these exercises aren't directly connected to AI safety, I think they're quite useful for preparing to think about agent foundations research. Afterwards, I will discuss the core ideas in the theorems and where they've shown up in alignment research.

The math involved is not much deeper than a first course in the various subjects (logic, set theory, topology, computability theory, etc). If you don't know the terms, a bit of googling, wikipedia and math.stackexchange should easily get you most of the way. Note that the posts can be tackled in any order.

Here are some ways you can use these exercises:

  • You can host a local MIRIx group, and go through the exercises together. This might be useful to give a local group an affordance to work on math rather than only reading papers.
  • You can work on them by yourself for a while, and post questions when you get stuck. You can also post your solutions to help others, let others see an alternate way of doing a problem, or help you realize that there is a problem with your solution.
  • You can skip to the discussion (which has some spoilers), learn a bunch of theorems from Wikipedia, and use this as a starting point for trying to understand some MIRI papers.
  • You can use answering these questions as a goalpost for learning a bunch of introductory math from a large collection of different subfields.
  • You can show off by pointing out that some of the questions are wrong, and then I will probably fix them and thank you.

The first set of exercises is here.

Thanks to Sam Eisenstat for helping develop these exercises, Ben Pace for helping edit the sequence, and many AISFP participants for testing them and noticing errors.

Meta

Read the following.

Please use the (new) spoilers feature - the symbol '>' followed by '!' followed by space - in your comments to hide all solutions, partial solutions, and other discussions of the math. The comments will be moderated strictly to cover up spoilers!

I recommend putting all the object level points in spoilers and leaving metadata outside of the spoilers, like so:

Here's my solution / partial solution / confusion for question #5:

And put your idea in here! (reminder: LaTex is cmd-4 / ctrl-4)



Discuss

Topological Fixed Point Exercises

17 ноября, 2018 - 04:42
Published on Sat Nov 17 2018 01:40:06 GMT+0000 (UTC)

.mjx-chtml {display: inline-block; line-height: 0; text-indent: 0; text-align: left; text-transform: none; font-style: normal; font-weight: normal; font-size: 100%; font-size-adjust: none; letter-spacing: normal; word-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; margin: 0; padding: 1px 0} .MJXc-display {display: block; text-align: center; margin: 1em 0; padding: 0} .mjx-chtml[tabindex]:focus, body :focus .mjx-chtml[tabindex] {display: inline-table} .mjx-full-width {text-align: center; display: table-cell!important; width: 10000em} .mjx-math {display: inline-block; border-collapse: separate; border-spacing: 0} .mjx-math * {display: inline-block; -webkit-box-sizing: content-box!important; -moz-box-sizing: content-box!important; box-sizing: content-box!important; text-align: left} .mjx-numerator {display: block; text-align: center} .mjx-denominator {display: block; text-align: center} .MJXc-stacked {height: 0; position: relative} .MJXc-stacked > * {position: absolute} .MJXc-bevelled > * {display: inline-block} .mjx-stack {display: inline-block} .mjx-op {display: block} .mjx-under {display: table-cell} .mjx-over {display: block} .mjx-over > * {padding-left: 0px!important; padding-right: 0px!important} .mjx-under > * {padding-left: 0px!important; padding-right: 0px!important} .mjx-stack > .mjx-sup {display: block} .mjx-stack > .mjx-sub {display: block} .mjx-prestack > .mjx-presup {display: block} .mjx-prestack > .mjx-presub {display: block} .mjx-delim-h > .mjx-char {display: inline-block} .mjx-surd {vertical-align: top} .mjx-mphantom * {visibility: hidden} .mjx-merror {background-color: #FFFF88; color: #CC0000; border: 1px solid #CC0000; padding: 2px 3px; font-style: normal; font-size: 90%} .mjx-annotation-xml {line-height: normal} .mjx-menclose > svg {fill: none; stroke: currentColor} .mjx-mtr {display: table-row} .mjx-mlabeledtr {display: table-row} .mjx-mtd {display: table-cell; text-align: center} .mjx-label {display: table-row} .mjx-box {display: inline-block} .mjx-block {display: block} .mjx-span {display: inline} .mjx-char {display: block; white-space: pre} .mjx-itable {display: inline-table; width: auto} .mjx-row {display: table-row} .mjx-cell {display: table-cell} .mjx-table {display: table; width: 100%} .mjx-line {display: block; height: 0} .mjx-strut {width: 0; padding-top: 1em} .mjx-vsize {width: 0} .MJXc-space1 {margin-left: .167em} .MJXc-space2 {margin-left: .222em} .MJXc-space3 {margin-left: .278em} .mjx-test.mjx-test-display {display: table!important} .mjx-test.mjx-test-inline {display: inline!important; margin-right: -1px} .mjx-test.mjx-test-default {display: block!important; clear: both} .mjx-ex-box {display: inline-block!important; position: absolute; overflow: hidden; min-height: 0; max-height: none; padding: 0; border: 0; margin: 0; width: 1px; height: 60ex} .mjx-test-inline .mjx-left-box {display: inline-block; width: 0; float: left} .mjx-test-inline .mjx-right-box {display: inline-block; width: 0; float: right} .mjx-test-display .mjx-right-box {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} .MJXc-TeX-unknown-R {font-family: monospace; font-style: normal; font-weight: normal} .MJXc-TeX-unknown-I {font-family: monospace; font-style: italic; font-weight: normal} .MJXc-TeX-unknown-B {font-family: monospace; font-style: normal; font-weight: bold} .MJXc-TeX-unknown-BI {font-family: monospace; font-style: italic; font-weight: bold} .MJXc-TeX-ams-R {font-family: MJXc-TeX-ams-R,MJXc-TeX-ams-Rw} .MJXc-TeX-cal-B {font-family: MJXc-TeX-cal-B,MJXc-TeX-cal-Bx,MJXc-TeX-cal-Bw} .MJXc-TeX-frak-R {font-family: MJXc-TeX-frak-R,MJXc-TeX-frak-Rw} .MJXc-TeX-frak-B {font-family: MJXc-TeX-frak-B,MJXc-TeX-frak-Bx,MJXc-TeX-frak-Bw} .MJXc-TeX-math-BI {font-family: MJXc-TeX-math-BI,MJXc-TeX-math-BIx,MJXc-TeX-math-BIw} .MJXc-TeX-sans-R {font-family: MJXc-TeX-sans-R,MJXc-TeX-sans-Rw} .MJXc-TeX-sans-B {font-family: MJXc-TeX-sans-B,MJXc-TeX-sans-Bx,MJXc-TeX-sans-Bw} .MJXc-TeX-sans-I {font-family: MJXc-TeX-sans-I,MJXc-TeX-sans-Ix,MJXc-TeX-sans-Iw} .MJXc-TeX-script-R {font-family: MJXc-TeX-script-R,MJXc-TeX-script-Rw} .MJXc-TeX-type-R {font-family: MJXc-TeX-type-R,MJXc-TeX-type-Rw} .MJXc-TeX-cal-R {font-family: MJXc-TeX-cal-R,MJXc-TeX-cal-Rw} .MJXc-TeX-main-B {font-family: MJXc-TeX-main-B,MJXc-TeX-main-Bx,MJXc-TeX-main-Bw} .MJXc-TeX-main-I {font-family: MJXc-TeX-main-I,MJXc-TeX-main-Ix,MJXc-TeX-main-Iw} .MJXc-TeX-main-R {font-family: MJXc-TeX-main-R,MJXc-TeX-main-Rw} .MJXc-TeX-math-I {font-family: MJXc-TeX-math-I,MJXc-TeX-math-Ix,MJXc-TeX-math-Iw} .MJXc-TeX-size1-R {font-family: MJXc-TeX-size1-R,MJXc-TeX-size1-Rw} .MJXc-TeX-size2-R {font-family: MJXc-TeX-size2-R,MJXc-TeX-size2-Rw} .MJXc-TeX-size3-R {font-family: MJXc-TeX-size3-R,MJXc-TeX-size3-Rw} .MJXc-TeX-size4-R {font-family: MJXc-TeX-size4-R,MJXc-TeX-size4-Rw} .MJXc-TeX-vec-R {font-family: MJXc-TeX-vec-R,MJXc-TeX-vec-Rw} .MJXc-TeX-vec-B {font-family: MJXc-TeX-vec-B,MJXc-TeX-vec-Bx,MJXc-TeX-vec-Bw} @font-face {font-family: MJXc-TeX-ams-R; src: local('MathJax_AMS'), local('MathJax_AMS-Regular')} @font-face {font-family: MJXc-TeX-ams-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_AMS-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_AMS-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_AMS-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-cal-B; src: local('MathJax_Caligraphic Bold'), local('MathJax_Caligraphic-Bold')} @font-face {font-family: MJXc-TeX-cal-Bx; src: local('MathJax_Caligraphic'); font-weight: bold} @font-face {font-family: MJXc-TeX-cal-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Caligraphic-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Caligraphic-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Caligraphic-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-frak-R; src: local('MathJax_Fraktur'), local('MathJax_Fraktur-Regular')} @font-face {font-family: MJXc-TeX-frak-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Fraktur-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Fraktur-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Fraktur-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-frak-B; src: local('MathJax_Fraktur Bold'), local('MathJax_Fraktur-Bold')} @font-face {font-family: MJXc-TeX-frak-Bx; src: local('MathJax_Fraktur'); font-weight: bold} @font-face {font-family: MJXc-TeX-frak-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Fraktur-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Fraktur-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Fraktur-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-math-BI; src: local('MathJax_Math BoldItalic'), local('MathJax_Math-BoldItalic')} @font-face {font-family: MJXc-TeX-math-BIx; src: local('MathJax_Math'); font-weight: bold; font-style: italic} @font-face {font-family: MJXc-TeX-math-BIw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Math-BoldItalic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Math-BoldItalic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Math-BoldItalic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-R; src: local('MathJax_SansSerif'), local('MathJax_SansSerif-Regular')} @font-face {font-family: MJXc-TeX-sans-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-B; src: local('MathJax_SansSerif Bold'), local('MathJax_SansSerif-Bold')} @font-face {font-family: MJXc-TeX-sans-Bx; src: local('MathJax_SansSerif'); font-weight: bold} @font-face {font-family: MJXc-TeX-sans-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-I; src: local('MathJax_SansSerif Italic'), local('MathJax_SansSerif-Italic')} @font-face {font-family: MJXc-TeX-sans-Ix; src: local('MathJax_SansSerif'); font-style: italic} @font-face {font-family: MJXc-TeX-sans-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-script-R; src: local('MathJax_Script'), local('MathJax_Script-Regular')} @font-face {font-family: MJXc-TeX-script-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Script-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Script-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Script-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-type-R; src: local('MathJax_Typewriter'), local('MathJax_Typewriter-Regular')} @font-face {font-family: MJXc-TeX-type-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Typewriter-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Typewriter-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Typewriter-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-cal-R; src: local('MathJax_Caligraphic'), local('MathJax_Caligraphic-Regular')} @font-face {font-family: MJXc-TeX-cal-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Caligraphic-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Caligraphic-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Caligraphic-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-B; src: local('MathJax_Main Bold'), local('MathJax_Main-Bold')} @font-face {font-family: MJXc-TeX-main-Bx; src: local('MathJax_Main'); font-weight: bold} @font-face {font-family: MJXc-TeX-main-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-I; src: local('MathJax_Main Italic'), local('MathJax_Main-Italic')} @font-face {font-family: MJXc-TeX-main-Ix; src: local('MathJax_Main'); font-style: italic} @font-face {font-family: MJXc-TeX-main-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-R; src: local('MathJax_Main'), local('MathJax_Main-Regular')} @font-face {font-family: MJXc-TeX-main-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-math-I; src: local('MathJax_Math Italic'), local('MathJax_Math-Italic')} @font-face {font-family: MJXc-TeX-math-Ix; src: local('MathJax_Math'); font-style: italic} @font-face {font-family: MJXc-TeX-math-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Math-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Math-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Math-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size1-R; src: local('MathJax_Size1'), local('MathJax_Size1-Regular')} @font-face {font-family: MJXc-TeX-size1-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size1-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size1-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size1-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size2-R; src: local('MathJax_Size2'), local('MathJax_Size2-Regular')} @font-face {font-family: MJXc-TeX-size2-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size2-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size2-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size2-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size3-R; src: local('MathJax_Size3'), local('MathJax_Size3-Regular')} @font-face {font-family: MJXc-TeX-size3-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size3-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size3-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size3-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size4-R; src: local('MathJax_Size4'), local('MathJax_Size4-Regular')} @font-face {font-family: MJXc-TeX-size4-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size4-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size4-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size4-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-vec-R; src: local('MathJax_Vector'), local('MathJax_Vector-Regular')} @font-face {font-family: MJXc-TeX-vec-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Vector-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Vector-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Vector-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-vec-B; src: local('MathJax_Vector Bold'), local('MathJax_Vector-Bold')} @font-face {font-family: MJXc-TeX-vec-Bx; src: local('MathJax_Vector'); font-weight: bold} @font-face {font-family: MJXc-TeX-vec-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Vector-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Vector-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Vector-Bold.otf') format('opentype')}

This is one of three sets of fixed point exercises. The first post in this sequence is here, giving context.

  1. (1-D Sperner's lemma) Consider a path built out of n edges as shown. Color each vertex blue or green such that the leftmost vertex is blue and the rightmost vertex is green. Show that an odd number of the edges will be bichromatic.

  1. (Intermediate value theorem) The Bolzano-Weierstrass theorem states that any bounded sequence in Rn has a convergent subsequence. The intermediate value theorem states that if you have a continuous function f:[0,1]→R such that f(0)≤0 and f(1)≥0, then there exists an x∈[0,1] such that f(x)=0. Prove the intermediate value theorem. It may be helpful later on if your proof uses 1-D Sperner's lemma and the Bolzano-Weierstrass theorem.

  2. (1-D Brouwer fixed point theorem) Show that any continuous function f:[0,1]→[0,1] has a fixed point (i.e. a point x∈[0,1] with f(x)=x). Why is this not true for the open interval (0,1)?

  3. (2-D Sperner's lemma) Consider a triangle built out of n2 smaller triangles as shown. Color each vertex red, blue, or green, such that none of the vertices on the large bottom edge are red, none of the vertices on the large left edge are green, and none of the vertices on the large right edge are blue. Show that an odd number of the small triangles will be trichromatic.

  1. Color the all the points in the disk as shown. Let f be a continuous function from a closed triangle to the disk, such that the bottom edge is sent to non-red points, the left edge is sent to non-green points, and the right edge is sent to non-blue points. Show that f sends some point in the triangle to the center.

  1. Show that any continuous function f from closed triangle to itself has a fixed point.

  2. (2-D Brouwer fixed point theorem) Show that any continuous function from a compact convex subset of R2 to itself has a fixed point. (You may use the fact that given any closed convex subset S of Rn, the function from Rn to S which projects each point to the nearest point in S is well defined and continuous.)

  3. Reflect on how non-constructive all of the above fixed-point findings are. Find a parameterized class of functions where for each t∈[0,1], ft:[0,1]→[0,1], and the function t↦ft is continuous, but there is no continuous way to pick out a single fixed point from each function (i.e. no continuous function g such that g(t) is a fixed point of ft for all t).

  4. (Sperner's lemma) Generalize exercises 1 and 4 to an arbitrary dimension simplex.

  5. (Brouwer fixed point theorem) Show that any continuous function from a compact convex subset of Rn to itself has a fixed point.

  6. Given two nonempty compact subsets A,B⊆Rn, the Hausdorff distance between them is the supremum max{supa∈Ad(a,B),supb∈Bd(b,A)} over all points in either subset of the distance from that point to the other subset. We call a set valued function f:S→2T a continuous Hausdorff limit if there is a sequence {fn} of continuous functions from S to T whose graphs, {(x,y)∣y=fn(x)}⊆S×T, converge to the graph of f, {(x,y)∣f(x)∋y}⊆S×T, in Hausdorff distance. Show that every continuous Hausdorff limit f:T→2T from a compact convex subset of Rn to itself has a fixed point (a point x such that x∈f(x)).

  7. Let S and T be nonempty compact convex subsets of Rn. We say that a set valued function, f:S→2T is a Kakutani function if the graph of f, {(x,y)∣f(x)∋y}⊆S×T, is closed, and f(x) is convex and nonempty for all x∈S. For example, we could take S and T to be the interval [0,1], and we could have f:S→2T send each x<12 to {0}, map x=12 to the whole interval [0,1], and map \frac{1}{2}">x>12 to {1}. Show that every Kakutani function is a continuous Hausdorff limit. (Hint: Start with the case where S is a unit cube. Construct fn by breaking S into small cubes of side length 2−n. Constuct a smaller cube of side length 2−n−1 within each 2−n cube. Send each small 2−n−1 to the convex hull of the images of all points in the 2−n cube with a continuous function, and glue these together with straight lines. Make sure you don't accidentally get extra limit points.)

  8. (Kakutani fixed point theorem) Show that every Kakutani function from a compact convex subset of S⊆Rn to itself has a fixed point.

Please use the spoilers feature - the symbol '>' followed by '!' followed by space -in your comments to hide all solutions, partial solutions, and other discussions of the math. The comments will be moderated strictly to hide spoilers!

I recommend putting all the object level points in spoilers and leaving metadata outside of the spoilers, like so: "I think I've solved problem #5, here's my solution <spoilers>" or "I'd like help with problem #3, here's what I understand <spoilers>" so that people can choose what to read.



Discuss

Is Clickbait Destroying Our General Intelligence?

17 ноября, 2018 - 02:06
Published on Fri Nov 16 2018 23:06:29 GMT+0000 (UTC)

(Cross-posted from Facebook.)

Now and then people have asked me if I think that other people should also avoid high school or college if they want to develop new ideas. This always felt to me like a wrong way to look at the question, but I didn't know a right one.

Recently I thought of a scary new viewpoint on that subject.

This started with a conversation with Arthur where he mentioned an idea by Yoshua Bengio about the software for general intelligence having been developed memetically. I remarked that I didn't think duplicating this culturally transmitted software would be a significant part of the problem for AGI development. (Roughly: low-fidelity software tends to be algorithmically shallow. Further discussion moved to comment below.)

But this conversation did get me thinking about the topic of culturally transmitted software that contributes to human general intelligence. That software can be an important gear even if it's an algorithmically shallow part of the overall machinery. Removing a few simple gears that are 2% of a machine's mass can reduce the machine's performance by way more than 2%. Feral children would be the case in point.

A scary question is whether it's possible to do subtler damage to the culturally transmitted software of general intelligence.

I've had the sense before that the Internet is turning our society stupider and meaner. My primary hypothesis is "The Internet is selecting harder on a larger population of ideas, and sanity falls off the selective frontier once you select hard enough."

To review, there's a general idea that strong (social) selection on a characteristic imperfectly correlated with some other metric of goodness can be bad for that metric, where weak (social) selection on that characteristic was good. If you press scientists a little for publishable work, they might do science that's of greater interest to others. If you select very harshly on publication records, the academics spend all their time worrying about publishing and real science falls by the wayside.

On my feed yesterday was an essay complaining about how the intense competition to get into Harvard is producing a monoculture of students who've lined up every single standard accomplishment and how these students don't know anything else they want to do with their lives. Gentle, soft competition on a few accomplishments might select genuinely stronger students; hypercompetition for the appearance of strength produces weakness, or just emptiness.

A hypothesis I find plausible is that the Internet, and maybe television before it, selected much more harshly from a much wider field of memes; and also allowed tailoring content more narrowly to narrower audiences. The Internet is making it possible for ideas that are optimized to appeal hedonically-virally within a filter bubble to outcompete ideas that have been even slightly optimized for anything else. We're looking at a collapse of reference to expertise because deferring to expertise costs a couple of hedons compared to being told that all your intuitions are perfectly right, and at the harsh selective frontier there's no room for that. We're looking at a collapse of interaction between bubbles because there used to be just a few newspapers serving all the bubbles; and now that the bubbles have separated there's little incentive to show people how to be fair in their judgment of ideas for other bubbles, it's not the most appealing Tumblr content. Print magazines in the 1950s were hardly perfect, but they could get away with sometimes presenting complicated issues as complicated, because there weren't a hundred blogs saying otherwise and stealing their clicks. Or at least, that's the hypothesis.

It seems plausible to me that basic software for intelligent functioning is being damaged by this hypercompetition. Especially in a social context, but maybe even outside it; that kind of thing tends to slop over. When someone politely presents themselves with a careful argument, does your cultural software tell you that you're supposed to listen and make a careful response, or make fun of the other person and then laugh about how they're upset? What about when your own brain tries to generate a careful argument? Does your cultural milieu give you any examples of people showing how to really care deeply about something (i.e. debate consequences of paths and hew hard to the best one), or is everything you see just people competing to be loud in their identification? The Occupy movement not having any demands or agenda could represent mild damage to a gear of human general intelligence that was culturally transmitted and that enabled processing of a certain kind of goal-directed behavior. And I'm not sure to what extent that is merely a metaphor, versus it being simple fact if we could look at the true software laid out. If you look at how some bubbles are talking and thinking now, "intellectually feral children" doesn't seem like entirely inappropriate language.

Shortly after that conversation with Arthur, it occurred to me that I was pretty much raised and socialized by my parents' collection of science fiction.

My parents' collection of old science fiction.

Isaac Asimov. H. Beam Piper. A. E. van Vogt. Early Heinlein, because my parents didn't want me reading the later books.

And when I did try reading science fiction from later days, a lot of it struck me as... icky. Neuromancer, bleah, what is wrong with this book, it feels damaged, why do people like this, it feels like there's way too much flash and it ate the substance, it's showing off way too hard.

And now that I think about it, I feel like a lot of my writing on rationality would be a lot more popular if I could go back in time to the 1960s and present it there. "Twelve Virtues of Rationality" is what people could've been reading instead of Heinlein's Stranger in a Strange Land, to take a different path from the branching point that found Stranger in a Strange Land appealing.

I didn't stick to merely the culture I was raised in, because that wasn't what that culture said to do. The characters I read didn't keep to the way they were raised. They were constantly being challenged with new ideas and often modified or partially rejected those ideas in the course of absorbing them. If you were immersed in an alien civilization that had some good ideas, you were supposed to consider it open-mindedly and then steal only the good parts. Which... kind of sounds axiomatic to me? You could make a case that this is an obvious guideline for how to do generic optimization. It's just what you do to process an input. And yet "when you encounter a different way of thinking, judge it open-mindedly and then steal only the good parts" is directly contradicted by some modern software that seems to be memetically hypercompetitive. It probably sounds a bit alien or weird to some people reading this, at least as something that you'd say out loud. Software contributing to generic optimization has been damaged.

Later the Internet came along and exposed me to some modern developments, some of which are indeed improvements. But only after I had a cognitive and ethical foundation that could judge which changes were progress versus damage. More importantly, a cognitive foundation that had the idea of even trying to do that. Tversky and Kahneman didn't exist in the 1950s, but when I was exposed to this new cognitive biases literature, I reacted like an Isaac Asimov character trying to integrate it into their existing ideas about psychohistory, instead of a William Gibson character wondering how it would look on a black and chrome T-Shirt. If that reference still means anything to anyone.

I suspect some culturally transmitted parts of the general intelligence software got damaged by radio, television, and the Internet, with a key causal step being an increased hypercompetition of ideas compared to earlier years. I suspect this independently of any other hypotheses about my origin story. It feels to me like the historical case for this thesis ought to be visible by mere observation to anyone who watched the quality of online discussion degrade from 2002 to 2017.

But if you consider me to be more than usually intellectually productive for an average Ashkenazic genius in the modern generation, then in this connection it's an interesting and scary further observation that I was initially socialized by books written before the Great Stagnation. Or by books written by authors from only a single generation later, who read a lot of old books themselves and didn't watch much television.

That hypothesis doesn't feel wrong to me the way that "oh you just need to not go to college" feels wrong to me.



Discuss

Dimensional regret without resets

16 ноября, 2018 - 22:22
Published on Fri Nov 16 2018 19:22:32 GMT+0000 (UTC)

.mjx-chtml {display: inline-block; line-height: 0; text-indent: 0; text-align: left; text-transform: none; font-style: normal; font-weight: normal; font-size: 100%; font-size-adjust: none; letter-spacing: normal; word-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; margin: 0; padding: 1px 0} .MJXc-display {display: block; text-align: center; margin: 1em 0; padding: 0} .mjx-chtml[tabindex]:focus, body :focus .mjx-chtml[tabindex] {display: inline-table} .mjx-full-width {text-align: center; display: table-cell!important; width: 10000em} .mjx-math {display: inline-block; border-collapse: separate; border-spacing: 0} .mjx-math * {display: inline-block; -webkit-box-sizing: content-box!important; -moz-box-sizing: content-box!important; box-sizing: content-box!important; text-align: left} .mjx-numerator {display: block; text-align: center} .mjx-denominator {display: block; text-align: center} .MJXc-stacked {height: 0; position: relative} .MJXc-stacked > * {position: absolute} .MJXc-bevelled > * {display: inline-block} .mjx-stack {display: inline-block} .mjx-op {display: block} .mjx-under {display: table-cell} .mjx-over {display: block} .mjx-over > * {padding-left: 0px!important; padding-right: 0px!important} .mjx-under > * {padding-left: 0px!important; padding-right: 0px!important} .mjx-stack > .mjx-sup {display: block} .mjx-stack > .mjx-sub {display: block} .mjx-prestack > .mjx-presup {display: block} .mjx-prestack > .mjx-presub {display: block} .mjx-delim-h > .mjx-char {display: inline-block} .mjx-surd {vertical-align: top} .mjx-mphantom * {visibility: hidden} .mjx-merror {background-color: #FFFF88; color: #CC0000; border: 1px solid #CC0000; padding: 2px 3px; font-style: normal; font-size: 90%} .mjx-annotation-xml {line-height: normal} .mjx-menclose > svg {fill: none; stroke: currentColor} .mjx-mtr {display: table-row} .mjx-mlabeledtr {display: table-row} .mjx-mtd {display: table-cell; text-align: center} .mjx-label {display: table-row} .mjx-box {display: inline-block} .mjx-block {display: block} .mjx-span {display: inline} .mjx-char {display: block; white-space: pre} .mjx-itable {display: inline-table; width: auto} .mjx-row {display: table-row} .mjx-cell {display: table-cell} .mjx-table {display: table; width: 100%} .mjx-line {display: block; height: 0} .mjx-strut {width: 0; padding-top: 1em} .mjx-vsize {width: 0} .MJXc-space1 {margin-left: .167em} .MJXc-space2 {margin-left: .222em} .MJXc-space3 {margin-left: .278em} .mjx-test.mjx-test-display {display: table!important} .mjx-test.mjx-test-inline {display: inline!important; margin-right: -1px} .mjx-test.mjx-test-default {display: block!important; clear: both} .mjx-ex-box {display: inline-block!important; position: absolute; overflow: hidden; min-height: 0; max-height: none; padding: 0; border: 0; margin: 0; width: 1px; height: 60ex} .mjx-test-inline .mjx-left-box {display: inline-block; width: 0; float: left} .mjx-test-inline .mjx-right-box {display: inline-block; width: 0; float: right} .mjx-test-display .mjx-right-box {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} .MJXc-TeX-unknown-R {font-family: monospace; font-style: normal; font-weight: normal} .MJXc-TeX-unknown-I {font-family: monospace; font-style: italic; font-weight: normal} .MJXc-TeX-unknown-B {font-family: monospace; font-style: normal; font-weight: bold} .MJXc-TeX-unknown-BI {font-family: monospace; font-style: italic; font-weight: bold} .MJXc-TeX-ams-R {font-family: MJXc-TeX-ams-R,MJXc-TeX-ams-Rw} .MJXc-TeX-cal-B {font-family: MJXc-TeX-cal-B,MJXc-TeX-cal-Bx,MJXc-TeX-cal-Bw} .MJXc-TeX-frak-R {font-family: MJXc-TeX-frak-R,MJXc-TeX-frak-Rw} .MJXc-TeX-frak-B {font-family: MJXc-TeX-frak-B,MJXc-TeX-frak-Bx,MJXc-TeX-frak-Bw} .MJXc-TeX-math-BI {font-family: MJXc-TeX-math-BI,MJXc-TeX-math-BIx,MJXc-TeX-math-BIw} .MJXc-TeX-sans-R {font-family: MJXc-TeX-sans-R,MJXc-TeX-sans-Rw} .MJXc-TeX-sans-B {font-family: MJXc-TeX-sans-B,MJXc-TeX-sans-Bx,MJXc-TeX-sans-Bw} .MJXc-TeX-sans-I {font-family: MJXc-TeX-sans-I,MJXc-TeX-sans-Ix,MJXc-TeX-sans-Iw} .MJXc-TeX-script-R {font-family: MJXc-TeX-script-R,MJXc-TeX-script-Rw} .MJXc-TeX-type-R {font-family: MJXc-TeX-type-R,MJXc-TeX-type-Rw} .MJXc-TeX-cal-R {font-family: MJXc-TeX-cal-R,MJXc-TeX-cal-Rw} .MJXc-TeX-main-B {font-family: MJXc-TeX-main-B,MJXc-TeX-main-Bx,MJXc-TeX-main-Bw} .MJXc-TeX-main-I {font-family: MJXc-TeX-main-I,MJXc-TeX-main-Ix,MJXc-TeX-main-Iw} .MJXc-TeX-main-R {font-family: MJXc-TeX-main-R,MJXc-TeX-main-Rw} .MJXc-TeX-math-I {font-family: MJXc-TeX-math-I,MJXc-TeX-math-Ix,MJXc-TeX-math-Iw} .MJXc-TeX-size1-R {font-family: MJXc-TeX-size1-R,MJXc-TeX-size1-Rw} .MJXc-TeX-size2-R {font-family: MJXc-TeX-size2-R,MJXc-TeX-size2-Rw} .MJXc-TeX-size3-R {font-family: MJXc-TeX-size3-R,MJXc-TeX-size3-Rw} .MJXc-TeX-size4-R {font-family: MJXc-TeX-size4-R,MJXc-TeX-size4-Rw} .MJXc-TeX-vec-R {font-family: MJXc-TeX-vec-R,MJXc-TeX-vec-Rw} .MJXc-TeX-vec-B {font-family: MJXc-TeX-vec-B,MJXc-TeX-vec-Bx,MJXc-TeX-vec-Bw} @font-face {font-family: MJXc-TeX-ams-R; src: local('MathJax_AMS'), local('MathJax_AMS-Regular')} @font-face {font-family: MJXc-TeX-ams-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_AMS-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_AMS-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_AMS-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-cal-B; src: local('MathJax_Caligraphic Bold'), local('MathJax_Caligraphic-Bold')} @font-face {font-family: MJXc-TeX-cal-Bx; src: local('MathJax_Caligraphic'); font-weight: bold} @font-face {font-family: MJXc-TeX-cal-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Caligraphic-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Caligraphic-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Caligraphic-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-frak-R; src: local('MathJax_Fraktur'), local('MathJax_Fraktur-Regular')} @font-face {font-family: MJXc-TeX-frak-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Fraktur-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Fraktur-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Fraktur-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-frak-B; src: local('MathJax_Fraktur Bold'), local('MathJax_Fraktur-Bold')} @font-face {font-family: MJXc-TeX-frak-Bx; src: local('MathJax_Fraktur'); font-weight: bold} @font-face {font-family: MJXc-TeX-frak-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Fraktur-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Fraktur-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Fraktur-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-math-BI; src: local('MathJax_Math BoldItalic'), local('MathJax_Math-BoldItalic')} @font-face {font-family: MJXc-TeX-math-BIx; src: local('MathJax_Math'); font-weight: bold; font-style: italic} @font-face {font-family: MJXc-TeX-math-BIw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Math-BoldItalic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Math-BoldItalic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Math-BoldItalic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-R; src: local('MathJax_SansSerif'), local('MathJax_SansSerif-Regular')} @font-face {font-family: MJXc-TeX-sans-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-B; src: local('MathJax_SansSerif Bold'), local('MathJax_SansSerif-Bold')} @font-face {font-family: MJXc-TeX-sans-Bx; src: local('MathJax_SansSerif'); font-weight: bold} @font-face {font-family: MJXc-TeX-sans-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-I; src: local('MathJax_SansSerif Italic'), local('MathJax_SansSerif-Italic')} @font-face {font-family: MJXc-TeX-sans-Ix; src: local('MathJax_SansSerif'); font-style: italic} @font-face {font-family: MJXc-TeX-sans-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-script-R; src: local('MathJax_Script'), local('MathJax_Script-Regular')} @font-face {font-family: MJXc-TeX-script-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Script-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Script-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Script-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-type-R; src: local('MathJax_Typewriter'), local('MathJax_Typewriter-Regular')} @font-face {font-family: MJXc-TeX-type-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Typewriter-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Typewriter-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Typewriter-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-cal-R; src: local('MathJax_Caligraphic'), local('MathJax_Caligraphic-Regular')} @font-face {font-family: MJXc-TeX-cal-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Caligraphic-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Caligraphic-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Caligraphic-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-B; src: local('MathJax_Main Bold'), local('MathJax_Main-Bold')} @font-face {font-family: MJXc-TeX-main-Bx; src: local('MathJax_Main'); font-weight: bold} @font-face {font-family: MJXc-TeX-main-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-I; src: local('MathJax_Main Italic'), local('MathJax_Main-Italic')} @font-face {font-family: MJXc-TeX-main-Ix; src: local('MathJax_Main'); font-style: italic} @font-face {font-family: MJXc-TeX-main-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-R; src: local('MathJax_Main'), local('MathJax_Main-Regular')} @font-face {font-family: MJXc-TeX-main-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-math-I; src: local('MathJax_Math Italic'), local('MathJax_Math-Italic')} @font-face {font-family: MJXc-TeX-math-Ix; src: local('MathJax_Math'); font-style: italic} @font-face {font-family: MJXc-TeX-math-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Math-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Math-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Math-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size1-R; src: local('MathJax_Size1'), local('MathJax_Size1-Regular')} @font-face {font-family: MJXc-TeX-size1-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size1-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size1-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size1-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size2-R; src: local('MathJax_Size2'), local('MathJax_Size2-Regular')} @font-face {font-family: MJXc-TeX-size2-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size2-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size2-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size2-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size3-R; src: local('MathJax_Size3'), local('MathJax_Size3-Regular')} @font-face {font-family: MJXc-TeX-size3-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size3-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size3-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size3-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size4-R; src: local('MathJax_Size4'), local('MathJax_Size4-Regular')} @font-face {font-family: MJXc-TeX-size4-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size4-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size4-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size4-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-vec-R; src: local('MathJax_Vector'), local('MathJax_Vector-Regular')} @font-face {font-family: MJXc-TeX-vec-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Vector-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Vector-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Vector-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-vec-B; src: local('MathJax_Vector Bold'), local('MathJax_Vector-Bold')} @font-face {font-family: MJXc-TeX-vec-Bx; src: local('MathJax_Vector'); font-weight: bold} @font-face {font-family: MJXc-TeX-vec-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Vector-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Vector-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Vector-Bold.otf') format('opentype')}

TLDR: I derive a variant of the RL regret bound by Osband and Van Roy (2014), that applies to learning without resets of environments without traps. The advantage of this regret bound over those known in the literature, is that it scales with certain learning-theoretic dimensions rather than number of states and actions. My goal is building on this result to derive this type of regret bound for DRL, and, later on, other settings interesting from an AI alignment perspective.

Previously I derived a regret bound for deterministic environments that scales with prior entropy and "prediction dimension". That bound behaves as O(√1−γ) in the episodic setting but only as O(3√1−γ) in the setting without resets. Moreover, my attempts to generalize the result to stochastic environments led to bounds that are even weaker (have a lower exponent). Therefore, I decided to put that line of attack on hold, and use Osband and Van Roy's technique instead, leading to an O(√1−γ) bound in the stochastic setting without resets. This bound doesn't scale down with the entropy of the prior, but this does not seem as important as dependence on γ.

Results

Russo and Van Roy (2013) introduced the concept of "eluder dimension" for the benefit of the multi-armed bandit setting, and Osband and Van Roy extended it to a form suitable for studying reinforcement learning. We will consider the following, slightly modified version of their definition.

Given a real vector space Y, we will use PSD(Y) to denote the set of positive semidefinite bilinear forms on Y and PD(Y) to denote the set of positive definite bilinear forms on Y. Given a bilinear form B:Y×Y→R, we will slightly abuse notation by also regarding it as a linear functional B:Y⊗Y→R. Thereby, we have B(v⊗w)=B(v,w) and Bv⊗2=B(v,v). Also, if Y is finite-dimensional and B is non-degenerate, we will denote B−1:Y∗×Y∗→R the unique bilinear form which satisfies

∀v∈Y,α∈Y∗:(∀β∈Y∗:B−1(α,β)=βv)⟺(∀w∈Y:B(v,w)=αw)

Definition 1

Consider a set X, a real vector space Y, some F⊆{X→Y} and a family {Bx∈PSD(Y)}x∈X. Consider also n∈N, a sequence {xk∈X}k∈[n] and x∗∈X. x∗ is said to be (F,B)-dependant on {xk} when, for any f,~f∈F

n−1∑k=0Bxk(f(xk)−~f(xk))⊗2≤1⟹Bx∗(f(x∗)−~f(x∗))⊗2≤1

Otherwise, x∗ is said to be (F,B)-independent of {xk}.

Definition 2

Consider a set X, a real vector space Y and some F⊆{X→Y}. The Russo-Van Roy-Osband dimension (RVO dimension) dimRVOF is the supremum of the set of n∈N for which there is {xk∈X}k∈[n] and B s.t. for all m∈[n], xm is (F,B)-independent of {xk}k∈[m].

We have the following basic bounds on RVO dimension.

Proposition 1

Consider a set X, a real vector space Y and some F⊆{X→Y}. Then

dimRVOF≤|X|

Proposition 2

Consider a set X, a real vector space Y and some F⊆{X→Y}. Then

dimRVOF≤|F|(|F|−1)2

Another concept we need to formulate the regret bound is the Minkowski–Bouligand dimension.

Definition 3

Consider a set X, a real vector space Y, some F⊆{X→Y} and a family {Bx∈PSD(Y)}x∈X. A set A⊆F is said to be a B-covering of F when

∀f∈F∃~f∈A:supx∈XBx(f(x)−~f(x))⊗2<1

Definition 4

Consider a set X, a real vector space Y, some F⊆{X→Y} and a family {Bx∈PSD(Y)}x∈X. The covering number N(F,B) is the infimum of the set of n∈N for which there is a B-covering of F of size n.

Definition 5

Consider a finite set X, a finite-dimensional real vector product space Y and some F⊆{X→Y}. Fix any {Bx∈PD(Y)}x∈X. The Minkowski–Bouligand dimension (MB dimension) of F is defined by

dimMBF:=limsupϵ→0lnN(F,ϵ−2B)ln1ϵ

It is easy to see the above is indeed well-defined, i.e. doesn't depend on the choice of B. This is because given any B,~B, there are constants c1,c2∈R+ s.t. for all F and ϵ

c1N(F,ϵ−2B)≤N(F,ϵ−2~B)≤c2N(F,ϵ−2B)

Similarly, for any {Bx∈PSD(Y)}x∈X, we have

dimMBF≥limsupϵ→0lnN(F,ϵ−2B)ln1ϵ

For finite F and ϵ≪1, it's obvious that N(F,ϵ−2B)≤|F|, and in particular dimMBF=0. It is also possible to show that, for any bounded F, dimMBF≤|X|dimY.

Note that, in general, MB dimension is fractional.

We will need yet another (but rather simple) notion of "dimension".

Definition 6

Consider a set X, a vector space Y and some F⊆{X→Y}. The local dimension of F is defined by

dimlocF:=maxx∈Xdimspan{f(x)|f∈F}

Obviously dimlocF≤|F| and dimlocF≤dimY.

Consider finite non-empty sets S (states) and A (actions). Observe that ΔS can be regarded as a subset of the vector space RS. This allows us to speak of the RVO, MB and local dimensions of a hypothesis class of transition kernels H⊆{S×Ak→S} (in this case X=S×A and Y=RS).

We can now formulate the regret bound.

Theorem 1

There is some C∈R+ s.t. the following holds.

Consider any finite non-empty sets S and A, R:S→[0,1], closed set H⊆{S×Ak→S} and Borel probability measure ζ on H (prior). We define the maximal bias span τζR by

τζR:=limsupγ→1maxT∈Hmaxs∈SVTR(s,γ)−mins∈SVTR(s,γ)1−γ

Denote Dloc:=dimlocH, DMB:=dimMBH and DRVO:=dimRVOH. Then, there is a family of policies {π†γ:S∗×Sk→A}γ∈(0,1) s.t.

limsupγ→1ET∼ζ[EU∗TR(γ)−EUπ†γTR(γ)]τζRDloc√(DMB+1)DRVO(1−γ)ln11−γ≤C

Here (like in previous essays), VTR(s,γ) is the value function for transition kernel T, reward function R, state s and geometric time discount parameter γ; EUπTR(γ) is the expected utility for policy π; EU∗TR(γ) is the maximal expected utility over policies. The expression in the numerator is, thereby, the Bayesian regret.

The implicit condition τζR<∞ implies that for any T∈H and s,s′∈S, V0TR(s)=V0TR(s′). This is a no-traps condition stronger than the condition A0TR(s)=A we used before: not only that long-term value cannot be lost in expectation, it cannot be lost at all. For any finite H satisfying this no-traps condition, we have

τζR=maxT∈H(maxs∈SV1TR(s)−mins∈SV1TR(s))<∞

A few directions for improving on this result:

  • It is not hard to see from the proof that it is also possible to write down a concrete bound for fixed γ (rather than considering the γ→1 limit), but its form is somewhat convoluted.

  • It is probably possible to get an anytime policy with this form of regret, using PSRL with dynamic episode duration.

  • It is interesting to try to make do with the weaker no-traps condition A0TR(s)=A, especially since a stronger no-traps conditions would translate to a stronger condition on the advisor in DRL.

  • It is interesting to study RVO dimension in more detail. For example, I'm not even sure whether Proposition 2 is the best possible bound in terms of |F| or it's e.g. possible to get a linear bound.

  • It seems tempting to generalize local dimension by allowing the values of f(x) to lie on some nonlinear manifold of given dimension for any given x. This approach, if workable, might require a substantially more difficult proof.

  • The "cellular decision processes" discussed previously in "Proposition 3" have exponentially high local dimension, meaning that this regret bound is ineffective for them. We can consider a variant in which, on every time step, only one cell or a very small number of cells (possibly chosen randomly) change. This would have low local dimension. One way to interpret it is, as a continuous time process in which each cell has a certain rate of changing its state.

Proofs

Proof of Proposition 1

Consider some {xk∈X}k∈[m] and x∗∈X which is (F,B)-independent of {xk}. Then, there are some f,~f∈F s.t. the following two inequalities hold

m−1∑k=0Bxk(f(xk)−~f(xk))⊗2≤1

1">Bx∗(f(x∗)−~f(x∗))⊗2>1

The first inequality implies that, for any k∈[m], Bxk(f(xk)−~f(xk))⊗2≤1. Comparing with the second inequality, we conclude that x∗≠xk.

Now suppose that {xk∈X}k∈[n] is s.t. for all m∈[n], xm is (F,B)-independent of {xk}k∈[m]. By the previous paragraph, it follows that xm≠xk for any m,k∈[n] s.t. k<m. Hence, n≤|X|, Q.E.D.

Proof of Proposition 2

Suppose that {xk∈X}k∈[n] is s.t. for all m∈[n], xm is (F,B)-independent of {xk}k∈[m]. Then, for each m∈[n], we can choose fm,~fm∈F s.t. the following two inequalities hold

m−1∑k=0Bxk(fm(xk)−~fm(xk))⊗2≤1

1">Bxm(fm(xm)−~fm(xm))⊗2>1

In particular, the second inequality implies that fm≠~fm.

Now, consider some k∈[m]. By the first inequality

Bxk(fm(xk)−~fm(xk))⊗2≤1

On the other hand, the second inequality with k instead of m gives

1">Bxk(fk(xk)−~fk(xk))⊗2>1

It follows that {fm,~fm}≠{fk,~fk}. Therefore, n cannot exceed the number of unordered pairs of distinct elements in F, Q.E.D.

Given a measurable space X, some μ,ν∈ΔX and a measurable function f:X→R, we will use the notation

Ex∼μ−ν[f(x)]:=Ex∼μ[f(x)]−Ex∼ν[f(x)]

Given X,Y measurable spaces, some K,L:Xk→Y and a measurable function f:Y→R, we will use the notation

Ey∼K[f(y)|x]:=Ey∼K(x)[f(y)]

Ey∼K−L[f(y)|x]:=Ey∼K(x)−L(x)[f(y)]

Given finite sets S,A, some T:S×Ak→S and π:S→A, we will use the notation Tπ:Sk→S defined by

Tπ(s):=T(s,π(s))

Proposition A.1

In the setting of Theorem 1, fix T∈N+ and γ∈(0,1). Let Π:H×S→A be a Borel measurable mapping s.t. Π(T) is an optimal policy, i.e.

EUΠ(T)TR(γ)=EU∗TR(γ)

Let πPSζΠT:S∗×Sk→A be the policy implemented by a PSRL algorithm with prior ζ and episode length T, s.t. whenever hypothesis T is sampled, policy Π(T) is followed. Denote the Bayesian regret by

R(γ):=ET∼ζ[EU∗TR(γ)−EUπPSζΠTTR(γ)]

Let (Ω,P) be a probability space governing both the uncertainty about the true hypothesis, the stochastic behavior of the environment and the random sampling inside the algorithm. [See the proof of "Lemma 1" in this previous essay or the proof of "Theorem 1" in another previous essay.] Furthermore, let H∗:Ω→H be a random variable representing the true hypothesis, {Hn:Ω→H}n∈N be the random variables s.t. Hn represents the hypothesis sampled at time n (i.e. during episode number ⌊n/T⌋), {Θn:Ω→S}n∈N be random variables s.t. Θn represents the state at time n and {An:Ω→A}n∈N be random variables s.t. An represents the action taken at time n. Denote El:=H∗Π(HlT) and ¯El:=HlTΠ(H∗). Then

R(γ)=∞∑n=0γn+1E[EHn−H∗[VHnR(γ)|Θn,An]]+∞∑l=0γ(l+1)TE[E¯ETl−ETl[VH∗R(γ)|ΘlT]]

Here, ETl means raising El to the T-th power w.r.t. Markov kernel composition, and the same for ¯ETl.

We will use the notation VTπR(s,γ) to stand for the expected utility achieved by policy π when starting from state s with transition kernel T, reward function R and time discount parameter γ.

Proof of Proposition A.1

For any n∈N, define Πn:H×H×S∗×Sk→A as follows.

Πn(T1,T2,h,s):={Π(T1,s) if |h|<nΠ(T2,s) if |h|≥n

That is, Πn(T1,T2) is a policy that follows Π(T1) for time n and Π(T2) afterwards.

In the following, we use the shorthand notation

V∗(s):=VH∗R(s,γ)

Vl(s):=VHlTR(s,γ)

Vlk(s):=VH∗ΠT−k(HlT,H∗)R(s,γ)

It is easy to see that

R(γ)=∞∑l=0γlTE[V∗(ΘlT)−Vl0(ΘlT)]

The above is essentially what appeared as "Proposition B.1" before, for the special case of PSRL, and where we regard every episode as a single time step in a new MDP in which every action is a policy for the duration of an episode in the original MDP.

By definition, HlT and H∗ have the same distribution even when conditioned by the history up to lT. Therefore

E[V∗(ΘlT)]=E[Vl(ΘlT)]

It follows that

R(γ)=∞∑l=0γlTE[Vl(ΘlT)−Vl0(ΘlT)]

We now prove by induction on k∈[T+1] that

E[Vl(ΘlT)−Vl0(ΘlT)]=lT+k−1∑n=lTγn−lT+1E[EHn−H∗[Vl|Θn,An]]+γkE[Vl(ΘlT+k)−Vlk(ΘlT+k)]

For k=0 this is a tautology. For any k∈[T], the Bellman equation says that

Vl(s)=(1−γ)R(s)+γEHlTΠ(HlT)[Vl|s]

Vlk(s)=(1−γ)R(s)+γEH∗Π(HlT)[Vl,k+1|s]

It follows that

E[Vl(ΘlT+k)−Vlk(ΘlT+k)]=γE[EHlTΠ(HlT)[Vl|ΘlT+k]−EH∗Π(HlT)[Vl,k+1|ΘlT+k]]

Since Π(HlT) is exactly the policy followed by PSRL at time lT+k, we get

E[Vl(ΘlT+k)−Vlk(ΘlT+k)]=γE[EHlT[Vl|ΘlT+k,AlT+k]−EH∗[Vl,k+1|ΘlT+k,AlT+k]]

We now subtract and add EH∗[Vl|ΘlT+k,AlT+k], and use the fact that H∗(ΘlT+k,AlT+k) is the conditional distribution of ΘlT+k+1.

E[Vl(ΘlT+k)−Vlk(ΘlT+k)]=γE[EHlT−H∗[Vl|ΘlT+k,AlT+k]+Vl(ΘlT+k+1)−Vl,k+1(ΘlT+k+1)]

Applying this identity to the second second term on the right hand side of the induction hypothesis, we prove the induction step. For k=T, we get, denoting n0:=lT and n1:=(l+1)T

E[Vl(Θn0)−Vl0(Θn0)]=n1−1∑n=n0γn−n0+1E[EHn−H∗[Vl|Θn,An]]+γTE[Vl(Θn1)−V∗(Θn1)]

Clearly

E[Vl(Θn1)]=E[EETl[Vl∣∣Θn0]]

E[V∗(Θn1)]=E[EETl[V∗∣∣Θn0]]

Using the definition of PSRL, we can exchange and true and sampled hypothesis and get

E[Vl(Θn1)]=E[E¯ETl[V∗∣∣Θn0]]

It follows that

E[Vl(Θn0)−Vl0(Θn0)]=n1−1∑n=n0γn−n0+1E[EHn−H∗[Vl|Θn,An]]+γTE[E¯ETl−ETl[V∗∣∣Θn0]]

Applying this to each term in the earlier expression for R(γ), we get the desired result. Q.E.D.

Proposition A.2

Consider a real finite-dimensional normed vector space Y and a linear subspace Z⊆Y. Then, there exists B∈PSD(Y) s.t.

  1. For any v∈Y, Bv⊗2≤∥v∥2

  2. For any v∈Z, (dimZ)2Bv⊗2≥∥v∥2

Proof of Proposition A.2

We assume 0">dimZ>0 since otherwise the claim is trivial (take B=0).

By Theorem B.1 (see Appendix), there is ~B∈PSD(Z) s.t. for any v∈Z

~Bv⊗2≤∥v∥2≤dimZ⋅~Bv⊗2

By Corollary B.1 (see Appendix), there is a projection operator P:Y→Y s.t. imY=Z and ∥P∥≤√dimZ. We define B∈PSD(Y) by

B(v,w):=~B(Pv,Pw)dimZ

For any v∈Y, we have

Bv⊗2=~B(Pv,Pv)dimZ≤∥Pv∥2dimZ≤∥P∥2∥v∥2dimZ≤∥v∥2

For any v∈Z, we have Pv=v and therefore

∥v∥2≤dimZ⋅~Bv⊗2=(dimZ)2~B(Pv,Pv)dimZ=(dimZ)2Bv⊗2

Q.E.D.

Proposition A.3

Consider a finite-dimensional real vector space Y, some B∈PD(Y) and a Borel probability measure μ∈ΔY s.t. Pry∼μ[By⊗2≤1]=1. Let y0:=Ey∼μ[y] and σ:=2√2. Then, μ is σ-sub-Gaussian w.r.t. B, i.e., for any α∈Y∗

Ey∼μ[exp(α(y−y0))]≤exp(σ2B−1α⊗22)

Proof of Proposition A.3

By isomorphism, it is sufficient to consider the case Y=Rn, B(v,w)=v⋅w, α(v)=tv0 for some n∈N and t∈[0,∞). For this form of α it is sufficient to consider the case n=1. It remains to show that

Ey∼μ[et(y−y0)]≤e12σ2t2=e4t2

Here, we assume that Pry∼μ[|y|≤1]=1.

We consider separately the cases t≥12 and t<12. In the first case

Ey∼μ[et(y−y0)]≤maxy∈[−1,+1]et(y−y0)≤e2t≤e(2t)2=e4t2

In the second case, we use that for any x∈(−∞,+1]

ex<1+x+e2x2

The above holds because, at x=0 the left hand side and the right hand have the same value and first derivative, and for any x∈(−∞,+1), the second derivative of the left hand side is less than the second derivative of the right hand side. We get

Ey∼μ[et(y−y0)]≤Ey∼μ[1+t(y−y0)+e2t2(y−y0)2]=1+e2t2Vary∼μ[y]≤1+e2t2≤ee2t2≤e4t2

Q.E.D.

Definition A.1

Consider a set X, a finite-dimensional real vector space Y, some F⊆{X→Y} and a family {Bx∈PSD(Y)}x∈X. Assume F is compact w.r.t. the product topology on X→Y≅∏x∈XY. Consider also some n∈N, x∈Xn, y∈Yn and r∈R+. We then use the notation

LSF[xy,B]:=argminf∈Fn−1∑m=0Bxm(f(xm)−y)⊗2

CSF[xy,B]:={f∈F∣∣ ∣∣n−1∑m=0Bxm(f(xm)−LSFB[xy](xm))⊗2≤1}

I chose the notation LS as an abbreviation of "least squares" and CS as an abbreviation of "confidence set". Note that LS is somewhat ambiguous (and therefore, so is CS) since there might be multiple minima, but this will not be important in the following (i.e. an arbitrary minimum can be chosen).

Proposition A.4

There is some CA.4∈R+ s.t. the following holds.

Consider finite sets X,S, some F⊆{Xk→S} and a family {Bx∈PSD(RS)}x∈X. Assume that for any x∈X and φ∈ΔS, Bxφ⊗2≤1. Let {Hn⊆P(Xω×Sω)}n∈N be the canonical filtration, i.e.

Hn:={A′⊆Xω×Sω∣∣A′={xs|xs:n∈A}, A⊆Xn×Sn}

Consider also f∗∈F and μ∈Δ(Xω×Sω) s.t. for any n∈N, x∈X, and s∈S

Prxs∼μ[sn=s|xn=x, Hn]=f∗(s∣x)

Fix ϵ∈R+, δ∈(0,1). Denote

β(t):=CA.4(lnN(F,ϵ−2B)δ+ϵtlnetδ)

Then,

Prxs∼μ[f∗∉∞⋂n=0CSF[xs:n,β(n+1)−1B]]≤δ

Proof of Proposition A.4

For each x∈X, choose a finite set Ex and a linear mapping Px:RS→REx s.t. Bx(v,w)=Px(v)⋅Px(w). Let ~Y:=⨁x∈XREx. Define ~F⊆{X→~Y} by

~F:={~f:X→~Y∣∣~f(x)=Px(f(x)), f∈F}

Define Pω:Xω×Sω→Xω×~Yω by

Pω(xs)n:=xnPxn(sn)

Let ~f∗:=Pω(f∗) and ~μ:=Pω∗μ. By Proposition A.3, ~μ is 2√2-sub-Gaussian. Applying Proposition B.1 (see Appendix) to the tilde objects gives the desired result. Here, we choose the constant CA.4 s.t. the term M=1 in β as defined in Proposition B.1 is absorbed by the term σlnetδ≥1 (note that t≥1 since we substitute t=n+1, δ<1 and 1">σ=2√2>1). Q.E.D.

Definition A.2

Consider a set X, some x∈X, a real vector space Y, some F⊆{X→Y} and a family {Bx∈PSD(Y)}x∈X. The B-width of F at x is defined by

WF(x,B):=supf,~f∈F√Bx(f(x)−~f(x))⊗2

Proposition A.5

There is some CA.5∈R+ s.t. the following holds.

Consider a set X, a real vector space Y, some F⊆{X→Y} and a family {Bx∈PSD(Y)}x∈X. Consider also some x∈Xω, y∈Yω, T∈N+, γ∈(0,1), θ∈R+, η0,η1∈R+ and δ∈(0,1). Denote

β(t):=η0+η1tlnetδ

For any n∈N, define Fn by

Fn:=CSF[xy:n,β(n+1)−1B]

Assume that \frac{1}{2}">γT>12. Then,

\theta]]} \leq C_{\mathrm{A.5}}\RVO{\F}\cdot\AP{\theta^{-2}\beta\AP{\frac{1}{1-\gamma}}+T}">∞∑l=0T−1∑m=0γlT+m[[WFlT(xlT+m,B)>θ]]≤CA.5dimRVOF⋅(θ−2β(11−γ)+T)

Proof of Proposition A.5

For each x∈X, choose a finite set Ex and a linear mapping Px:Y→REx s.t. Bx(v,w)=Px(v)⋅Px(w). Let ~Y:=⨁x∈XREx. Define ~F⊆{X→~Y} by

~F:={~f:X→~Y∣∣~f(x)=Px(f(x)), f∈F}

Define also ~y by

~yn=Pxn(yn)

Applying Proposition B.2 (see Appendix) to the tilde objects, we conclude that for any N∈N

\theta]]} \leq \RVO{\F}\cdot\AP{4\theta^{-2}\beta(NT)+T}">N−1∑l=0T−1∑m=0[[WFlT(xlT+m,B)>θ]]≤dimRVOF⋅(4θ−2β(NT)+T)

Multiplying the inequality by γNT and summing over N, we get

\theta]]} \leq \RVO{\F}\sum_{N=0}^\infty\gamma^{NT}\AP{4\theta^{-2}\beta(NT)+T}">∞∑l=0(∞∑N=l+1γNT)T−1∑m=0[[WFlT(xlT+m,B)>θ]]≤dimRVOF∞∑N=0γNT(4θ−2β(NT)+T)

On the left hand side, we sum the geometric series. On the right hand side, we use the observation that

γNT(4θ−2β(NT)+T)≤1T∫T0γNT+t−T(4θ−2β(NT+t)+T)dt

γNT(4θ−2β(NT)+T)≤1TγT∫T0γNT+t(4θ−2β(NT+t)+T)dt

Here, we used that β(t) is an increasing function for t≥1 and β(0)=0. We get

\theta]]} \leq \frac{\RVO{\F}}{T\gamma^T}\int_0^\infty\gamma^{t}\AP{4\theta^{-2}\beta(t)+T}\D t">∞∑l=0γ(l+1)T1−γTT−1∑m=0[[WFlT(xlT+m,B)>θ]]≤dimRVOFTγT∫∞0γt(4θ−2β(t)+T)dt

The integral on the right hand side is a Laplace transform (where the dual variable is s=ln1γ). The functions f(t)=1, f(t)=t and f(t)=tlnt all have the property that, for any s∈R+

L[f](s)≤1sf(1s)

Indeed, we have

L[1](s)=1s≤1s

L[t](s)=1s2≤1s⋅1s

L[tlnt](s)=−lns+γEM−1s2=1s⋅1s(ln1s+1−γEM)≤1s⋅1sln1s

Here, γEM is the Euler-Mascheroni constant.

We conclude

\theta]]} \leq \frac{\RVO{\F}}{T\gamma^T}\cdot\frac{1}{\ln{\frac{1}{\gamma}}}\AP{4\theta^{-2}\beta\AP{\frac{1}{\ln\frac{1}{\gamma}}}+T}">γT1−γT∞∑l=0γlTT−1∑m=0[[WFlT(xlT+m,B)>θ]]≤dimRVOFTγT⋅1ln1γ⎛⎝4θ−2β⎛⎝1ln1γ⎞⎠+T⎞⎠

Using the condition \frac{1}{2}">γT>12 and absorbing O(1) factors into the definition of CA.5, we get

\theta]]} \leq C_{\text{A.5}}\RVO{\F}\cdot\AP{\theta^{-2}\beta\AP{\frac{1}{1-\gamma}}+T}">∞∑l=0γlTT−1∑m=0[[WFlT(xlT+m,B)>θ]]≤CA.5dimRVOF⋅(θ−2β(11−γ)+T)

Since γm≤1, this implies

\theta]]} \leq C_{\mathrm{A.5}}\RVO{\F}\cdot\AP{\theta^{-2}\beta\AP{\frac{1}{1-\gamma}}+T}">∞∑l=0T−1∑m=0γlT+m[[WFlT(xlT+m,B)>θ]]≤CA.5dimRVOF⋅(θ−2β(11−γ)+T)

Q.E.D.

Proposition A.6

There is some CA.6∈R+ s.t. the following holds.

Consider a set X, a real vector space Y, some F⊆{X→Y} and a family {Bx∈PSD(Y)}x∈X. Assume that for any x∈X and f∈F, Bxf(x)⊗2≤1. Consider also some x∈Xω, y∈Yω, T∈N+, γ∈(0,1), η0,η1∈R+ and δ∈(0,1). Define β and Fn the same way as in Proposition A.5. Denote D:=dimRVOF. Assume 0">D>0 and \frac{1}{2}">γT>12. Then,

∞∑l=0T−1∑m=0γlT+mWFlT(xlT+m,B)≤CA.6(DT+√Dβ(11−γ)11−γ)

Proof of Proposition A.6

Due to the assumption Bxf(x)⊗2≤1, we have WFn(x,B)≤2. For any t∈R+, we have

\theta]]\D\theta\leq t+\int_t^2[[\W^{F_{lT}}\AP{\boldsymbol{x}_{lT+m},B}>\theta]]\D\theta">WFlT(xlT+m,B)=∫20[[WFlT(xlT+m,B)>θ]]dθ≤t+∫2t[[WFlT(xlT+m,B)>θ]]dθ

\theta]]}\D\theta">∞∑l=0T−1∑m=0γlT+mWFlT(xlT+m,B)≤t1−γ+∫2t∞∑l=0T−1∑m=0γlT+m[[WFlT(xlT+m,B)>θ]]dθ

Applying Proposition A.5 to the right hand side

∞∑l=0T−1∑m=0γlT+mWFlT(xlT+m,B)≤t1−γ+CA.5D∫2t(θ−2β(11−γ)+T)dθ

Evaluating the integral and dropping some negative terms on the right hand side, we get

∞∑l=0T−1∑m=0γlT+mWFlT(xlT+m,B)≤t1−γ+CA.5D(1tβ(11−γ)+2T)

We now set t to be

t:=√Dβ(11−γ)⋅(1−γ)

For an appropriate choice of CA.6, it follows that

∞∑l=0T−1∑m=0γlT+mWFlT(xlT+m,B)≤CA.6(DT+√Dβ(11−γ)11−γ)

Q.E.D.

Proof of Theorem 1

We take π†γ:=πPSζΠT where Π is as in Proposition A.1 and T∈N+ will be specified later. Denote the Bayesian regret by

R(γ):=ET∼ζ[EU∗TR(γ)−EUπ†γTR(γ)]

By Proposition A.1

R(γ)=∞∑n=0γn+1E[EHn−H∗[VHnR(γ)|Θn,An]]+∞∑l=0γ(l+1)TE[E¯ETl−ETl[VH∗R(γ)|ΘlT]]

R(γ)≤∞∑n=0γnE[∣∣∣EHn−H∗[VHnR(γ)|Θn,An]∣∣∣]+∞∑l=0γlTE[∣∣ ∣∣E¯ETl−ETl[VH∗R(γ)|ΘlT]∣∣ ∣∣]

We will use the notation

ΔV(γ):=maxT∈H(maxs∈SVTR(s,γ)−mins∈SVTR(s,γ))

It follows that

R(γ)≤ΔV(γ)(∞∑n=0γnE[dtv(Hn(Θn,An),H∗(Θn,An))]+∞∑l=0γlTE[dtv(ETlT(ΘlT),¯ETlT(ΘlT))])

R(γ)≤ΔV(γ)(∞∑n=0γnE[dtv(Hn(Θn,An),H∗(Θn,An))]+11−γT)

Consider Y=RS equipped with the L1 norm. Given s∈S and a∈A, consider also the subspace

Wsa:=span{T(s,a)|T∈H}

By Proposition A.2, there is Bsa∈PSD(Y) s.t.

  1. For any φ∈ΔS

Bsaφ⊗2≤1

  1. For any T,~T∈H

14D2locBsa(T(s,a)−~T(s,a))⊗2≥dtv(T(s,a),~T(s,a))2

We now apply Proposition A.4 with δ:=12(1−γ)2 and ϵ:=(1−γ)2. We get

Pr[H∗∈∞⋂n=0CSH[ΘA:nΘn,β(n+1)−1B]]≥1−12(1−γ)2

Here, β was defined in Proposition A.4.

Since the hypothesis Hn is sampled from the posterior, for any l∈N we also have

Pr[HlT∈CSH[ΘA:lTΘlT,β(lT+1)−1B]]≥1−12(1−γ)2

Pr[H∗,HlT∈CSH[ΘA:lTΘlT,β(lT+1)−1B]]≥1−(1−γ)2

Denote

Gn:={H∗,HlT∈CSH[ΘA:lTΘlT,β(lT+1)−1B]}⊆Ω

We get

R(γ)≤ΔV(γ)∞∑n=0γn(E[dtv(Hn(Θn,An),H∗(Θn,An));Gn]+(1−γ)2)

R(γ)≤ΔV(γ)(∞∑n=0γnE[dtv(Hn(Θn,An),H∗(Θn,An));Gn]+1−γ+11−γT)

Using property 2 of B

R(γ)≤ΔV(γ)(12Dloc∞∑n=0γnE[√BΘnAn(Hn(Θn,An)−H∗(Θn,An))⊗2;Gn]+1−γ+11−γT)

Denote

Hl:=CSH[ΘA:lTΘlT,β(lT+1)−1B]

Clearly

Pr[√BΘnAn(Hn(Θn,An)−H∗(Θn,An))⊗2≤WH⌊n/T⌋(ΘnAn,B);Gn]=1

Using this inequality, dropping the ;Gn (since it can only the right hand side smaller) and moving the sum inside the expected value, we get

R(γ)≤ΔV(γ)(12DlocE[∞∑n=0γnWH⌊n/T⌋(ΘnAn,B)]+1−γ+11−γT)

We will now assume 0">DRVO>0 (if DRVO=0, then |H|=1 and R(γ)=0) and \frac{1}{2}">γT>12. Applying Proposition A.6, we conclude

R(γ)≤ΔV(γ)(DlocCA.62(DRVOT+√DRVOβ(11−γ)11−γ)+1−γ+11−γT)

Denote the second factor on the right hand side F(γ), so that the inequality becomes

R(γ)≤ΔV(γ)F(γ)

We set

T:=⎢⎢ ⎢ ⎢ ⎢⎣1√DlocDRVO(1−γ)ln11−γ⎥⎥ ⎥ ⎥ ⎥⎦

Now, we analyze the γ→1 limit. In this limit, the expression for T justifies our assumption that \frac{1}{2}">γT>12. Indeed, we have

limγ→1lnγT=limγ→1Tlnγ=limγ→1lnγ√DlocDRVO(1−γ)ln11−γ=0

Using the previous inequality for R(γ), we get

limsupγ→1R(γ)√(1−γ)ln11−γ≤limsupγ→1ΔV(γ)F(γ)√(1−γ)ln11−γ

We assume τζR<∞, otherwise the theorem is vacuous. Multiplying the numerator and denominator on the right hand side by √1−γ, we get

limsupγ→1R(γ)√(1−γ)ln11−γ≤τζRlimsupγ→1 ⎷1−γln11−γ⋅F(γ)

We will now analyze the contribution of each term in F(γ) to the limit on the right hand side (using the fact that limsup(F1+F2)≤limsupF1+limsupF2). We ignore multiplicative constants that can be absorbed into C.

The first term gives (using our choice of T)

limsupγ→1 ⎷1−γln11−γ⋅ ⎷DlocDRVO(1−γ)ln11−γ=0

The second term gives (using the definitions of β and our choices of δ and ϵ)

limsupγ→1 ⎷1−γln11−γ⋅Dloc ⎷DRVO(ln2N(H,(1−γ)−4B)(1−γ)2+(1−γ)ln2e(1−γ)3)11−γ≤

limsupγ→1 ⎷1−γln11−γ⋅Dloc√DRVO1−γ⎛⎝√lnN(H,(1−γ)−4B)+√ln2(1−γ)+√(1−γ)ln2e(1−γ)3⎞⎠

We analyze each subterm separately. The first subterm gives

limsupγ→1 ⎷1−γln11−γ⋅Dloc√DRVO1−γlnN(H,(1−γ)−4B)=

Dloc√DRVOlimsupγ→1 ⎷lnN(H,(1−γ)−4B)12ln1(1−γ)2≤

Dloc√2DRVODMB

The second subterm gives

limsupγ→1 ⎷1−γln11−γ⋅Dloc√DRVO1−γln21−γ=Dloc√DRVO

The third subterm gives

limsupγ→1 ⎷1−γln11−γ⋅Dloc√DRVO1−γ(1−γ)ln2e(1−γ)3=0

The third and fourth terms give

limsupγ→1 ⎷1−γln11−γ⋅(1−γ)=0

To analyze the fifth term, observe that limγ→1(1−γ)T(γ)=0. Hence

limsupγ→1 ⎷1−γln11−γ⋅11−γT(γ)=

limsupγ→1 ⎷1−γln11−γ⋅1(1−γ)T(γ)=

limsupγ→1 ⎷1−γln11−γ⋅√DlocDRVO(1−γ)ln11−γ(1−γ)=

√DlocDRVO

Putting everything together, we observe that the expression Dloc√DRVO(DMB+1) dominates all the terms (up to a multiplicative constant). Here, we use that Dloc is an integer and hence Dloc≥√Dloc. We conclude

limsupγ→1R(γ)√(1−γ)ln11−γ≤CτζRDloc√DRVO(DMB+1)

Q.E.D.

Appendix

The following was proved in John (1948), available in the collection Giorgi and Kjeldesen (2014) (the theorem in question is on page 214).

Theorem B.1 (John)

Consider a real finite-dimensional normed vector space Y. Then, there exists B∈PD(Y) s.t. for any v∈Y

Bv⊗2≤∥v∥2≤dimY⋅Bv⊗2

The following is from Kadets and Snobar (1971).

Theorem B.2 (Kadets-Snobar)

Consider a real Banach space Y and a finite-dimensional linear subspace Z⊆Y. Then, for any ϵ∈R+, there is a projection operator P:Y→Y s.t. imP=Z and ∥P∥<√dimZ+ϵ.

Corollary B.1

Consider a real finite-dimensional normed vector space Y and a linear subspace Z⊆Y. Then, there is a projection operator P⋆:Y→Y s.t. imP⋆=Z and ∥P⋆∥≤√dimZ.

Proof of Corollary B.1

Let End(Y) be the vector space of linear operators Y→Y. Define

Pr(Y,Z):={P∈End(Y)∣∣P2=P, imP=Z}

X:={P∈Pr(Y,Z)∣∣∥P∥≤√dimZ+1}

Pr(Y,Z) is an affine subspace of End(Y) and X is a compact set. Define f:X→R by f(P):=∥P∥. f is a continuous function. By Theorem B.2, inff≤√dimZ. Since X is compact, f attains its infimum at some P⋆∈X, and we have f(P⋆)≤√dimZ, Q.E.D.

The next proposition appeared (in slightly greater generality) in Osband and Van Roy as "Proposition 5". We will use Id∈PD(Rd) to denote the form corresponding to the identity matrix.

Proposition B.1 (Osband-Van Roy)

There is some CB.1∈R+ s.t. the following holds.

Consider a finite set X, the vector space Y:=Rd for some d∈N and some F⊆{X→Y}. Let {Hn⊆P(Xω×Yω)}n∈N be the canonical filtration, i.e.

Hn:={A′⊆Xω×Yω∣∣A′={xy|xy:n∈A}, A⊆Xn×Yn Borel}

Consider also f∗∈F and μ∈Δ(Xω×Yω) s.t. for any n∈N and x∈X

Exy∼μ[yn|xn=x, Hn]=f∗(x)

Assume that M∈R+ is s.t. yn⋅yn≤M2 with μ-probability 1 for all n∈N. Assume also that σ∈R+ is s.t. μ is σ-sub-Gaussian, i.e., for any α∈Y, n∈N and x∈X

Exy∼μ[exp(α⋅(yn−f∗(x)))|xn=x, Hn]≤exp(σ2(α⋅α)2)

Fix ϵ∈R+, δ∈(0,1). Define β:R+→R by

β(t):=CB.1(σ2lnN(F,ϵ−2Id)δ+ϵt(M+σlnetδ))

Then,

Prxy∼μ[f∗∉∞⋂n=0CSF[xy:n,β(n+1)−1Id]]≤δ

Note that we removed a square root in the definition of β compared to equation (7) in Osband and Van Roy. This only makes β larger (up to a constant factor) and therefore, only makes the claim weaker.

The proposition below appeared in Osband and Van Roy as "Lemma 1".

Proposition B.2 (Osband-Van Roy)

Consider a set X, the vector space Y=Rd for some d∈N and some F⊆{X→Y}. Consider also some x∈Xω, y∈Yω, T∈N+, N∈N, θ∈R+, δ∈(0,1) and a nondecreasing sequence {βn∈R+}n∈N. For any n∈N, define Fn by

Fn:=CSF[xy:n,β−1nId]

Then,

\theta]]} \leq \RVO{\F}\cdot\AP{4\theta^{-2}\beta_{NT-1}+T}">N−1∑l=0T−1∑m=0[[WFlT(xlT+m,Id)>θ]]≤dimRVOF⋅(4θ−2βNT−1+T)



Discuss

History of LessWrong: Some Data Graphics

16 ноября, 2018 - 10:07
Published on Fri Nov 16 2018 07:07:15 GMT+0000 (UTC)

Some graphs showing posting activity on LessWrong through the years.

NOTE: If you’re reading this post on GreaterWrong, you can click on the images to enlarge, zoom in, and click through them all as a slideshow.

Comments per post:

The same thing, on a log scale:

Posts per month:

The 100 most prolific authors over LessWrong’s lifespan:

The same thing, on a log scale:

Whose posts have generated the most total discussion?

As above, but on a log scale:

Data available in a Google Docs spreadsheet. (Or download in CSV format.)

You can also download an Excel spreadsheet, which contains the above graphs and some intermediate processed data.



Discuss

Sam Harris and the Is–Ought Gap

16 ноября, 2018 - 04:04
Published on Fri Nov 16 2018 01:04:08 GMT+0000 (UTC)

Many secular materialist are puzzled by Sam Harris's frequent assertion that science can bridge Hume's is–ought gap. Indeed, bafflement abounds on both sides whenever he debates his "bridge" with other materialists. Both sides are unable to understand how the other can fail to grasp elementary and undeniable points. This podcast conversation with the physicist Sean Carroll provides a vivid yet amicable demonstration.

I believe that this mutual confusion is a consequence of two distinct but unspoken ways of thinking about idealized moral argumentation. I'll call these two ways logical and dialectical.

Roughly, logical argumentation is focused on logical proofs of statements. Dialectical argumentation is geared towards rational persuasion of agents. These two different approaches lead to very different conclusions about what kinds of statements are necessary in rigorous moral arguments. In particular, the is–ought gap is unavoidable when you take the logical point of view. But this gap evaporates when you take the dialectical point of view.[1]

I won't be arguing for one of these views over the other. My goal is rather to dissolve disagreement. I believe that properly understanding these two views will render a lot of arguments unnecessary.

Logical moral argumentation

Logical argumentation, in the sense in which I'm using the term here, is focused on finding rigorous logical proofs of moral statements. The reasoning proceeds by logical inference from premises to conclusion. The ideal model is something like a theory in mathematical logic, with all conclusions proved from a basic set of axioms using just the rules of logic.

People who undertake moral argumentation with this ideal in mind envision a theory that can express "is" statements, but which also contains an "ought" symbol. Under suitable circumstances, the theory proves "is" statements like "You are pulling the switch that diverts the trolley," and "If you pull the switch, the trolley will be diverted." But what makes the theory moral is that it can also prove "ought" statements like "You ought to pull the switch that diverts the trolley."[2]

Now, this "ought" symbol could appear in the ideal formal theory in one of only two ways: Either the "ought" symbol is an undefined symbol appearing among the axioms, or the "ought" symbol is subsequently defined in terms of the more-primitive "is" symbols used to express the axioms.[3]

When Harris claims to be able to bridge the is–ought gap in purely scientific terms, many listeners think that he's claiming to do so from this "logical argumentation" point of view. In that case, such a bridge would be successful only if every possible scientifically competent agent would accept the axioms of the theory used. In particular, "accepting" a statement that includes the "ought" symbol would mean something like "actually being motivated to do what the statement says that one 'ought' to do, at least in the limit of ideal reflection".

But, on these terms, the is–ought gap is unavoidable: No moral theory can be purely scientific in this sense. For, however "ought" is defined by a particular sequence of "is" symbols, there is always a possible scientifically competent agent who is not motivated by "ought" so defined.[4]

Thus, from this point of view, no moral theory can bridge the is–ought gap by scientific means alone. Moral argumentation must always include an "ought" symbol, but the use of this symbol cannot be justified on purely scientific grounds. This doesn't mean that moral arguments can't be successful at all. It doesn't even mean that they can't be objectively right or wrong. But it does mean that their justification must rest on premises that go beyond the purely scientific.

This is Sean Carroll's point of view in the podcast conversation with Harris linked above. But Harris, I claim, could not understand Carroll's argument, and Carroll in turn could not understand Harris's, because Harris is coming from the dialectical point of view.

Dialectical moral argumentation

Dialectical moral argumentation is not modeled on logical proof. Rather, it is modeled on rational persuasion. The ideal context envisioned here is a conversation between rational agents in which one of the agents is persuading the other to do something. The persuader proceeds from assertion to assertion until the listener is persuaded to act.[5]

But here is the point: Such arguments shouldn't include an "ought" symbol at all!—At least, not ideally.

By way of analogy, suppose that you're trying to convince me to eat some ice cream. (This is not a moral argument, which is why this is only an analogy.) Then obviously you can't use "You should eat ice cream" as an axiom, because that would be circular. But, more to the point, you wouldn't even have to use that statement in the course of your argument. Instead, ideally, your argument would just be a bunch of "is" facts about the ice cream (cold, creamy, sweet, and so on). If the ice cream has chocolate chips, and you know that I like chocolate chips, you will tell me facts about the chocolate chips (high in quantity and quality, etc.). But there's no need to add, "And you should eat chocolate chips."

Instead, you will just give me all of those "is" facts about the ice cream, maybe draw some "is" implications, and then rely on my internal motivational drives to find those facts compelling. If the "is" facts alone aren't motivating me, then something has gone wrong with the conversation. Either you as the persuader failed to pick facts that will motivate me, or I as the listener failed to understand properly the facts that you picked.

Now, practically speaking, when you attempt to persuade me to X, you might find it helpful to say things like "You ought to X". But, ideally, this usage of "ought" should serve just as a sort of signpost to help me to follow the argument, not as an essential part of the argument itself. Nonetheless, you might use "ought" as a framing device: "I'm about to convince you that you ought to X." Or: "Remember, I already convinced you that you ought to X. Now I'm going to convince you that doing X requires doing Y."

But an ideal argument wouldn't need any such signposts. You would just convince me of certain facts about the world, and then you'd leave it to my internal motivational drives to do the rest—to induce me to act as you desired on the basis of the facts that you showed me.

Put another way, if you're trying to persuade me to X, then you shouldn't have to tell me explicitly that doing X would be good. If you have to say that, then the "is" facts about X must not actually be motivating to me. But, in that case, just telling me that doing X would be good isn't going to convince me, so your argument has failed.

Likewise, if the statement "Doing X would cause Y" isn't already motivating, then the statement "Doing X would cause Y, and Y would be good" shouldn't be motivating either, at least not ideally. If you're doing your job right, you've already picked an is-statement Y that motivates me directly, or which entails another is-statement that will motivate me directly. So adding "and Y would be good" shouldn't be telling me anything useful. It would be at best a rhetorical flourish, and so not a part of ideal argumentation.

Thus, from this point of view, there really is a sense in which "ought" reduces to "is". The is–ought gap vanishes! Wherever "ought" appears, it will be found, on closer inspection, to be unnecessary. All of the rational work in the argument is done purely by "is". Of course, crucial work is also done by my internal motivational structure. Without that, your "is" statements couldn't have the desired effect. But that structure isn't part of your argument. In the argument itself, it's all just "is... is... is...", all the way down.

This, I take it, is Sam Harris's implicit point of view. Or, at least, it should be.

Footnotes

[1] I am not saying that these views of moral argumentation exhaust all of the possibilities. I'm not even saying that they are mutually exclusive in practice. Normally, people slide among such views as the needs of the situation require. But I think that some people tend to get needlessly locked into one view when they try to think abstractly about what counts as a valid and rigorous moral argument.

[2] From the logical point of view, all moral argumentation is first and foremost about the assertions that we can prove. Argumentation is not directly about action. There is only an indirect connection to action in the sense that arguments can prove assertions about actions, like "X ought to be done". Furthermore, this "ought" must be explicit. Otherwise, you're just proving "is" statements.

[3] Analogously, you can get the symbol .mjx-chtml {display: inline-block; line-height: 0; text-indent: 0; text-align: left; text-transform: none; font-style: normal; font-weight: normal; font-size: 100%; font-size-adjust: none; letter-spacing: normal; word-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; margin: 0; padding: 1px 0} .MJXc-display {display: block; text-align: center; margin: 1em 0; padding: 0} .mjx-chtml[tabindex]:focus, body :focus .mjx-chtml[tabindex] {display: inline-table} .mjx-full-width {text-align: center; display: table-cell!important; width: 10000em} .mjx-math {display: inline-block; border-collapse: separate; border-spacing: 0} .mjx-math * {display: inline-block; -webkit-box-sizing: content-box!important; -moz-box-sizing: content-box!important; box-sizing: content-box!important; text-align: left} .mjx-numerator {display: block; text-align: center} .mjx-denominator {display: block; text-align: center} .MJXc-stacked {height: 0; position: relative} .MJXc-stacked > * {position: absolute} .MJXc-bevelled > * {display: inline-block} .mjx-stack {display: inline-block} .mjx-op {display: block} .mjx-under {display: table-cell} .mjx-over {display: block} .mjx-over > * {padding-left: 0px!important; padding-right: 0px!important} .mjx-under > * {padding-left: 0px!important; padding-right: 0px!important} .mjx-stack > .mjx-sup {display: block} .mjx-stack > .mjx-sub {display: block} .mjx-prestack > .mjx-presup {display: block} .mjx-prestack > .mjx-presub {display: block} .mjx-delim-h > .mjx-char {display: inline-block} .mjx-surd {vertical-align: top} .mjx-mphantom * {visibility: hidden} .mjx-merror {background-color: #FFFF88; color: #CC0000; border: 1px solid #CC0000; padding: 2px 3px; font-style: normal; font-size: 90%} .mjx-annotation-xml {line-height: normal} .mjx-menclose > svg {fill: none; stroke: currentColor} .mjx-mtr {display: table-row} .mjx-mlabeledtr {display: table-row} .mjx-mtd {display: table-cell; text-align: center} .mjx-label {display: table-row} .mjx-box {display: inline-block} .mjx-block {display: block} .mjx-span {display: inline} .mjx-char {display: block; white-space: pre} .mjx-itable {display: inline-table; width: auto} .mjx-row {display: table-row} .mjx-cell {display: table-cell} .mjx-table {display: table; width: 100%} .mjx-line {display: block; height: 0} .mjx-strut {width: 0; padding-top: 1em} .mjx-vsize {width: 0} .MJXc-space1 {margin-left: .167em} .MJXc-space2 {margin-left: .222em} .MJXc-space3 {margin-left: .278em} .mjx-test.mjx-test-display {display: table!important} .mjx-test.mjx-test-inline {display: inline!important; margin-right: -1px} .mjx-test.mjx-test-default {display: block!important; clear: both} .mjx-ex-box {display: inline-block!important; position: absolute; overflow: hidden; min-height: 0; max-height: none; padding: 0; border: 0; margin: 0; width: 1px; height: 60ex} .mjx-test-inline .mjx-left-box {display: inline-block; width: 0; float: left} .mjx-test-inline .mjx-right-box {display: inline-block; width: 0; float: right} .mjx-test-display .mjx-right-box {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} .MJXc-TeX-unknown-R {font-family: monospace; font-style: normal; font-weight: normal} .MJXc-TeX-unknown-I {font-family: monospace; font-style: italic; font-weight: normal} .MJXc-TeX-unknown-B {font-family: monospace; font-style: normal; font-weight: bold} .MJXc-TeX-unknown-BI {font-family: monospace; font-style: italic; font-weight: bold} .MJXc-TeX-ams-R {font-family: MJXc-TeX-ams-R,MJXc-TeX-ams-Rw} .MJXc-TeX-cal-B {font-family: MJXc-TeX-cal-B,MJXc-TeX-cal-Bx,MJXc-TeX-cal-Bw} .MJXc-TeX-frak-R {font-family: MJXc-TeX-frak-R,MJXc-TeX-frak-Rw} .MJXc-TeX-frak-B {font-family: MJXc-TeX-frak-B,MJXc-TeX-frak-Bx,MJXc-TeX-frak-Bw} .MJXc-TeX-math-BI {font-family: MJXc-TeX-math-BI,MJXc-TeX-math-BIx,MJXc-TeX-math-BIw} .MJXc-TeX-sans-R {font-family: MJXc-TeX-sans-R,MJXc-TeX-sans-Rw} .MJXc-TeX-sans-B {font-family: MJXc-TeX-sans-B,MJXc-TeX-sans-Bx,MJXc-TeX-sans-Bw} .MJXc-TeX-sans-I {font-family: MJXc-TeX-sans-I,MJXc-TeX-sans-Ix,MJXc-TeX-sans-Iw} .MJXc-TeX-script-R {font-family: MJXc-TeX-script-R,MJXc-TeX-script-Rw} .MJXc-TeX-type-R {font-family: MJXc-TeX-type-R,MJXc-TeX-type-Rw} .MJXc-TeX-cal-R {font-family: MJXc-TeX-cal-R,MJXc-TeX-cal-Rw} .MJXc-TeX-main-B {font-family: MJXc-TeX-main-B,MJXc-TeX-main-Bx,MJXc-TeX-main-Bw} .MJXc-TeX-main-I {font-family: MJXc-TeX-main-I,MJXc-TeX-main-Ix,MJXc-TeX-main-Iw} .MJXc-TeX-main-R {font-family: MJXc-TeX-main-R,MJXc-TeX-main-Rw} .MJXc-TeX-math-I {font-family: MJXc-TeX-math-I,MJXc-TeX-math-Ix,MJXc-TeX-math-Iw} .MJXc-TeX-size1-R {font-family: MJXc-TeX-size1-R,MJXc-TeX-size1-Rw} .MJXc-TeX-size2-R {font-family: MJXc-TeX-size2-R,MJXc-TeX-size2-Rw} .MJXc-TeX-size3-R {font-family: MJXc-TeX-size3-R,MJXc-TeX-size3-Rw} .MJXc-TeX-size4-R {font-family: MJXc-TeX-size4-R,MJXc-TeX-size4-Rw} .MJXc-TeX-vec-R {font-family: MJXc-TeX-vec-R,MJXc-TeX-vec-Rw} .MJXc-TeX-vec-B {font-family: MJXc-TeX-vec-B,MJXc-TeX-vec-Bx,MJXc-TeX-vec-Bw} @font-face {font-family: MJXc-TeX-ams-R; src: local('MathJax_AMS'), local('MathJax_AMS-Regular')} @font-face {font-family: MJXc-TeX-ams-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_AMS-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_AMS-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_AMS-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-cal-B; src: local('MathJax_Caligraphic Bold'), local('MathJax_Caligraphic-Bold')} @font-face {font-family: MJXc-TeX-cal-Bx; src: local('MathJax_Caligraphic'); font-weight: bold} @font-face {font-family: MJXc-TeX-cal-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Caligraphic-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Caligraphic-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Caligraphic-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-frak-R; src: local('MathJax_Fraktur'), local('MathJax_Fraktur-Regular')} @font-face {font-family: MJXc-TeX-frak-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Fraktur-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Fraktur-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Fraktur-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-frak-B; src: local('MathJax_Fraktur Bold'), local('MathJax_Fraktur-Bold')} @font-face {font-family: MJXc-TeX-frak-Bx; src: local('MathJax_Fraktur'); font-weight: bold} @font-face {font-family: MJXc-TeX-frak-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Fraktur-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Fraktur-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Fraktur-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-math-BI; src: local('MathJax_Math BoldItalic'), local('MathJax_Math-BoldItalic')} @font-face {font-family: MJXc-TeX-math-BIx; src: local('MathJax_Math'); font-weight: bold; font-style: italic} @font-face {font-family: MJXc-TeX-math-BIw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Math-BoldItalic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Math-BoldItalic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Math-BoldItalic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-R; src: local('MathJax_SansSerif'), local('MathJax_SansSerif-Regular')} @font-face {font-family: MJXc-TeX-sans-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-B; src: local('MathJax_SansSerif Bold'), local('MathJax_SansSerif-Bold')} @font-face {font-family: MJXc-TeX-sans-Bx; src: local('MathJax_SansSerif'); font-weight: bold} @font-face {font-family: MJXc-TeX-sans-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-sans-I; src: local('MathJax_SansSerif Italic'), local('MathJax_SansSerif-Italic')} @font-face {font-family: MJXc-TeX-sans-Ix; src: local('MathJax_SansSerif'); font-style: italic} @font-face {font-family: MJXc-TeX-sans-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_SansSerif-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_SansSerif-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_SansSerif-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-script-R; src: local('MathJax_Script'), local('MathJax_Script-Regular')} @font-face {font-family: MJXc-TeX-script-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Script-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Script-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Script-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-type-R; src: local('MathJax_Typewriter'), local('MathJax_Typewriter-Regular')} @font-face {font-family: MJXc-TeX-type-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Typewriter-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Typewriter-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Typewriter-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-cal-R; src: local('MathJax_Caligraphic'), local('MathJax_Caligraphic-Regular')} @font-face {font-family: MJXc-TeX-cal-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Caligraphic-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Caligraphic-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Caligraphic-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-B; src: local('MathJax_Main Bold'), local('MathJax_Main-Bold')} @font-face {font-family: MJXc-TeX-main-Bx; src: local('MathJax_Main'); font-weight: bold} @font-face {font-family: MJXc-TeX-main-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Bold.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-I; src: local('MathJax_Main Italic'), local('MathJax_Main-Italic')} @font-face {font-family: MJXc-TeX-main-Ix; src: local('MathJax_Main'); font-style: italic} @font-face {font-family: MJXc-TeX-main-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-main-R; src: local('MathJax_Main'), local('MathJax_Main-Regular')} @font-face {font-family: MJXc-TeX-main-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Main-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Main-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Main-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-math-I; src: local('MathJax_Math Italic'), local('MathJax_Math-Italic')} @font-face {font-family: MJXc-TeX-math-Ix; src: local('MathJax_Math'); font-style: italic} @font-face {font-family: MJXc-TeX-math-Iw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Math-Italic.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Math-Italic.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Math-Italic.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size1-R; src: local('MathJax_Size1'), local('MathJax_Size1-Regular')} @font-face {font-family: MJXc-TeX-size1-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size1-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size1-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size1-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size2-R; src: local('MathJax_Size2'), local('MathJax_Size2-Regular')} @font-face {font-family: MJXc-TeX-size2-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size2-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size2-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size2-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size3-R; src: local('MathJax_Size3'), local('MathJax_Size3-Regular')} @font-face {font-family: MJXc-TeX-size3-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size3-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size3-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size3-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-size4-R; src: local('MathJax_Size4'), local('MathJax_Size4-Regular')} @font-face {font-family: MJXc-TeX-size4-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Size4-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Size4-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Size4-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-vec-R; src: local('MathJax_Vector'), local('MathJax_Vector-Regular')} @font-face {font-family: MJXc-TeX-vec-Rw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Vector-Regular.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Vector-Regular.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Vector-Regular.otf') format('opentype')} @font-face {font-family: MJXc-TeX-vec-B; src: local('MathJax_Vector Bold'), local('MathJax_Vector-Bold')} @font-face {font-family: MJXc-TeX-vec-Bx; src: local('MathJax_Vector'); font-weight: bold} @font-face {font-family: MJXc-TeX-vec-Bw; src /*1*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/eot/MathJax_Vector-Bold.eot'); src /*2*/: url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/woff/MathJax_Vector-Bold.woff') format('woff'), url('https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/fonts/HTML-CSS/TeX/otf/MathJax_Vector-Bold.otf') format('opentype')} + in a theory of arithmetic in two ways. On the one hand, in first-order Peano arithmetic, the + symbol is undefined, but it appears in the axioms, which govern its behavior. On the other hand, in the original second-order Peano axioms, there was no + symbol. Instead, there was only a successor-of symbol. But one may subsequently introduce + by defining it in terms of the successor-of symbol using second-order logic.

[4] Some might dispute this, especially regarding the meaning of the phrase "possible scientifically competent agent". But this is not the crux of the disagreement that I'm trying to dissolve.

[5] Here I mean "persuaded" in the sense of "choosing to act out of a sense of moral conviction", rather than out of considerations of taste or whatever.



Discuss

Страницы