Skip navigation
The Australian National University
Advanced Topics in Artificial Intelligence COMP4620/COMP8620

Advanced Topics in Artificial Intelligence COMP4620/COMP8620

Welcome to the Advanced AI course at the ANU !

This year (2015) the course will focus on the Foundations of AI, including inductive inference, decision-making under uncertainty, reinforcement learning, intelligent agents, information theory, philosophical foundations, and others. Note that traditionally the course varies significantly from year to year. Material from other years is available from the left menu.


14Oct15: Written exam will be Thursday, 19.Nov.2015, 9:15-11:30, Melville Hall
4Sep15: Assignment 2 available
04Aug15: Assignment 1 available
26May15: website contents created


Offered By: The AI Group @ Research School of Computer Science @ Australian National University
Offered In: Second Semester, 2015 (20 July to 30 October). See Schedule below
Lecturer: Marcus Hutter
Tutors/Labs/Assistance: Tom Everitt
Target: Undergraduate (COMP4620) and Graduate (COMP8620) students. Others welcome.
Enrollment: Undergraduate & Masters: The usual way via ISIS. Honors&Others: Contact lecturer.
Admin: Bindi Mamouney
Course Subjects: Computer Science & Mathematics & Statistics
Unit Value: 6 units
Time Table: See Schedule below for details
Office hours: Wed 9ºº-10ºº, RSISE Bld 115, Room B259.
Indicative Assessment: Assignments (45%); Seminar (10%); Examination (45%) [details]
Indicative Workload: 25h lectures, 10h tutorial, 10h lab, ~50h assignments, lots of self-study
Prescribed texts: Excerpts from (see resources for details)
- Shane Legg (2008) Machine Super Intelligence
- Marcus Hutter (2005) Universal Artificial Intelligence
- Joel Veness et al. (2011) A Monte Carlo AIXI Approximation
ANU page:
Wattle page:
This page:

Prerequisites: If you have absolved the Machine Learning course COMP4670 or the Artificial Intelligence course COMP3620 or the Information Theory course COMP2610 you should have the necessary background for this course. Otherwise you can acquire the necessary background e.g. from the AI book Russell&Norvig (2010) Chp.2,3,5.2,5.5,13,15.1-2,17.1-3,21.
Chapter 1 of Li&Vitanyi (2008) is a great refresher of basic computer, information, and probability theory.

Course Description

This is an advanced undergraduate and graduate course that covers advanced topics in Artificial Intelligence. Topics vary from one offering to the next (see Study@ANU page). This year (2015) the course will focus on the foundations of AI, including inductive inference, decision-making, reinforcement learning, information theory, and some game and agent theory. The dream of creating artificial devices that reach or outperform human intelligence is many centuries old. This course presents an elegant parameter-free theory of an optimal reinforcement learning agent embedded in an arbitrary unknown environment that possesses essentially all aspects of rational intelligence. The theory reduces all conceptual AI problems to pure computational questions, and is key to addressing many theoretical, philosophical, and practical AI questions. How to perform inductive inference is closely related to the AI problem. The course covers Solomonoff's theory, which solves the induction problem, at least from a philosophical and statistical perspective. Both theories are based on Occam's razor quantified by Kolmogorov complexity, Bayesian probability theory, and sequential decision theory. The course is for computer science students interested in knowing about or building general AI systems from first principles, and others interested in the formal foundations of intelligence.

Learning Outcomes

While the Introduction to AI course taught a diversity of methods for solving a variety of AI problems, this Advanced AI course emphasizes the foundational, unifying, and general aspects of (artificial) intelligence. Course highlights are:
  • Formal definitions of (general rational) Intelligence;
  • Optimal rational agents for arbitrary problems;
  • Philosophical, mathematical, and computational background;
  • Some approximations, implementations, and applications;
  • State-of-the-art artificial general intelligence.
Despite this grand vision and mission, most of the course necessarily is devoted to introducing the key ingredients of this theory, which are important subjects in their own right. On completing this course students will have a solid understanding of:
  • measures, tests, and definitions of intelligence;
  • Occam's razor;
  • universal Turing machines;
  • algorithmic information theory;
  • probability theory;
  • universal induction;
  • Bayesian sequence prediction;
  • minimum description length principle;
  • intelligent agents;
  • sequential decision theory;
  • reinforcement learning;
  • planning under uncertainty;
  • universal search;
  • Monte-Carlo tree search;
  • philosophical foundations.
