Advanced Topics in Artificial Intelligence COMP4620/COMP8620

Welcome to the Advanced AI course at the ANU !

The course focuses on the Foundations of AI, including inductive inference, sequence prediction, decision-making under uncertainty, reinforcement learning, intelligent agents, information theory, philosophical foundations, and others.


14Oct17: Written exam will be Wednesday, 15.Nov.2017, 14:00-16:15, 7-11 Barry Drive First Floor Right Side
19Sep17: Assignment 2 available
31Jul17: Assignment 1 available
26May17: website contents created


Offered By: Intelligent Agents Team @ The AI Group @ Research School of Computer Science @ Australian National University
Offered In: Second Semester, 2017 (24 July to 17 November). See Schedule below
Lecturer: Marcus Hutter
Tutors/Labs/Assistance: Sultan Javed Majeed
Target: Undergraduate (COMP4620) and Graduate (COMP8620) students. Others welcome.
Enrollment: Undergraduate & Masters: The usual way via ISIS. Honors&Others: Contact admin/lecturer.
Admin: Sandra Harrison or, 02 6125 4450, Office N202, Level 2 CSIT Bld.108
Class representative: See here for further information.
Course Subjects: Computer Science & Mathematics & Statistics
Unit Value: 6 units
Time Table: See Schedule below for details
Indicative Assessment: Assignments (45%); Seminar (10%); Examination (45%) [details]
Indicative Workload: ~25h lectures, ~6h 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:


Machine Learning (COMP4670/COMP8600) or Artificial Intelligence (COMP3620/COMP6320) or Information Theory (COMP2610/COMP6261). Students are expected to be familiar with the material in the AI book Russell&Norvig (2010) Chp. 2, 3, 5.2, 5.5, 13, 15.1-2, 17.1-3, 21; and Chapter 1 of Li&Vitanyi (2008), which is a great refresher of basic computability, information, and probability theory.
    The course requires good math and probability skills in general. It is often regarded as (one of) the hardest CS course(s) at ANU, and definitely is more challenging than the three courses above.
    The following self-evaluation may help you determine whether to take this course or not. If you can answer most questions essentially correctly within the suggested time, you are probably prepared for the course. If you have difficulties answering say 3 or more questions even given extra time, the course is probably too difficult for you. Study the material above before you consult the solution.
    Note: If you are planning to do a project with me, excelling in this course is a de-facto prerequisite, since most of my projects require the knowledge taught in this course.

Course Description

This is an advanced undergraduate and graduate course that covers advanced topics in Artificial Intelligence. The course focuses 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: 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: 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.


Lectures: Tue (JD101) & Wed (JD102) 11ºº-12ºº & Thu (JD102) 13ºº-14ºº John Dedman Math Bld.27;
Tutorials: Tue.13-15ºº |Wed.15-17ºº |Thu.11-13ºº N108 CSIT Bld.108;
Labs: Tue|Wed.15-17ºº N111 |Fri.16-18ºº N112 CSIT Bld.108

Lectures, Tutorials, and Labs will not run every day/week!
See schedule below for details.

#Week Lecture / Tutorial / Lab
to be updated throughout the course
124Jul - 28Jul
do self-evaluation (solution)
Overview & Introduction [Advertisement]
[Slides] Reading:[Legg08.Chp.1]
231Jul -4Aug
get assignment 1
Information Theory & Kolmogorov Complexity
[Slides] Reading:[UAIBook.Sec.2.2]
37Aug - 11Aug Bayesian Probability Theory
[Slides] Reading:[UAIBook.Sec.2.3]
Algorithmic Probability & Universal Induction
[Slides] Reading:[UAIBook.Sec.2.4]
No tutorials
414Aug - 18Aug Minimum Description Length
[Slides] Optional Reading:[MDL.Chp.1]
Universal Similarity [Slides] Optional Reading:[USM]
No tutorials. No lecture on Thu.17.Aug
521Aug - 25Aug Tutorials (only). No lectures
628Aug - 1Sep Bayesian Sequence Prediction [Slides] Reading: Parts of [UAIBook.Chp.3]
Context Tree Weighting [Slides] Reading:[CTW]
4Sep - 15Sep break
718Sep - 22Sep
hand in assignment 1
get assignment 2
Universal Rational Agents [Slides] Reading:[UAIBook.Chp.4.1&4.2&5.1.1]
MC-AIXI-CTW [Slides] Reading:[MC-AIXI-CTW]
Orientation Lab for Assignment 2
824Sep - 29Sep Theory of Rational Agents
[Slides] Reading:try [UAIBook.Chp.5]
Q&A Lab for Assignment 2
92oct - 6oct Approximations and Applications [Slides]
Q&A Lab for Assignment 2
109oct - 13oct Solutions to Assignment 1 (in lecture slots for all students)
Q&A Lab for Assignment 2
1116oct - 20oct
hand in assignment 2
Q&A Lab for Assgnment 2 (only). No Lectures
1223oct - 27oct
Discussion [Slides] Reading:[UAIBook.Chp.8]
+ Student Presentation of Individual Contribution to Practical Assignment. Send slides in advance to Sultan Javed Majeed

Written exam will be Wednesday, 15 November 2017, 14:00-16:15, 7-11 Barry Drive First Floor Right Side, see official Time Table and Assessment section below for details.


Theory Assignment 1: The theory assignment is to be done individually or in groups of two students, and will involve various mathematical exercises that will deepen the understanding of the lectured material. Sultan Javed Majeed 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. A code skeleton in very light C++ will be provided, but a group can request to use a different programming language at their own risk. 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 5-8 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 Sultan Javed Majeed 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, and result in 0 points, hence failure of the course.
Practice: Practical Group Assignment (25%). Late submissions will not be accepted, and result in 0 points, hence failure of the course.
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 similar to Ass.1).
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.
Grading: Final course marks will be subject to moderation, so may differ from the raw sum of assessment marks.