Eliezer talks a lot about decision theory in his sequences, e.g. the Aumann agreement theorem or the von Neumann-Morgenstern utility theorem. From what I've seen so far, decision theory looks extremely interesting.

Which textbook in decision theory would you recommend to start with? I'd appreciate if the book contained not only theory, but also some exercise/problem section - I have noticed that usually a lecture is not enough to fully grasp a topic. I want a book which will not shy away from mathematical side of the theory.

I have a strong background in mathematics and computer science, but I only know a little about game theory.

There's actually only one comment on decision theory textbooks, which recommends the Martin Peterson's one. I skimmed through it at our library and it seems to be more directed at philosophy students and those with poor mathematical background. There's also Resnik or Luce & Raiffa mentioned but they are claimed to be out of date.

While it's always important to grasp the intuition, reading books for the "common people" will give you much slower progress than if you read a book meant for someone who already has solid mathematical foundations.