This theoretical background enables students at least in principle to analyze and develop generally intelligent systems, with the group project being a first step in this endeavor. Tutorials in the first half of the course will consolidate the knowledge via theoretical exercises. The group project in the second half is about approximating, implementing, and applying the theory to small problems like Tic-Tac-Toe, Poker, and Pacman.


Week Lecture Tutorial/Lab
to be updated throughout the course Tuesday and Wednesday 15ºº-16ºº
Chemistry Lecture Theatre T2 in Building 34
Thu.9-11ºº, Tut/Lab in N108/N114; CSIT Bld.108
20Jul - 24Jul Overview & Introduction [Advertizement]
[Slides] Reading:[Legg08.Chp.1]
27Jul - 31Jul Information Theory & Kolmogorov Complexity
[Slides] Reading:[UAIBook.Sec.2.2]
3Aug - 7Aug Bayesian Probability Theory
[Slides] Reading:[UAIBook.Sec.2.3]
get assignment 1
10Aug - 14Aug Algorithmic Probability & Universal Induction
[Slides] Reading:[UAIBook.Sec.2.4]
17Aug - 21Aug Minimum Description Length & Universal Similarity
[Slides,Slides] Optional Reading:[MDL.Chp.1,USM]
24Aug - 28Aug Bayesian Sequence Prediction & CTW
[Slides, Slides] Reading: Parts of [UAIBook.Chp.3,CTW]
31Aug - 4Sep Universal Rational Agents
[Slides] Reading:[UAIBook.Chp.4.1&4.2]
get assignment 2
orientation Lab
7Sep - 18Sep break ---
21Sep - 25Sep Theory of Rational Agents
[Slides] Reading:try[UAIBook.Chp.5]
hand in assignment 1
28Sep - 2oct Approximations and Applications
tutorial: solutions to assignment 1
5oct - 9oct MC-AIXI-CTW
[Slides] Reading:[MC-AIXI-CTW]
12oct - 16oct Discussion
[Slides] Reading:[UAIBook.Chp.8]
19oct - 23oct Discussion lab+
hand in assignment 2
26oct - 30oct Student Presentation of Individual Contribution to Practical Assignment. Send slides in advance to Tom Everitt. ---

Written exam will be Thursday, 19 November 2015, 9:15-11:30, Melville Hall, see official Time Table and Assessment section below for details.


Theory Assignment 1: The theory assignment is to be done individually, and will involve various mathematical exercises that will deepen the understanding of the lectured material. Tom Everitt will be tutor and primary contact for the theory assignment.

Practical Group Assignment 2: The practical assignment will be a group project. Goal is to implement the MC-AIXI-CTW model, which is a recent practical scaled-down version of the theoretical universal AI agent AIXI. Students will acquire first-hand experience how a single algorithm can autonomously learn to solve various toy problems like playing Tic-Tac-Toe or PacMan or Poker just based on experience and reward feedback without ever being told the rules of the game. The implementation should be completely stand-alone in very light C++. Particular emphasis is on ease of use (installation, compilation, running, modification) and good documentation. The project involves programming of various sophisticated functions, and requires and furthers the understanding of the theoretical material taught in the main class.
    Each group will consist of 6-9 students. A group can self-organize and distribute work internally. The various modules/tasks/domains can be implemented by different students, each responsible for delivering a well-tested module including source and documentation. The group is responsible to deliver a final product consisting of documented source code, experimental results, and a final joint report.
    Lab director Tom Everitt will supervise the practical group project during lab sessions.


Rehearsal of lecture material and help with assignments: See Wattle


Theory: Individual Theory Assignments (20%). Late submissions will not be accepted.
Practice: Practical Group Assignment (25%). Late submissions will not be accepted.
Seminar: Seminar = 5 minute presentation of individual contribution to group assignment (10%).
Exam: Final written examination (45%) Exam (120min,written,closed-book,informal&math questions).
Know: What to know for the exam: Material in the course slides.
            The other provided reading material should help you to better understand the slides, but will itself not be examined.
Pass: To pass the course, students must pass each assignment and the final exam.


Updated:  25 November 2015 / Responsible Officer:   JavaScript must be enabled to display this email address. / Page Contact:   JavaScript must be enabled to display this email address. / Powered by: Snorkel 1.4