There are two little paragraphs in the 5e Dungeon Master's Guide, plus three bullet points, that offer a wonderful amount of room for expansion: Training, p. 231. In the 4th edition Dungeon Master's Guide II, there are a few pages on Alternative Rewards, and the group I played 4e with thought this was just about the best thing in the world - thus giving me incentive to explore training as treasure in 5e.
Personal Mechanical Plot
Way back in this blog's first year, I wrote about Five Kinds of Plot, and described one of them as Personal Mechanical Plot: story based on a single character mastering a new technique, spell, or other ability. It's usually awkward and frustrating, however, to require the player to complete story goals before receiving class abilities or being allowed to multiclass. All the worse if the player didn't plan his build ahead of time (players should never have to do this), so the DM can't plan ahead to guide the story in that direction.
The point of this, then, is that treasure doesn't get handed out on a schedule that is attached to XP progression, at least not in 5e. (The 4e rules suggest that boons or training rewards should in some way expire after five levels, in the same way that you would level to the point that a piece of magical gear became outdated. This philosophy is not relevant to 5e.) Depending on the structure of the training reward, it's plausible that you might level to the point that it's no longer a meaningful benefit. For example, the three training benefits that the DMG proposes are:
Situationally useful, or not. Gaining inspiration at dawn each day for 1d4+6 days is pretty cool, though it's more like a divine boon or temporary enlightenment than training, per se. Also, if you end your training and immediately go on a ten-day journey without many encounters, some DMs would rule that your training benefit was in fact no benefit at all. (The better ruling is that the countdown only advances when you don't have Inspiration at the start of the day.)
A skill proficiency becomes outdated if you happen to buy the Skilled feat just before receiving the reward. Best Practices DMing, as far as I'm concerned, would allow the player to respend that selection immediately, or within two sessions or so at the outside.
Likewise for any feat, and with the same Best Practices DMing solution.
Anyway, training rewards of this kind are basically intangible magic items, right? The rules demonstrate some of the possible range of power, since in a mathematical way a skill proficiency is worth a third of a feat. A tool proficiency is worth some amount less than that, since the rules on gaining new tool proficiencies are player-facing and, by default, available downtime options. I'm not actually interested in those relative values, though, only in the fact that training rewards can vary widely. Because they are, in a sense, intangible magic items, I feel like the game would benefit from requiring some kind of slot limit for the most potent ones, just as characters have a limit of three attunement slots (and less powerful or distinctive magic items don't cost one of these slots). Once you have multiple options to fill that "training slot," a short or long rest should be plenty to change them out, just like magic item attunement. In the fiction, I imagine you're just re-reading your teacher's lessons on that training, performing katas, meditating, whatever is appropriate to the training.
Personal Mechanical Plot, then, is a storyline that revolves around the need to reach a training montage. If you're going to include this in a game, it's important to share it around as equally as any other kind of personal attention and reward - hypothetically, if one character got six magic items that all required attunement and another character got six training rewards that did not require attunement (and you did not use the "training slots" I am proposing), the training-reward character might have a substantive advantage, because she gets to use 100% of her reward, rather than 50%. Again, this power-gaming approach isn't constructive or interesting, but it's important to account for in design and game-running.
There are times in gaming when acquiring a specific piece of treasure - a holy avenger sword comes to mind - is the lure that gets PCs interested in the story and its conflict in the first place. If anything, though, I'd think this would be more common with training-as-treasure. Some examples:
A sword-saint at a distant monastery is the last keeper of a potent, secret technique. She wishes to find a worthy student to pass this blade-lore on to before she departs from this life. This also works if it's a room decorated with detailed mosaics demonstrating the technique, or detailed descriptions in a musty old tome, or paint on the wall of a cave.
A dragonborn or draconic sorcerer seeks to unlock a deeper power of the bloodline and a closer connection to his ancestral dragon. The dragon, of course, demands a trial by fire.
One who possesses the rare and mighty flametongue sword (supposing for a moment that there are only a few in the whole campaign setting) may benefit from its common powers, but the dedicated wielder may unlock greater powers: the ability to parry white dragonbreath and spells of ice, the ability to blacken the sword's flames to damage creatures of fire, and even the ability to exalt the blade's flame to cleave through demonic foes.
When a warlock goes on a quest on behalf of her patron, shouldn't her reward be directly related to her class, and something other than a new item? The patron is the source of her class powers; surely the patron could be the source of more power if she's especially favored? A bonus invocation seems like it would be about right. If the warlock keeps doing this, though, I think she should get additional options for that bonus invocation slot, which she can switch out during a short or long rest.
Allowing spellcasters to pursue the wizard's School benefits (including wizards wanting School benefits from outside their own School) makes sense, and pleasingly emphasizes the academic nature of the wizard. So run a few scenes, possibly as a recurring downtime thing, that is Hogwarts with some serial numbers filed off. For that matter, it could be a really nice bargaining offer on the NPC side when the PC spellcaster has a new spell to trade. Anyway, there are a lot of plausible challenges here, but clearing those centaurs out of the Forbidden Forest comes to mind. Alternately, pose a series of logic problems, for which the PC has to perform research or go on adventures just to get the clues.
So I mentioned not requiring a training quest for advancement. (NB. I am not talking about the cash-for-training rules on p. 131 of the DMG. Those are a matter of taste, but basically fine.) Maybe instead you require an Intelligence check, DC 5 + number of levels gained since the last time you failed this check. On a success, bully for you, pass Go and collect one character level. On a failure, you may gain this level, but you come to a point in your next level such that you can't teach yourself, and the easily-available trainers can't help you get past your block. You've got to find a new trainer, possibly recruiting them as a contact and ally. Once you do this, you can advance freely again. (You start rolling Intelligence checks again the level after that).
What I'm imagining here is really more like if the Level Up move in Dungeon World required a roll, and that roll had a 6- outcome. Obviously you'd also have 7-9 and 10+ outcomes in such a case - I just don't know offhand what those would be.
I think it makes a lot of sense for vision quests to result in new training rewards. I seem to recall a lot of this in Baldur's Gate, and maybe also Planescape: Torment. It usually makes less sense for vision quests - or astral journeys, for that matter - to result in physical treasure, but resulting in useful knowledge? Well, yeah.
Training Reward Brainstorm
My parameters for good training rewards: seems like knowledge or a technique; as much as possible, applicable to multiple classes; not so powerful as to overwhelm or duplicate a primary ability from a character class (for example, Extra Attack is not a good candidate); actions are (nearly) always more interesting than passive abilities; and most of the time a specific NPC should be the source of the training, but there can be exceptions to this. For reasons discussed in a previous post, it's difficult to give fighters new attack options without upsetting the apple cart. I especially like offering alternate reactions, because they have interesting triggers.
Make an attack. If that attack hits, deal damage equal to your Strength modifier, and your opponent's armor (including natural armor, but ineffective against characters with no armor at all) is damaged. Until that opponent takes a short rest, all characters gain a +1d4 bonus to attacks against that character. Such attacks against the target stack, increasing the die value of the bonus by one die step.
As a reaction when you are the target of a Shove attack, you may roll both a Strength (Athletics) and Dexterity (Acrobatics) check. If both of your checks beat the attacker's opposed roll, you may throw the attacker up to ten feet in any direction. The target is prone at the end of this movement.
When you take fire, cold, lightning, or thunder damage, you may spend your reaction to reduce the damage you take by 1d8 + your Constitution bonus. The next time you cast a spell that deals damage of the same type before taking a short or long rest, your spell deals an additional 1d8 damage.
You can sometimes chronologically displace yourself. You create a duplicate of yourself that is identical to you in every way. The DM controls this duplicate, but it is you: it never deliberately harms you in any way, and always aids you to the fullest of its ability. Each time it takes damage or undergoes any other major source of stress, it must make a Charisma saving throw (DC = 10 or half of the damage suffered, whichever is greater). On a failed saving throw, it disappears, returning to its own time. It also disappears the second time any specific duplicate would roll initiative (that is, a single duplicate never lasts for more than one combat encounter.) You must "pay back" this appearance, either by taking the Recuperation action at your first opportunity for downtime, or if you go too long (in the DM's judgment) without doing so, the DM may force you to miss 1d4 rounds of an encounter when it would be most inconvenient to do so. You are chronologically displaced - effectively banished to another time - during the duration. If possible, track the amount of damage your duplicate took, and suffer that damage on returning from chronological displacement.
A god or organized religion appoints you as a proxy in a cosmic struggle. (Surely this is a common element of high-level play in at least half of all campaigns.) You receive the power of the First Malediction, by which the gods won their victory against (creature type, probably aberrations but maybe giants, dragons, fiends, or whatever) at the dawn of time. When you utter the First Malediction, it affects a single creature of the specified type. The creature makes a saving throw against DC 20. On a failure, it takes 2d10 + your Wisdom modifier radiant or necrotic damage (as appropriate to the deity or religion); on a success it takes half damage. This damage increases to 4d10 + Wis mod at 5th level, 6d10 + Wis mod at 11th level, and 8d10 + Wis mod at 17th level. The first time you use this power after a long rest, it has no additional cost. Further uses cost you a number of Hit Dice equal to your previous number of uses since your last long rest. Characters with the Channel Divinity class feature may ignore the Hit Dice cost of their current usage by spending a use of Channel Divinity.
Whenever a character (not an object or ambient effect) targets you with an effect that forces a Wisdom saving throw and you succeed, you may spend your reaction, or the bonus action or action of your following turn, to pluck the answer to one question from the attacker's mind. This question must be phrased to be answered with a Yes or No.
When you attack with a melee weapon in one hand and nothing (or a gauntlet) in your other hand, and your attack misses, you may spend a bonus action to make a pommel strike, haft strike, or the like as a follow-up attack. This attack deals 1d4 bludgeoning damage + your Strength or Dexterity bonus.
All of these things seem to me like they'd be fun. I must acknowledge Metroplexity as a major source of inspiration here, as many kinds of actions (but especially fights) grant new and useful combat techniques. Also, the Wildlands South NERO campaign, in which the opportunity to learn new Lost Arts was one of the most sought-after rewards that the game offered. Maybe you agree that this kind of thing is cool, in which case you are a person of discernment and high moral character! Even if you don't, though, the Comments field is open to you.